$\sum_{d|n} \varphi(d)=n$

Question

I want to solve $\sum_{d|n} \varphi(d)=n$ using Group theory.

Here, $\varphi(d)$ is Euler's totient function.

I think I should use $\Bbb Z_n$ and fundamental theorem of cyclic group.

Then I use $\varphi(d)$ as the number of generators of $\Bbb Z_d$

But I can't link this idea with the sum of all $ d|n $

Help me!

Answer 1

Hint: use the fact that, if $n=\prod p_i^{\alpha_i}, \mathbb {Z_n}\simeq \prod \mathbb {Z_{p_i^{\alpha_i}}}$.

Answer 2

The order of each element $k$ of the cyclic group $\mathbb{Z}_n$ is a divisor $d$ of $n$. Therefore, $$ \left| \mathbb{Z}_n\right| = \sum_{d|n}\#\,\lbrace k \in \mathbb{Z}_n: k\text{ of order } d \rbrace $$ An element $k$ of $\mathbb{Z}_n$ verifies $d \cdot k = 0$ if and only if $k$ belongs to the subgroup generated by $l = n/d$, which is a copy of $\mathbb{Z}_d$. Then, $k$ is of order $d$ if and only if it is a generator of this subgroup. However, the number of generators of $\mathbb{Z}_d$ is $\varphi(d)$. Therefore, $$ \#\,\lbrace k \in \mathbb{Z}_n: k\text{ of order } d \rbrace = \varphi(d) $$ Now, it is enough to note the obvious, $\left| \mathbb{Z}_n\right| = n$.

Answer 3

As usual, Gauss's proof is the best. For each element of $C_n$, it generates a cyclic group of order $d$ dividing $n$. And there are $\varphi(d)$ such elements for each such $d$.