Some numbers have the largest order possible. Mod 7, the powers of 3 are $3, 2, 6, 4, 5, 1$: every nonzero residue appears once. Such a number turns multiplication mod $p$ into addition of exponents, and that is the foundation of discrete logarithms and Diffie–Hellman.
Definition. $g$ is a primitive root mod $n$ when $\operatorname{ord}_n(g) = \varphi(n)$. Mod a prime $p$ this means order $p - 1$, so $g, g^{2}, \dots, g^{p-1}$ are all the nonzero residues, each exactly once.
Theorem (Gauss). Every prime $p$ has a primitive root; in fact it has exactly $\varphi(p - 1)$ of them. (Among other moduli, only $1, 2, 4, p^{k}$ and $2p^{k}$ have primitive roots; mod 8, for instance, every unit has order 1 or 2.)
The test. Let $q_1, \dots, q_s$ be the primes dividing $p - 1$. Then $g$ is a primitive root mod $p$ exactly when $$g^{(p-1)/q_i} \not\equiv 1 \pmod{p} \quad\text{for every } i.$$
Why it works
Worked example: A primitive root
- $p - 1 = 10 = 2 \cdot 5$, so check $2^{10/2} = 2^{5}$ and $2^{10/5} = 2^{2}$.
- $2^{5} = 32 \equiv 10$ and $2^{2} = 4$. Neither is 1.
Answer: Yes.
Worked example: Not a primitive root
- $p - 1 = 12 = 2^{2} \cdot 3$, so check $3^{6}$ and $3^{4}$.
- $3^{3} = 27 \equiv 1$, so $3^{6} \equiv 1$. That settles it: the order of 3 is only 3.
Answer: No.
Worked example: The smallest one
- $22 = 2 \cdot 11$, so check $g^{11}$ and $g^{2}$.
- $g = 2$: $2^{11} = 2048 = 89 \cdot 23 + 1$, so no. $g = 3$: $3^{11} \equiv 1$ too, so no. $g = 4 = 2^{2}$: $4^{11} = (2^{11})^{2} \equiv 1$, no.
- $g = 5$: $5^{2} = 25 \equiv 2$ and $5^{11} \equiv 22 \equiv -1$. Neither is 1, so 5 is a primitive root.
Answer: $5$.
Common mistake
Key idea