Proof that the group of units of Z/pZ is cyclic by counting elements of each order

Proof

We count the elements of each order and compare with the totient function.

1. Let $p$ be a prime and let $G = (\Z/p\Z)^\times$ be the group of units of $\Z/p\Z$. Write $1$ for its identity $[1]$.
2. The ring $\Z/p\Z$ is a field, so each nonzero class is a unit.
3. The class $[0]$ is not a unit, because $[0][x] = [0] \neq [1]$ for each $x$, as $p \geq 2$. So $G$ is the set of the $p - 1$ nonzero classes, and $\abs{G} = p - 1$.
4. For each positive divisor $d$ of $p - 1$, let $N(d)$ be the number of elements of $G$ of order $d$.
5. Each element of the finite group $G$ has an order, and this order divides $\abs{G} = p - 1$. So $\sum_{d \mid p - 1} N(d) = p - 1$.
6. Fix a positive divisor $d$ of $p - 1$. We show that $N(d) \leq \varphi(d)$, where $\varphi$ is Euler's totient function. If $N(d) = 0$, this holds, since $\varphi(d) \geq 0$.
7. Otherwise, let $a \in G$ have order $d$. The powers $a^0, a^1, \ldots, a^{d-1}$ are $d$ distinct elements of $G$.
8. Each power satisfies $(a^k)^d = (a^d)^k = 1$. So each of them is a root of the polynomial $T^d - 1$ in $\Z/p\Z$.
9. The polynomial $T^d - 1$ is nonzero of degree $d$. Since $\Z/p\Z$ is a field, it has at most $d$ roots in $\Z/p\Z$.
10. By steps 7 to 9, the roots of $T^d - 1$ in $\Z/p\Z$ are exactly $a^0, \ldots, a^{d-1}$.
11. Let $b \in G$ have order $d$. Then $b^d = 1$, so $b$ is a root of $T^d - 1$. By step 10, $b = a^k$ for some $k$ with $0 \leq k \leq d - 1$.
12. By the order of a power, $a^k$ has order $d / \gcd(d, k)$. This equals $d$ if and only if $\gcd(d, k) = 1$.
13. The powers in step 7 are distinct, so $N(d)$ is the number of $k$ with $0 \leq k \leq d - 1$ and $\gcd(d, k) = 1$.
14. Since $\gcd(d, 0) = d = \gcd(d, d)$, we may replace $k = 0$ by $k = d$. So $N(d)$ is the number of $k$ with $1 \leq k \leq d$ and $\gcd(d, k) = 1$, which is $\varphi(d)$.
15. Thus $N(d) \leq \varphi(d)$ for every positive divisor $d$ of $p - 1$.
16. By step 5, step 15 and the sum of the totient over the divisors, $p - 1 = \sum_{d \mid p - 1} N(d) \leq \sum_{d \mid p - 1} \varphi(d) = p - 1$.
17. So the inequality in step 16 is an equality. Each term satisfies $N(d) \leq \varphi(d)$, so $N(d) = \varphi(d)$ for each divisor $d$ of $p - 1$.
18. In particular, $N(p - 1) = \varphi(p - 1)$. This is at least $1$, because $k = 1$ satisfies $1 \leq 1 \leq p - 1$ and $\gcd(p - 1, 1) = 1$.
19. So there is an element $g \in G$ of order $p - 1$. The subgroup $\langle g \rangle$ has $p - 1$ distinct elements.
20. Since $\langle g \rangle \subseteq G$ and both sets have $p - 1$ elements, $\langle g \rangle = G$.
21. Hence $G = (\Z/p\Z)^\times$ is cyclic of order $p - 1$.