Primitive Root — Definition, Formula & Examples

A primitive root modulo

n

is an integer

g

whose successive powers produce every integer that is coprime to

n

, before the pattern repeats. In other words,

g

is a generator of the multiplicative group of integers modulo

n

An integer $g$ is a primitive root modulo $n$ if $g$ has multiplicative order $\phi(n)$ modulo $n$ , meaning $\phi(n)$ is the smallest positive integer $k$ such that $g^k \equiv 1 \pmod{n}$ , where $\phi$ denotes Euler's totient function.

Key Formula

\text{ord}_n(g) = \phi(n)

Where:

$g$ = A candidate primitive root
$n$ = The modulus
$\text{ord}_n(g)$ = The multiplicative order of g modulo n (smallest positive k with g^k ≡ 1 mod n)
$\phi(n)$ = Euler's totient function, the count of integers from 1 to n that are coprime to n

How It Works

To check whether

g

is a primitive root modulo

n

, compute

g^1, g^2, \ldots, g^{\phi(n)}

modulo

n

and verify that

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

for any

k < \phi(n)

. A shortcut: you only need to check that

g^{\phi(n)/p} \not\equiv 1 \pmod{n}

for each prime factor

p

\phi(n)

. Primitive roots exist modulo

n

only when

n

1, 2, 4, p^k

, or

2p^k

for an odd prime

p

and

k \geq 1

. Not every modulus has a primitive root — for instance, there is none modulo 8 or 12.

Worked Example

Problem: Show that 3 is a primitive root modulo 7.

Step 1: Compute Euler's totient: since 7 is prime, φ(7) = 6. A primitive root must have order 6.

\phi(7) = 6

Step 2: The prime factors of 6 are 2 and 3. Check that 3 raised to 6/2 and 6/3 is not congruent to 1 mod 7.

3^{3} = 27 \equiv 6 \pmod{7}, \quad 3^{2} = 9 \equiv 2 \pmod{7}

Step 3: Neither result is 1, so no smaller exponent gives 1. The order of 3 is 6, which equals φ(7).

\text{ord}_7(3) = 6 = \phi(7)

Answer: 3 is a primitive root modulo 7. Its powers mod 7 cycle through all nonzero residues: 3, 2, 6, 4, 5, 1.

Why It Matters

Primitive roots underpin the Diffie-Hellman key exchange and other cryptographic protocols, where security relies on the difficulty of the discrete logarithm problem in cyclic groups. They also appear throughout number theory proofs, including the structure theorem for the multiplicative group modulo

n

Common Mistakes

Mistake: Assuming every modulus has a primitive root.

Correction: Primitive roots exist only modulo 1, 2, 4, p^k, or 2p^k (odd prime p). For example, there is no primitive root modulo 8 because every odd number squared is ≡ 1 mod 8.