lean_workbook_plus_42311

Proof: Consider the fractions $\dfrac{1}{n}, \dfrac{2}{n}, \ldots, \dfrac{n}{n}$ , and reduce them. There are exactly $\phi(d)$ of them with denominator $d$ , where $d|n$ . So the number of fractions is $\sum_{d|n}\phi(d)$ . But it is also $n$ , so $\sum_{d|n}\phi(d) = n$ .