---
tag: Q83MS5FFZB
kind: proof
name: Proof of the existence of primitive roots modulo a prime by counting elements of each order
msc: [11A07]
proves: 04XGKK8WQW
uses: [0KM2CJ80G7, 0SBRX5CZ5R, 0SN0MAEKYX, 0Y4B7P0GS8, 0R8YXRC9AJ, 0KJVQV3E0F, 0VVPQNVM8S, 09JXE6XMCC, 0VV04M41AN, 0HY1MXMEN9, 0S7495H4HM, 05THZKR9AN, 0B85Q41RP6]
sources:
  - url: https://kconrad.math.uconn.edu/blurbs/grouptheory/cyclicmodp.pdf
    locator: Theorem 2.6
---

## Proof

1. Let $p$ be a [[prime number|0SN0MAEKYX]]. Let $G = (\mathbb{Z}/p\mathbb{Z})^\times$ be the [[group of units|05THZKR9AN]] of $\mathbb{Z}/p\mathbb{Z}$.
2. The ring $\mathbb{Z}/p\mathbb{Z}$ [[is a field|0R8YXRC9AJ]]. 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|0SBRX5CZ5R]] $\operatorname{ord}_p(a)$ is the order of $\overline{a}$ in $G$. By the [[corollary on orders modulo p|0Y4B7P0GS8]], 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|0VV04M41AN]]. 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|0KJVQV3E0F]]. 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|0VVPQNVM8S]], 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|09JXE6XMCC]], $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|0HY1MXMEN9]], $\varphi(p) = p - 1$. So $g$ is a [[primitive root|0KM2CJ80G7]] modulo $p$.
17. The group $G$ has order $\varphi(p) = p - 1$, by the [[order of the group of units|0S7495H4HM]]. 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|0B85Q41RP6]] of order $p - 1$ generated by $\overline{g}$.

## Idea

Over a field, the polynomial $x^d - 1$ has at most $d$ roots. So once one element of order $d$ exists, all elements of order $d$ are among its powers, and there are exactly $\varphi(d)$ of them. The counts must add up to $p - 1 = \sum_{d \mid p - 1} \varphi(d)$, so no order can be missing, not even $p - 1$.