# derivation of Euler phi-function

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\geq 2$ and $p_{1},p_{2},\cdots,p_{r}$ be all prime divisors of n. Let $N=\{a\mid 0\leq a and $A_{i}:=\{a\mid 0\leq 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,

 $\displaystyle\phi(n)=\#(N)=\sum_{J\subset\{1,2,\cdots,r\}}(-1)^{\#(J)}\#(A_{J}% )=\sum_{J\subset\{1,2,\cdots,r\}}(-1)^{\#(J)}\frac{n}{p_{J}}=n\sum_{J\subset\{% 1,2,\cdots,r\}}(-1)^{\#(J)}\frac{1}{p_{J}}$ $\displaystyle=n(1-(\frac{1}{p_{1}}+\frac{1}{p_{2}}+\cdots+\frac{1}{p_{r}})+% \cdots(-1)^{r}\frac{1}{p_{1}p_{2}\cdots p_{r}})=n\prod_{p|n}(1-\frac{1}{p}).$

$\Box$

Title derivation of Euler phi-function DerivationOfEulerPhifunction 2013-03-22 17:42:52 2013-03-22 17:42:52 jwaixs (18148) jwaixs (18148) 22 jwaixs (18148) Derivation msc 11-00