Editing Euler's totient function (section)

== Computing Euler's totient function ==

There are several formulae for computing {{math|''φ''(''n'')}}.

===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>

===Fourier transform===

The totient is the [[discrete Fourier transform]] of the [[Greatest common divisor|gcd]], evaluated at 1.<ref>{{harvtxt|Schramm|2008}}</ref> Let

:<math> \mathcal{F} \{ \mathbf{x} \}[m] = \sum\limits_{k=1}^n x_k \cdot e^{{-2\pi i}\frac{mk}{n}}</math>

where {{math|''x<sub>k</sub>'' {{=}} gcd(''k'',''n'')}} for {{math|''k'' ∈ {1, ..., ''n''}<nowiki/>}}. Then

:<math>\varphi (n) = \mathcal{F} \{ \mathbf{x} \}[1] = \sum\limits_{k=1}^n \gcd(k,n) e^{-2\pi i\frac{k}{n}}.</math>

The real part of this formula is

:<math>\varphi (n)=\sum\limits_{k=1}^n \gcd(k,n) \cos {\tfrac{2\pi k}{n}}
.</math>

For example, using <math>\cos\tfrac{\pi}5 = \tfrac{\sqrt 5+1}4
</math> and <math>\cos\tfrac{2\pi}5 = \tfrac{\sqrt 5-1}4
</math>:<math display="block">\begin{array}{rcl}
\varphi(10) &=& \gcd(1,10)\cos\tfrac{2\pi}{10} + \gcd(2,10)\cos\tfrac{4\pi}{10}
+ \gcd(3,10)\cos\tfrac{6\pi}{10}+\cdots+\gcd(10,10)\cos\tfrac{20\pi}{10}\\
&=& 1\cdot(\tfrac{\sqrt5+1}4)  + 2\cdot(\tfrac{\sqrt5-1}4) + 
1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(-\tfrac{\sqrt5+1}4) + 5\cdot (-1) \\
&& +\  2\cdot(-\tfrac{\sqrt5+1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(\tfrac{\sqrt5-1}4) +
1\cdot(\tfrac{\sqrt5+1}4) + 10 \cdot (1) \\
&=& 4 .
\end{array}
</math>Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of {{mvar|n}}. However, it does involve the calculation of the greatest common divisor of {{mvar|n}} and every positive integer less than {{mvar|n}}, which suffices to provide the factorization anyway.

===Divisor sum===

The property established by Gauss,<ref>Gauss, DA, art 39</ref> that

:<math>\sum_{d\mid n}\varphi(d)=n,</math>

where the sum is over all positive divisors {{mvar|d}} of {{mvar|n}}, can be proven in several ways. (See [[Arithmetical function#Notation|Arithmetical function]] for notational conventions.)

One proof is to note that {{math|''φ''(''d'')}} is also equal to the number of possible generators of the [[cyclic group]] {{math|''C''<sub>''d''</sub>}} ; specifically, if {{math|''C''<sub>''d''</sub> {{=}} ⟨''g''⟩}} with {{math|1=''g''<sup>''d''</sup> = 1}}, then {{math|''g''<sup>''k''</sup>}} is a generator for every {{mvar|k}} coprime to {{mvar|d}}. Since every element of {{math|''C''<sub>''n''</sub>}} generates a cyclic [[subgroup]], and each subgroup {{math|''C''<sub>''d''</sub> ⊆ ''C''<sub>''n''</sub>}} is generated by precisely {{math|''φ''(''d'')}} elements of {{math|''C''<sub>''n''</sub>}}, the formula follows.<ref>Gauss, DA art. 39, arts. 52-54</ref> Equivalently, the formula can be derived by the same argument applied to the [[Root of unity#Group of nth roots of unity|multiplicative group of the {{mvar|n}}th roots of unity]] and the [[primitive root of unity|primitive {{mvar|d}}th roots of unity]].

The formula can also be derived from elementary arithmetic.<ref>Graham et al. pp. 134-135</ref> For example, let {{math|''n'' {{=}} 20}} and consider the positive fractions up to 1 with denominator 20:
:<math>
 \tfrac{ 1}{20},\,\tfrac{ 2}{20},\,\tfrac{ 3}{20},\,\tfrac{ 4}{20},\,
 \tfrac{ 5}{20},\,\tfrac{ 6}{20},\,\tfrac{ 7}{20},\,\tfrac{ 8}{20},\,
 \tfrac{ 9}{20},\,\tfrac{10}{20},\,\tfrac{11}{20},\,\tfrac{12}{20},\,
 \tfrac{13}{20},\,\tfrac{14}{20},\,\tfrac{15}{20},\,\tfrac{16}{20},\,
 \tfrac{17}{20},\,\tfrac{18}{20},\,\tfrac{19}{20},\,\tfrac{20}{20}.
</math>

Put them into lowest terms:
:<math>
 \tfrac{ 1}{20},\,\tfrac{ 1}{10},\,\tfrac{ 3}{20},\,\tfrac{ 1}{ 5},\,
 \tfrac{ 1}{ 4},\,\tfrac{ 3}{10},\,\tfrac{ 7}{20},\,\tfrac{ 2}{ 5},\,
 \tfrac{ 9}{20},\,\tfrac{ 1}{ 2},\,\tfrac{11}{20},\,\tfrac{ 3}{ 5},\,
 \tfrac{13}{20},\,\tfrac{ 7}{10},\,\tfrac{ 3}{ 4},\,\tfrac{ 4}{ 5},\,
 \tfrac{17}{20},\,\tfrac{ 9}{10},\,\tfrac{19}{20},\,\tfrac{1}{1}
</math>

These twenty fractions are all the positive {{sfrac|''k''|''d''}} ≤ 1 whose denominators are the divisors {{math|''d''  {{=}} 1, 2, 4, 5, 10, 20}}. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely {{sfrac|1|20}}, {{sfrac|3|20}}, {{sfrac|7|20}}, {{sfrac|9|20}}, {{sfrac|11|20}}, {{sfrac|13|20}}, {{sfrac|17|20}}, {{sfrac|19|20}}; by definition this is {{math|''φ''(20)}} fractions. Similarly, there are {{math|''φ''(10)}} fractions with denominator 10, and {{math|''φ''(5)}} fractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of size {{math|''φ''(''d'')}} for each {{math|''d''}} dividing 20. A similar argument applies for any ''n.''

[[Möbius inversion]] applied to the divisor sum formula gives
:<math> \varphi(n) = \sum_{d\mid n} \mu\left( d \right) \cdot \frac{n}{d}  = n\sum_{d\mid n} \frac{\mu (d)}{d},</math>

where {{mvar|μ}} is the [[Möbius function]], the [[multiplicative function]] defined by <math>\mu(p) = -1</math> and <math> \mu(p^k) = 0</math> for each prime {{math|1=''p''}} and {{math|1=''k'' ≥ 2}}. This formula may also be derived from the product formula by multiplying out <math display="inline"> \prod_{p\mid n} (1 - \frac{1}{p}) </math> to get <math display="inline"> \sum_{d \mid n} \frac{\mu (d)}{d}. </math>

An example:<math display="block">
 \begin{align}
\varphi(20) &= \mu(1)\cdot 20 + \mu(2)\cdot 10 +\mu(4)\cdot 5 +\mu(5)\cdot 4 + \mu(10)\cdot 2+\mu(20)\cdot 1\\[.5em]
&= 1\cdot 20 - 1\cdot 10 + 0\cdot 5 - 1\cdot 4 + 1\cdot 2 + 0\cdot 1 = 8.
\end{align}
</math>