Proof of the existence of primitive roots modulo a prime by counting elements of each order

Proof

1. Let $p$ be a prime number. Let $G = (\mathbb{Z}/p\mathbb{Z})^\times$ be the group of units of $\mathbb{Z}/p\mathbb{Z}$.
2. The ring $\mathbb{Z}/p\mathbb{Z}$ is a field. So $G$ consists of the $p - 1$ nonzero classes $\overline{1}, \dots, \overline{p-1}$.
3. For $a \in \set{1, \dots, p-1}$, the multiplicative order $\operatorname{ord}_p(a)$ is the order of $\overline{a}$ in $G$. By the corollary on orders modulo p, it divides $p - 1$.
4. For each positive divisor $d$ of $p - 1$, let $\psi(d)$ be the number of $a \in \set{1, \dots, p-1}$ with $\operatorname{ord}_p(a) = d$.
5. Each of the $p - 1$ elements is counted for exactly one $d$, by step 3. So $\sum_{d \mid p-1} \psi(d) = p - 1$.
6. Claim: $\psi(d) \le \varphi(d)$ for each $d \mid p - 1$, where $\varphi$ is Euler's totient function. If $\psi(d) = 0$, this holds. So let $a$ be an element of order $d$.
7. The classes $\overline{a}^0, \overline{a}^1, \dots, \overline{a}^{d-1}$ are distinct. Indeed, if $\overline{a}^i = \overline{a}^j$ with $0 \le i < j < d$, then $\overline{a}^{j-i} = \overline{1}$ with $0 < j - i < d$. This contradicts $\operatorname{ord}_p(a) = d$.
8. Each $\overline{a}^i$ is a root of $x^d - 1$ in $\mathbb{Z}/p\mathbb{Z}$, because $(\overline{a}^i)^d = (\overline{a}^d)^i = \overline{1}$.
9. The polynomial $x^d - 1$ has degree $d$ over a field. So it has at most $d$ roots. By steps 7 and 8, its roots are exactly $\overline{a}^0, \dots, \overline{a}^{d-1}$.
10. Let $b$ have order $d$. Then $\overline{b}$ is a root of $x^d - 1$. By step 9, $\overline{b} = \overline{a}^i$ for some $i$ with $0 \le i < d$.
11. By the formula for the order of a power, the order of $\overline{a}^i$ is $d / \gcd(d, i)$. This equals $d$ exactly when $\gcd(d, i) = 1$.
12. So the elements of order $d$ are among the $\overline{a}^i$ with $0 \le i < d$ and $\gcd(i, d) = 1$. For $d = 1$ this is $i = 0$; for $d > 1$ it is $1 \le i < d$. In both cases there are $\varphi(d)$ such $i$. This proves the claim.
13. By steps 5 and 6 and the sum of the totient over the divisors, $p - 1 = \sum_{d \mid p-1} \psi(d) \le \sum_{d \mid p-1} \varphi(d) = p - 1$.
14. So equality holds in each term: $\psi(d) = \varphi(d)$ for every $d \mid p - 1$.
15. In particular $\psi(p - 1) = \varphi(p - 1) \ge 1$, since $1$ is coprime to $p - 1$. So some $g$ has $\operatorname{ord}_p(g) = p - 1$.
16. By the totient of a prime, $\varphi(p) = p - 1$. So $g$ is a primitive root modulo $p$.
17. The group $G$ has order $\varphi(p) = p - 1$, by the order of the group of units. By step 7 with $d = p - 1$, the powers of $\overline{g}$ give $p - 1$ distinct elements of $G$.
18. So the powers of $\overline{g}$ fill $G$, and $G$ is a cyclic group of order $p - 1$ generated by $\overline{g}$.