Divisibility property of the totient function $\varphi$ Let $n$ be a positive integer. Prove that \begin{equation} \sum_{d \vert n} \varphi(d)= n \end{equation} where $\varphi$ is the totient function of Euler.

For $d\vert n$, let $\mathcal{O}_d$ be the sets of elements of order $d$ in $\mathbb{Z}/n\mathbb{Z}$. Using Lagrange's theorem, $\\{\mathcal{O}_d\\}_{d\vert n}$ is a partition of $\mathbb{Z}/n\mathbb{Z}$. Howeover, as an element of order $d$ spans a group isomorphic to $\mathbb{Z}/d\mathbb{Z}$, $\mathcal{O}_d$ has cardinality $\varphi(d)$.