Editing Euler's totient function (section)

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