derivation of Euler phi-function

In this “proof” we will construct the solution for the Euler phi-function, $\varphi (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⟺$ $a$ is not divisible by $p$ for all primes $p$ dividing $n$.

Let $n\ge 2$ and $p_1,p_2,\mathrm{\cdots },p_r$ be all prime divisors of n. Let and . If $J\subset \{1,2,\mathrm{\cdots },r\}$ than $p_J:={\prod }_{j\in J}{p}_i$.

Thus, $\mathrm{\#}(A_J)=\mathrm{\#}({\bigcap }_{j\in J}{A}_j)=\mathrm{\#}(\{a\in A:p_J|a\})=\frac{n}{p_J}$

Using inclusion-exclusion,

$\varphi (n)=\mathrm{\#}(N)={\displaystyle \sum _{J\subset \{1,2,\mathrm{\cdots },r\}}}{(-1)}^{\mathrm{\#}(J)}\mathrm{\#}(A_J)={\displaystyle \sum _{J\subset \{1,2,\mathrm{\cdots },r\}}}{(-1)}^{\mathrm{\#}(J)}{\displaystyle \frac{n}{p_J}}=n{\displaystyle \sum _{J\subset \{1,2,\mathrm{\cdots },r\}}}{(-1)}^{\mathrm{\#}(J)}{\displaystyle \frac{1}{p_J}}$

$=n(1-({\displaystyle \frac{1}{p_1}}+{\displaystyle \frac{1}{p_2}}+\mathrm{\cdots }+{\displaystyle \frac{1}{p_r}})+\mathrm{\cdots }{(-1)}^r{\displaystyle \frac{1}{p_1{p}_2\mathrm{\cdots }{p}_r}})=n{\displaystyle \prod _{p|n}}(1-{\displaystyle \frac{1}{p}}).$

$\mathrm{\square }$

Title	derivation of Euler phi-function
Canonical name	DerivationOfEulerPhifunction
Date of creation	2013-03-22 17:42:52
Last modified on	2013-03-22 17:42:52
Owner	jwaixs (18148)
Last modified by	jwaixs (18148)
Numerical id	22
Author	jwaixs (18148)
Entry type	Derivation
Classification	msc 11-00