Sum of the totient over the divisors

Statement

Let $n$ be a positive integer. Then $\sum_{d \mid n} \varphi(d) = n$, where the sum runs over the positive divisors $d$ of $n$, and $\varphi$ is Euler's totient function.

Remarks

The proof: sort the fractions $\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$ by their denominators in lowest terms. For each divisor $d$ of $n$, exactly $\varphi(d)$ of them have the denominator $d$. For example, for $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$. With the Möbius inversion formula, the result gives $\varphi(n) = \sum_{d \mid n} \mu(d) \, n / d$.

History

Gauss proved this identity in his Disquisitiones Arithmeticae of 1801.

Explanations

L1 human

Write the fractions $\frac{1}{6}, \frac{2}{6}, \dots, \frac{6}{6}$ in lowest terms: $\frac16, \frac13, \frac12, \frac23, \frac56, \frac11$. The denominators $1, 2, 3, 6$ appear $1, 1, 2, 2$ times. These are $\varphi(1), \varphi(2), \varphi(3), \varphi(6)$, and their sum is $6$.