Simple question regarding number of elements in cyclic subgroups

Question

Let $G$ be a cyclic group with $N$ elements. Then it follows that

$$N=\sum_{d|N} \sum_{g\in G,\text{ord}(g)=d} 1.$$

I simply can not understand this equality. I know that for every divisor $d|N$ there is a unique subgroup in $G$ of order $d$ with $\phi(d)$ elements. But how come that when you add all these together you end up with the number of elements in the group $G$.

Answer 1

What you wrote is just the well-known formula

$$\sum_{d\mid n}\varphi(d)=n\ldots !$$

The basis of this, and in fact of your formula, is that there is one single, unique subgroup of order every divisor of $\;n\;$ : this is one characterization of finite cyclic groups.

Answer 2

Define $G_d = \{g \in G : \operatorname{ord}(g) = d\}$. By Lagrange's theorem, $$ G = \bigcup_{d|N}G_d. $$

Furthermore, the sets $\{G_d\}_{d|N}$ are disjoint: If $k \ne \ell$ then $G_k \cap G_\ell = \emptyset$, since we cannot have an element of order $k$ and $\ell$ at the same time. It follows that $$ N = \sum_{d|N} |G_d| = \sum_{d|N} \sum_{g \in G, \operatorname{ord}(g) = d} 1. $$