A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A primitive root modulo prime p is an integer g whose multiplicative order is p−1, generating the cyclic group (ℤ/pℤ)*. Every prime has primitive roots, and they provide a basis for discrete logarithms and index calculus methods in cryptography.
From your study of groups, you know that a cyclic group is one generated by a single element — every element of the group can be written as a power of that generator. The multiplicative group (ℤ/pℤ)*, the nonzero residues modulo a prime p under multiplication, turns out to always be cyclic. A primitive root modulo p is precisely a generator of this group: an integer g such that the powers g¹, g², g³, …, gp−1 produce every nonzero residue modulo p exactly once before cycling back to 1.
To see why the order of g must be p−1, recall from your work with the Euler totient function that φ(p) = p−1, and by Fermat's Little Theorem, gp−1 ≡ 1 (mod p) for any g not divisible by p. The multiplicative order of g is the smallest positive k such that gk ≡ 1 (mod p). If g is a primitive root, this smallest k is exactly p−1, meaning g generates the full group. An element with order less than p−1 only produces a proper subgroup — it cycles back to 1 before visiting all nonzero residues.
Not every element is a primitive root. For p = 7, the element 3 is a primitive root: 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 — all six nonzero residues appear. But 2 is not: 2¹=2, 2²=4, 2³=1, so 2 has order 3 and generates only {1, 2, 4}. The number of primitive roots modulo p is φ(p−1), which can be much smaller than p−1. The theorem guaranteeing their existence follows from the fact that a polynomial of degree d over ℤ/pℤ has at most d roots, which constrains the group structure tightly enough to force cyclicity.
The practical importance of primitive roots is cryptographic. If g is a primitive root mod p, then for any nonzero h, there is a unique exponent x ∈ {1, …, p−1} such that gx ≡ h (mod p). This x is the discrete logarithm of h base g. Computing gx mod p from x is fast (using repeated squaring), but recovering x from gx mod p is believed to be computationally hard for large primes — this asymmetry underlies the Diffie-Hellman key exchange and related cryptographic protocols. Primitive roots are the foundation on which this hardness rests.