Primitive Roots

By SkytrailGroup Mathematics Editorial Team April 12, 2026

Definition

g is a primitive root mod n if its powers generate all units mod n. Exists when n=1,2,4,pᵏ, or 2pᵏ.

Examples

Example 1. Is 2 a primitive root mod 5?

Solution. 2¹=2,2²=4,2³=3,2⁴=1. Yes, order 4=φ(5).

In Depth

A primitive root modulo \(n\) is an integer \(g\) whose powers generate all units: \(\{g^1,g^2,\ldots,g^{\phi(n)}\}=\{a:\gcd(a,n)=1\}\). Primitive roots exist modulo \(n\) iff \(n=1,2,4,p^k,2p^k\) for odd prime \(p\). When they exist, the group \((\mathbb{Z}/n\mathbb{Z})^*\) is cyclic.

Finding a primitive root: test candidates \(g\) by checking \(g^{\phi(n)/q}\not\equiv1\pmod{n}\) for each prime \(q\mid\phi(n)\). The smallest primitive root modulo \(p\) is usually small (often less than \(\ln^2 p\) under GRH), but no deterministic polynomial-time algorithm is known unconditionally.

Discrete logarithm: given \(g^x\equiv h\pmod{p}\), find \(x\). This is believed to be hard (no polynomial-time classical algorithm), and its hardness underpins Diffie–Hellman key exchange and ElGamal encryption. The best algorithms (index calculus, number field sieve) run in subexponential time.

The number of primitive roots modulo \(p\) is \(\phi(p-1)\). For example, modulo 7 (\(p-1=6\), \(\phi(6)=2\)), there are 2 primitive roots: 3 and 5. The primitive roots are the generators of the cyclic group \((\mathbb{Z}/p\mathbb{Z})^*\).

Artin's conjecture: every integer \(a\neq-1\) that is not a perfect square is a primitive root for infinitely many primes. Hooley proved this conditionally under GRH. Heath-Brown proved unconditionally that at most two of any three candidates fail to be primitive roots for infinitely many primes.

Key Properties & Applications

The index (discrete logarithm) of \(a\) with respect to primitive root \(g\) modulo \(p\) is the unique \(k\in\{0,\ldots,p-2\}\) with \(g^k\equiv a\pmod{p}\). Index arithmetic: \(\text{ind}(ab)\equiv\text{ind}(a)+\text{ind}(b)\pmod{p-1}\), analogous to logarithm laws.

Baby-step giant-step computes discrete logs in \(O(\sqrt{p})\) time and space. The index calculus method achieves subexponential time \(L_p[1/2]\) for prime fields. For elliptic curves, no subexponential algorithm is known, making ECC more efficient than RSA for equivalent security.

Primitive roots modulo prime powers: if \(g\) is a primitive root mod \(p\), then either \(g\) or \(g+p\) is a primitive root mod \(p^k\) for all \(k\geq1\). This lifts primitive roots from \(\mathbb{Z}/p\mathbb{Z}\) to \(\mathbb{Z}/p^k\mathbb{Z}\) using Hensel's lemma.