Proof of the primitive root theorem

Proof

We prove existence for $n = 2, 4, p^k, 2p^k$, and then nonexistence for every other $n \ge 2$. Throughout, $\varphi$ is Euler's totient function and $\operatorname{ord}_n(x)$ is the multiplicative order of an integer $x$ coprime to $n$. A primitive root modulo $n$ is such an $x$ with $\operatorname{ord}_n(x) = \varphi(n)$.

1. Let $e = \operatorname{ord}_n(x)$ and let $m \ge 0$ with $x^m \equiv 1 \pmod n$. By the division algorithm, $m = qe + r$ with $q \ge 0$ and $0 \le r < e$. Then $1 \equiv x^m = (x^e)^q x^r \equiv x^r \pmod n$, using powers of congruences. Minimality of $e$ forces $r = 0$. So $e \mid m$.
2. By Euler's theorem, $x^{\varphi(n)} \equiv 1 \pmod n$. So $\operatorname{ord}_n(x) \mid \varphi(n)$ by step 1, and in particular $\operatorname{ord}_n(x) \le \varphi(n)$.

Existence.

3. For $n = 2$: $\varphi(2) = 1$, and $x = 1$ has order $1$. For $n = 4$: $\varphi(4) = 2$, and $3 \not\equiv 1$ while $3^2 = 9 \equiv 1 \pmod 4$. So $3$ has order $2$.
4. Let $p$ be an odd prime and $k \ge 1$. By the existence of primitive roots modulo a prime, there is $g$ with $\operatorname{ord}_p(g) = p - 1$. Then $p \nmid g$.
5. Suppose $g^{p-1} \equiv 1 \pmod{p^2}$. By the binomial theorem, $(g + p)^{p-1} = g^{p-1} + (p-1) g^{p-2} p + p^2 s$ for an integer $s$.
6. So $(g+p)^{p-1} \equiv 1 + p^2 g^{p-2} - p g^{p-2} \equiv 1 - p g^{p-2} \pmod{p^2}$. By Euclid's lemma, $p \nmid g^{p-2}$, so $p^2 \nmid p g^{p-2}$. Hence $(g+p)^{p-1} \not\equiv 1 \pmod{p^2}$.
7. Also $g + p \equiv g \pmod p$, so all powers agree modulo $p$ and $\operatorname{ord}_p(g + p) = p - 1$. Replacing $g$ by $g + p$ if needed, we may assume $g^{p-1} \not\equiv 1 \pmod{p^2}$.
8. By Fermat's little theorem, $g^{p-1} \equiv 1 \pmod p$. So $g^{p-1} = 1 + p t_1$ with $t_1$ an integer, and $p \nmid t_1$ by step 7.
9. For $1 \le i \le p - 1$, we have $p \mid \binom{p}{i}$. Indeed, $\binom{p}{i} \, i! \, (p-i)! = p!$ by the factorial formula. Here $p \mid p!$, but $p \nmid i! \, (p-i)!$ by Euclid's lemma, since all factors are less than $p$. So Euclid's lemma gives $p \mid \binom{p}{i}$.
10. Claim: for each $j \ge 1$, $g^{p^{j-1}(p-1)} = 1 + p^j t_j$ with $t_j$ an integer and $p \nmid t_j$. We argue by induction on $j$. Step 8 is the case $j = 1$.
11. Assume the claim for $j$ and write $t = t_j$. By the binomial theorem, $g^{p^j (p-1)} = (1 + p^j t)^p = 1 + p^{j+1} t + \sum_{i=2}^{p-1} \binom{p}{i} p^{ij} t^i + p^{pj} t^p$.
12. For $2 \le i \le p - 1$, the term is divisible by $p \cdot p^{2j}$ by step 9, and $2j + 1 \ge j + 2$. The last term is divisible by $p^{pj}$, and $pj \ge 3j \ge j + 2$.
13. So $g^{p^j(p-1)} = 1 + p^{j+1}(t + p u)$ for an integer $u$. Set $t_{j+1} = t + pu$. Since $p \nmid t$, also $p \nmid t_{j+1}$. This proves the claim.
14. Now let $e = \operatorname{ord}_{p^k}(g)$, which is defined since $p \nmid g$. By step 2 and the totient of a prime power, $e \mid p^{k-1}(p-1)$.
15. From $g^e \equiv 1 \pmod{p^k}$ we get $g^e \equiv 1 \pmod p$. By step 1 with modulus $p$, $(p - 1) \mid e$. Write $e = (p-1) c$. Then $c \mid p^{k-1}$.
16. By the fundamental theorem of arithmetic, $c = p^i$ with $0 \le i \le k - 1$.
17. Suppose $i \le k - 2$; this needs $k \ge 2$. Then $e \mid p^{k-2}(p-1)$, so $g^{p^{k-2}(p-1)} \equiv 1 \pmod{p^k}$.
18. But step 10 with $j = k - 1$ gives $g^{p^{k-2}(p-1)} = 1 + p^{k-1} t_{k-1}$ with $p \nmid t_{k-1}$. So $p^k$ does not divide $g^{p^{k-2}(p-1)} - 1$, a contradiction.
19. Hence $i = k - 1$ and $e = p^{k-1}(p-1) = \varphi(p^k)$. So $g$ is a primitive root modulo $p^k$.
20. Let $n = 2p^k$. Put $h = g$ if $g$ is odd, and $h = g + p^k$ if $g$ is even. Since $p^k$ is odd, $h$ is odd.
21. As $h \equiv g \pmod{p^k}$, all powers of $h$ and $g$ agree modulo $p^k$. So $\operatorname{ord}_{p^k}(h) = \varphi(p^k)$.
22. A prime that divides both $h$ and $2p^k$ is $2$ or $p$. But $h$ is odd and $p \nmid h$. So $h$ is coprime to $2p^k$.
23. By the multiplicativity of the totient and the totient of a prime, $\varphi(2p^k) = \varphi(2)\varphi(p^k) = \varphi(p^k)$.
24. Let $e = \operatorname{ord}_{2p^k}(h)$. From $h^e \equiv 1 \pmod{p^k}$ and step 1, $\varphi(p^k) \mid e$, so $e \ge \varphi(p^k)$. By step 2, $e \le \varphi(2p^k) = \varphi(p^k)$. So $h$ is a primitive root modulo $2p^k$.

