Editing Euler's totient function (section)

===Euler's product formula===

It states
:<math>\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),</math>
where the product is over the distinct [[prime number]]s dividing {{mvar|n}}.

An equivalent formulation is
<math display="block">\varphi(n) = p_1^{k_1-1}(p_1{-}1)\,p_2^{k_2-1}(p_2{-}1)\cdots p_r^{k_r-1}(p_r{-}1),</math> where <math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}</math> is the [[prime factorization]] of <math>n</math> (that is, <math>p_1, p_2,\ldots,p_r</math> are distinct prime numbers).

The proof of these formulae depends on two important facts.

==== Phi is a multiplicative function ====

This means that if {{math|1=gcd(''m'', ''n'') = 1}}, then {{math|1=''φ''(''m'') ''φ''(''n'') = ''φ''(''mn'')}}. ''Proof outline:'' Let {{mvar|A}}, {{mvar|B}}, {{mvar|C}} be the sets of positive integers which are [[coprime]] to and less than {{mvar|m}}, {{mvar|n}}, {{mvar|mn}}, respectively, so that {{math|1={{!}}''A''{{!}} = ''φ''(''m'')}}, etc. Then there is a [[bijection]] between {{math|''A'' × ''B''}} and {{mvar|C}} by the [[Chinese remainder theorem]].

==== Value of phi for a prime power argument ====

If {{mvar|p}} is prime and {{math|''k'' ≥ 1}}, then

:<math>\varphi \left(p^k\right) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k \left( 1 - \tfrac{1}{p} \right).</math>

''Proof'': Since {{mvar|p}} is a prime number, the only possible values of {{math|gcd(''p''<sup>''k''</sup>, ''m'')}} are {{math|1, ''p'', ''p''<sup>2</sup>, ..., ''p''<sup>''k''</sup>}}, and the only way to have {{math|gcd(''p''<sup>''k''</sup>, ''m'') > 1}} is if {{mvar|m}} is a multiple of {{mvar|p}}, that is, {{math|1=''m'' ∈ {{mset|1=''p'', 2''p'', 3''p'', ..., ''p''<sup>''k'' − 1</sup>''p'' = ''p''<sup>''k''</sup>}}}}, and there are {{math|''p''<sup>''k'' − 1</sup>}} such multiples not greater than {{math|''p''<sup>''k''</sup>}}. Therefore, the other {{math|''p''<sup>''k''</sup> − ''p''<sup>''k'' − 1</sup>}} numbers are all relatively prime to {{math|''p''<sup>''k''</sup>}}.

====Proof of Euler's product formula====

The [[fundamental theorem of arithmetic]] states that if {{math|''n'' > 1}} there is a unique expression <math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, </math> where {{math|''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>''r''</sub>}} are [[prime number]]s and each {{math|''k''<sub>''i''</sub> ≥ 1}}. (The case {{math|1=''n'' = 1}} corresponds to the empty product.) Repeatedly using the multiplicative property of {{mvar|φ}} and the formula for {{math|''φ''(''p''<sup>''k''</sup>)}} gives

:<math>\begin{array} {rcl}
\varphi(n)&=& \varphi(p_1^{k_1})\, \varphi(p_2^{k_2}) 
\cdots\varphi(p_r^{k_r})\\[.1em]
&=& p_1^{k_1} \left(1- \frac{1}{p_1} \right) p_2^{k_2} \left(1- \frac{1}{p_2} \right) \cdots p_r^{k_r}\left(1- \frac{1}{p_r} \right)\\[.1em]
&=& p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \left(1- \frac{1}{p_1} \right) \left(1- \frac{1}{p_2} \right) \cdots \left(1- \frac{1}{p_r} \right)\\[.1em]
&=&n \left(1- \frac{1}{p_1} \right)\left(1- \frac{1}{p_2} \right) \cdots\left(1- \frac{1}{p_r} \right).
\end{array}</math>

This gives both versions of Euler's product formula.

An alternative proof that does not require the multiplicative property instead uses the [[inclusion-exclusion principle]] applied to the set <math>\{1,2,\ldots,n\}</math>, excluding the sets of integers divisible by the prime divisors.

====Example====

:<math>\varphi(20)=\varphi(2^2 5)=20\,(1-\tfrac12)\,(1-\tfrac15)
=20\cdot\tfrac12\cdot\tfrac45=8.</math>

In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.

The alternative formula uses only integers:<math display="block">\varphi(20) = \varphi(2^2 5^1)= 2^{2-1}(2{-}1)\,5^{1-1}(5{-}1) = 2\cdot 1\cdot 1\cdot 4 = 8.</math>