Exercise 9.1.10

Proof. More generally, we prove that a cyclic group $G$ of order $n$ has $\varphi (d)$ elements of order $d$ if $d\mid n$ (0 otherwise !).

Let $\zeta$ a generator of $G$: $G=⟨\zeta ⟩$.

Every element $\alpha \in G$ is of the form ${\zeta }^k,0\le k<n$. Recall (see Exercise 3), that

If $d\nmid n$, there is no element of order $d$ by Lagrange’s Theorem, and if $d\mid n$,

Indeed, if $\delta =\frac{n}{d}=n\wedge k$, then there exists $\lambda ,\mu$, with $\lambda \wedge \mu =1$, such that

$\mu =n∕\delta =d$, so $\lambda \wedge d=1$. As $0\le k<n$, $0\le \lambda <n∕\delta =d$.

Conversely, if $k=\lambda \frac{n}{d},\lambda \wedge d=1$, then

The elements of order $d$ in $G$ are thus the elements ${\zeta }^k$, where

The mapping $\phi :\{\lambda \in \mathbb{Z}|0\le \lambda <d,\lambda \wedge d=1\}\to \{\alpha \in G|o(\alpha )=d\}$ defined by $\phi (\lambda )={\zeta }^{\lambda \frac{n}{d}}$ is so a bijection.

Hence there exist exactly $\varphi (d)$ elements of order $d$ in $G$, for every factor $d$ of $n=|G|$. In particular, there exist $\varphi (n)$ elements of order $n=|G|$ in $G$, hence $\varphi (n)$ generators in a cyclic group $G$ of order $n$. □