structural:reformatting, structural:expansion, information:classification, linguistic:translation
Divisor sum

The property established by Gauss, that

where the sum is over all positive divisors d of n, can be proven in several ways. (See Arithmetical function for notational conventions.)

One proof is to note that φ (d) is also equal to the number of possible generators of the cyclic group C ; specifically, if C = ⟨ g ⟩ with g = 1, then g is a generator for every k coprime to d. Since every element of C generates a cyclic subgroup, and each subgroup C ⊆ C is generated by precisely φ (d) elements of C, the formula follows. Equivalently, the formula can be derived by the same argument applied to the multiplicative group of the n th roots of unity and the primitive d th roots of unity.

The formula can also be derived from elementary arithmetic. For example, let n = 20 and consider the positive fractions up to 1 with denominator 20:

Put them into lowest terms:

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

Möbius inversion applied to the divisor sum formula gives

where μ is the Möbius function, the multiplicative function defined by μ (p) = − 1 {\displaystyle \mu (p)=-1} and μ (p k) = 0 {\displaystyle \mu (p^{k})=0} for each prime p and k ≥ 2. This formula may also be derived from the product formula by multiplying out ∏ p ∣ n (1 − 1 p) {\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})} to get ∑ d ∣ n μ (d) d. {\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}

An example: φ (20) = μ (1) ⋅ 20 + μ (2) ⋅ 10 + μ (4) ⋅ 5 + μ (5) ⋅ 4 + μ (10) ⋅ 2 + μ (20) ⋅ 1 = 1 ⋅ 20 − 1 ⋅ 10 + 0 ⋅ 5 − 1 ⋅ 4 + 1 ⋅ 2 + 0 ⋅ 1 = 8. {\displaystyle {\begin{aligned}\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\\&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}}