Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]

Let $G=\langle x\rangle$ be the cyclic group of order $n$ generated by $x$. Then, \begin{align} n &= |G| \\ &= \sum_{1\leq d\leq n} |\{\text{elements of order } d\}| \\ &= \sum_{d|n}|\{\text{elements of order } d\}| \end{align} by Lagrange's Theorem. But $G$ has a unique cyclic subgroup of order $d$ for each $d|n$, namely $\langle x^{n/d}\rangle$. Moreover, each such subgroup has $\varphi(d)$ generators, so $$n = \sum_{d|n}\varphi(d)$$

Hint: You can show that $\sum\limits_{d|n}\phi(d) = \sum\limits_{d|n}\phi(\frac{n}{d}) $ but $\phi(\frac{n}{d})$ is all numbers with GCD of $d$ with $n$. Therefore the last sum counts all numbers till $n$ and is equal to $n$.

The simplest proof I know is this:

Consider all proper fractions of the form $a/n$. There are $n$ of those. When you consider their reduced forms you get fractions of the form $b/d$ with $d|n$ and $(b,d)=1$. By definition, there are $\phi(d)$ of those. The result follows.

Here's one approach:

Consider the polynomial $x^n-1$ as a polynomial over the complex numbers $\mathbb{C}$. You can easily see, almost tautologically, that

$$x^n-1=\prod_{d\mid n}\Phi_d(x)\qquad(\ast)$$

where $\Phi_d(x)$ is the polynomial whose roots are the primitive $d^{\text{th}}$ roots of unity (i.e. solutions to $x^d-1$ that do not satisfy $x^c-1$ for $0<c<d$).

But, rephrasing the definition, $\Phi_d(x)$ is the polynomial with roots $e^{\frac{2\pi i r}{d}}$ where $e^{\frac{2\pi r s}{d}}\ne 1$ for $0<s<d$. But, this is saying that $sr\not\equiv 0\mod d$ for $0<s<d$, or that $d$ and $r$ have no common factors. Since we only need to care about $r$ which are less than or equal to $d$ we see that, in fact, the are $\phi(d)$ such roots of $\Phi_d(x)$.

This allows us to conclude that $\deg \Phi_d(x)=\phi(d)$. Indeed, since $\Phi_d(x)\mid x^n-1$, and $x^n-1$ has no repeated roots in $\mathbb{C}$ (it's coprime to its derivative) we see that $\Phi_d(x)$ has no repeated roots. Thus, $\deg\Phi_d(x)$ is the number of roots of $\Phi_d(x)$ which is $\phi(d)$.

So, by comparing degrees in $(\ast)$ we get:

$$n=\sum_{d\mid n}\deg\Phi_d(x)=\sum_{d\mid n}\phi(d)$$