In this ``proof" we will construct the solution for the Euler phi-function, $ \phi(n) = n \prod_{ p | n } ( 1 - \frac{1}{n} ) $ .

We will do this for the natural number $ n > 0 $ . Keep in mind that $ \gcd(a,n) = 1 \Longleftrightarrow $ $ a $ is not divisible by $ p $ for all primes $ p $ dividing $ n $ .

Let $ n \ge 2 $ and $ p_1,p_2,\cdots,p_r $ be all prime divisors of n. Let $ N=\{a \mid 0 \leq a < n, \gcd(a,n) = 1\} $ and $ A_i := \{ a \mid 0 \leq a < n, p_i | a \} $ . If $ J \subset \{ 1,2,\cdots,r \} $ than $ p_J := \prod_{j \in J} p_i $ .

Thus, $ \# ( A_J ) = \# ( \bigcap_{ j \in J } A_j ) = \# ( \{ a \in A : p_J | a \} ) = \frac{ n }{ p_J } $

Using inclusion-exclusion,