Primitive Roots — Mathematics Knowledge System

Overview

An integer g is a primitive root modulo n if its powers g, g², g³, … cycle through every unit (every residue coprime to n) before repeating — that is, g has the maximum possible multiplicative order, φ(n). When a primitive root exists, the group of units mod n is 'cyclic,' generated entirely by the single element g, which turns multiplication mod n into addition of exponents (a discrete analogue of logarithms). Gauss proved that primitive roots exist exactly for n = 1, 2, 4, pᵏ, and 2pᵏ where p is an odd prime — notably, they do NOT exist mod 8, 15, or any n with two distinct odd prime factors. Primitive roots are the engine behind discrete logarithms, which underlie Diffie–Hellman key exchange and the ElGamal cryptosystem: computing gˣ mod p is fast, but recovering x from gˣ (the discrete log problem) is believed to be hard.

Intuition

Think of the units mod n arranged on a clock face with φ(n) positions. Multiplying by g rotates the clock by some fixed number of ticks. If that rotation amount is coprime to φ(n) — equivalently if g's order is the full φ(n) — repeatedly rotating visits every position before returning to the start, exactly like a gear with the right number of teeth touching every position on a circular track. A primitive root is a 'generator' rotation that never gets stuck in a short cycle.

Formal Definition

Definition

For n with a primitive root, let g be an integer coprime to n. The multiplicative order of g mod n is the smallest positive k with:

g^{k} \equiv 1 \pmod{n}

Definition of multiplicative order k = \mathrm{ord}_n(g)

g \text{ is a primitive root mod } n \iff \mathrm{ord}_n(g) = \varphi(n)

Primitive root condition

\{g^0, g^1, \ldots, g^{\varphi(n)-1}\} \equiv \{\text{all units mod } n\} \pmod n

g generates every unit mod n

Worked Examples

φ(7) = 6, so 3 must have order exactly 6. Compute successive powers of 3 mod 7.
$3^1, 3^2, 3^3, 3^4, 3^5, 3^6 \equiv 3, 2, 6, 4, 5, 1 \pmod 7$
The powers hit every nonzero residue {1,2,3,4,5,6} before returning to 1 at the 6th power.
$\{3,2,6,4,5,1\} = \{1,2,3,4,5,6\}$

Answer: Yes — 3 has order 6 = φ(7), so 3 is a primitive root mod 7.

Practice Problems

Difficulty 5/10

Is 2 a primitive root modulo 7? Compute its order.

Difficulty 6/10

How many primitive roots does 7 have, given that φ(6) = 2 counts them (a standard fact: the number of primitive roots mod p, when they exist, is φ(p−1))?

Difficulty 5/10

Explain why 8 has no primitive root, even though φ(8) = 4.

Quiz

Summary

g is a primitive root mod n if its powers generate every unit mod n, i.e. ord_n(g) = φ(n).
Primitive roots exist exactly for n = 1, 2, 4, pᵏ, 2pᵏ (Gauss); e.g. 8 and 15 have none.
When they exist, primitive roots give a discrete-logarithm structure to modular arithmetic, underlying Diffie–Hellman and ElGamal.

References

WebsiteWikipedia — Primitive root modulo n