Primitive Roots and Cyclic Groups Mod p

Core Idea

A primitive root mod p is an integer g whose powers g¹, g², ..., g^p-1 exhaust all nonzero residues mod p. Equivalently, g has order p-1. Every prime p has primitive roots, making (Z/pZ)* cyclic of order p-1.

Explainer

Fermat's Little Theorem tells you that every nonzero residue a mod p satisfies a^p-1 ≡ 1 (mod p), but it doesn't reveal the *smallest* exponent with this property. The order of a mod p is the smallest positive integer d such that a^d ≡ 1 (mod p). Because a^p-1 ≡ 1, the order d must divide p-1. Some elements have small order — for instance, 1 always has order 1, and if p-1 is even then −1 has order 2 — but the question is whether any element achieves the maximum possible order p-1. Such an element is a primitive root mod p.

When g is a primitive root, the p-1 powers g, g², ..., g^p-1 are all distinct (if gⁱ ≡ g^j with i < j, then g^j-i ≡ 1, contradicting the minimality of p-1). Since there are exactly p-1 nonzero residues mod p and the powers produce p-1 distinct values, every nonzero residue appears exactly once. The group (Z/pZ)* is cyclic: it is generated by a single element, exactly as the integers mod n under addition are generated by 1. This is a structural fact about primes — non-prime moduli don't always have primitive roots.

The existence of primitive roots mod every prime is a theorem, not obvious. The count is given by Euler's totient function: exactly φ(p-1) of the p-1 nonzero residues are primitive roots. For p = 7, p-1 = 6 and φ(6) = 2, so exactly two primitive roots exist — they are 3 and 5. Verify: 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) — all six residues appear. Once you find one primitive root g, the others are exactly the powers g^k where gcd(k, p-1) = 1.

Primitive roots are the key to defining discrete logarithms: if g is a primitive root mod p and a is any nonzero residue, there is a unique x in {0, 1, ..., p-2} with g^x ≡ a (mod p). This x is the discrete logarithm of a to base g, written log_g(a). Computing discrete logarithms — given g, p, and a, find x — is believed to be computationally hard for large primes. The security of Diffie-Hellman key exchange and ElGamal encryption rests on this hardness. The cyclic structure you've built here is precisely the algebraic foundation these cryptographic protocols exploit.