Proof: $$\sum_{d|N}\phi(d)=N$$ where the sum is over $d\in div(N)$
Let $G$ be the cyclic group $\mathbb Z/N \mathbb Z$. Then $$N = \sum_{g \in G} 1 = \sum_{d|N}\sum_{g \in G, ord(g)=d} 1=\sum_{d|N}\phi(d)$$
The step from $$\sum_{d|N}\sum_{g \in G, ord(g)=d} 1=\sum_{d|N}\phi(d)$$ is easy since the number of elements in $G$ having order $d$, where $d | N=|G|$ is $\phi(d)$, which I don't proof here.
However how does one take the step $$\sum_{g \in G} 1 = \sum_{d|N}\sum_{g \in G, ord(g)=d} 1$$ I having trouble seeing this. Please give a detailed answer.
Thanks.
Best Answer
Every element in $G$ has some order $d$, which must divide $n$.
It follows that $\displaystyle \# G = \sum_{d|N} \#\{g\in G : \operatorname{ord}g=d\}$.
But $\displaystyle \#G = \sum_{g\in G}1$, and $\displaystyle \#\{g\in G : \operatorname{ord}g=d\} = \sum_{\substack{g\in G, \\ \operatorname{ord} g = d}} 1$.