Existence Theorem for Primitive Roots in Prime Numbers

If $ p $ is a prime number, then there exists at least one number $ g $ such that $ g $ is a primitive root modulo $ p $.

In other words, the multiplicative group $ (\mathbb{Z}/p\mathbb{Z})^* $, consisting of all integers that are invertible modulo $ p $, is cyclic.

This means that every odd prime $ p $ has at least one primitive root modulo $ p $.

This result is a special case of a more general theorem on the existence of primitive roots for prime numbers.

For every prime number $ p $, there are exactly $ \varphi(p-1) $ primitive roots modulo $ p $, where $ \varphi(p-1) $ is the Euler totient function, which counts the numbers between 1 and $ p-1 $ that are coprime with $ p-1 $. $$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) $$

So, a prime number $ p $ can have multiple primitive roots, and their count is given by $ \varphi(p-1) $.

For example, the prime number $ p = 7 $ has only 2 primitive roots because $ \varphi(6) = 2 $, whereas the prime $ p = 17 $ has 8 primitive roots since $ \varphi(16) = 8 $.

Why does a primitive root always exist modulo a prime $ p $? The multiplicative group $ (\mathbb{Z}/p\mathbb{Z})^* $ contains exactly $ \varphi(p) = p - 1 $ elements. In group theory, a cyclic group of order $ p - 1 $ must have a generator. This generator is precisely the primitive root modulo $ p $, as its powers generate all elements of the group.

Practical Examples

Let’s explore some examples to identify primitive roots for different prime numbers:

Example 1

The invertible elements modulo $ p = 3 $ are $ \{1,2\} $.

Computing the powers of 2:

$$ 2^1 \equiv 2 \pmod{3} $$

$$ 2^2 \equiv 1 \pmod{3} $$

Since $ 2 $ generates the entire set, it is a primitive root modulo 3.

Note. The number of primitive roots can also be determined using Euler’s function: $$ \phi(3-1) = 2 \cdot \left(1 - \frac{1}{2}\right) = 2 \cdot \frac{1}{2} = 1 $$ In this case, $ p=3 $ has a single primitive root, which is 2.

Example 2

The invertible elements modulo $ p = 5 $ are $ \{1,2,3,4\} $.

Checking the powers of 2:

$$ 2^1 \equiv 2 \pmod{5} $$

$$ 2^2 \equiv 4 \pmod{5} $$

$$ 2^3 = 8 \equiv 3 \pmod{5} $$

$$ 2^4 = 16 \equiv 1 \pmod{5} $$

Since 2 generates the entire group, it is a primitive root modulo $ p=5 $.

Checking the powers of 3:

$$ 3^1 \equiv 3 \pmod{5} $$

$$ 3^2 = 9 \equiv 4 \pmod{5} $$

$$ 3^3 = 27 \equiv 2 \pmod{5} $$

$$ 3^4 = 16 \equiv 1 \pmod{5} $$

Since 3 also generates the entire group, it is another primitive root modulo $ p=5 $.

Verification. According to Euler’s function, $ p = 5 $ should have exactly two primitive roots: $$ \phi(5-1) = \phi(4) = 4 \cdot \left(1 - \frac{1}{2}\right) = 4 \cdot \frac{1}{2} = 2$$

Example 3

The invertible elements modulo $ p = 7 $ are $ \{1,2,3,4,5,6\} $.

Checking the powers of 3:

$$ 3^1 \equiv 3 \pmod{7} $$

$$ 3^2 = 9 \equiv 2 \pmod{7} $$

$$ 3^3 = 27 \equiv 6 \pmod{7} $$

$$ 3^4 = 4 \pmod{7} $$

$$ 3^5 = 5 \pmod{7} $$

$$ 3^6 = 1 \pmod{7} $$

Since 3 generates all invertible numbers, it is a primitive root modulo 7.

Similarly, 5 is another primitive root.

Verification. Using Euler’s function, $ p = 7 $ is expected to have exactly two primitive roots: $$ \phi(7-1) = \phi(6) = 6 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} = 2$$

And so on.