## An identity involving Euler’s totient function

Let $\varphi$ denote Euler’s totient function and let $n$ be a positive integer. Prove that $\sum_{d|n} \varphi(d) = n$, where $d$ ranges over the positive divisors of $n$.

Let $Z_n = \langle x \rangle$ denote the (unique) cyclic group of order $n$. Every element of $Z_n$ generates a unique (cyclic) subgroup, which is cyclic. Recall that $Z_n$ has a unique (cyclic) subgroup of order $d$ for each $d|n$, and that each of these is generated by $\varphi(d)$ elements. That is, letting $G_d$ denote the set of generators of $Z_d$, we have $Z_n = \bigcup_{d|n} G_d$ where the union is disjoint. Thus $\sum_{d|n} \varphi(d) = n$.