Nonexistence.

25. Let $k \ge 3$. Claim: every odd $a$ satisfies $a^{2^{k-2}} \equiv 1 \pmod{2^k}$. We argue by induction on $k$.
26. For $k = 3$, write $a = 2b + 1$. Then $a^2 = 4b(b+1) + 1$. One of $b$ and $b + 1$ is even, so $8 \mid a^2 - 1$.
27. If $a^{2^{k-2}} = 1 + 2^k s$ with $s$ an integer, then $a^{2^{k-1}} = 1 + 2^{k+1} s + 2^{2k} s^2$. Since $2k \ge k + 1$, this is $1$ modulo $2^{k+1}$. This proves the claim.
28. The integers coprime to $2^k$ are the odd ones. By step 27 and step 1, each has order at most $2^{k-2}$. This is less than $2^{k-1} = \varphi(2^k)$, so there is no primitive root modulo $2^k$.
29. Claim: $\varphi(c)$ is even for every integer $c \ge 3$. Let $S$ be the set of $x$ with $1 \le x \le c$ and $\gcd(x, c) = 1$. Then $c \notin S$.
30. For $x \in S$, we have $1 \le c - x \le c - 1$, and $\gcd(c - x, c) = \gcd(x, c) = 1$, since $x$ and $c - x$ have the same common divisors with $c$. So $x \mapsto c - x$ maps $S$ to itself, and applying it twice gives $x$.
31. If $x = c - x$, then $c = 2x$ and $\gcd(x, c) = x$, so $x = 1$ and $c = 2$. This is excluded. So $S$ splits into pairs $\set{x, c - x}$, and $\varphi(c) = \abs{S}$ is even.
32. Claim: if $n = ab$ with $a, b \ge 3$ coprime, then there is no primitive root modulo $n$. Let $x$ be coprime to $n$. Then $x$ is coprime to $a$ and to $b$.
33. Let $L = \varphi(a)\varphi(b)/2$. It is an integer, and $L = \varphi(a) \cdot (\varphi(b)/2) = \varphi(b) \cdot (\varphi(a)/2)$ with integer factors, by step 31.
34. By Euler's theorem, $x^L = (x^{\varphi(a)})^{\varphi(b)/2} \equiv 1 \pmod a$ and $x^L = (x^{\varphi(b)})^{\varphi(a)/2} \equiv 1 \pmod b$.
35. Both $x^L$ and $1$ are congruent to $1$ modulo $a$ and modulo $b$. By the Chinese remainder theorem, $x^L \equiv 1 \pmod{ab}$.
36. So $\operatorname{ord}_n(x) \le L < \varphi(a)\varphi(b) = \varphi(n)$, by multiplicativity of the totient. This proves the claim.
37. Now let $n \ge 2$ not be of the form $2, 4, p^k, 2p^k$. Write $n = 2^j m$ with $j \ge 0$ and $m$ odd. If $m = 1$, then $n = 2^j$ with $j \ge 3$, and step 28 applies.
38. If $m$ has two distinct prime factors, let $q$ be one of them and $q^f$ the exact power of $q$ in $m$. Then $m = q^f m'$ with $q \nmid m'$. The other prime factor of $m$ divides $m'$, so $m'$ is odd and $m' \ge 3$. Take $a = q^f$ and $b = 2^j m'$.
39. Then $a, b \ge 3$, and $q \nmid b$ by Euclid's lemma. So $a$ and $b$ are coprime, and step 36 applies.
40. If $m = q^f$ for one odd prime $q$, then $j \ne 0$ and $j \ne 1$ by assumption. So $j \ge 2$. Take $a = 2^j \ge 4$ and $b = q^f \ge 3$, which are coprime. Step 36 applies.
41. So a primitive root modulo $n$ exists if and only if $n \in \set{2, 4, p^k, 2p^k}$.