Primitive Root Modulo n

Given two positive integers $ n $ and $ r $ that are coprime, meaning $ \gcd(r, n) = 1 $, we say that $ r $ is a primitive root modulo $ n $ if the cyclic subgroup $ G(n, r) $ generated by $ r $ has the largest possible order, which is $ \varphi(n) $. Here, $ \varphi(n) $ is Euler’s totient function, which counts the number of integers less than $ n $ that are coprime to $ n $.

In simpler terms, $ r $ is a primitive root modulo $ n $ if its powers, taken modulo $ n $, produce all invertible elements in $ \mathbb{Z}_n $, meaning it generates the entire group $ U(\mathbb{Z}_n) $.

If $ r $ is a primitive root modulo $ n $, it is also called a generator of $ U(\mathbb{Z}_n) $.

A Practical Example
Additional Notes

A Practical Example

Let’s take $ n = 4 $ as an example.

The numbers that are coprime with $ 4 $ are $ \{1,3\} $, which form a group under multiplication modulo $ 4 $.

\[ U(\mathbb{Z}_4) = \{1, 3\} \]

A primitive root modulo $ n $ is an element that generates the group $ U(\mathbb{Z}_n) $, meaning that its powers cover all elements in the group.

Euler’s totient function for $ n = 4 $ counts how many numbers from 1 to 4 are coprime with $ n $, which in this case are 1 and 3.

$$ \varphi(4) = 2 $$

Now, let’s check if $ 3 $ is a primitive root:

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

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

Since the powers of $ 3 $ generate all elements in $ U(\mathbb{Z}_4) = \{1, 3\} $, $ 3 $ is a primitive root modulo $ 4 $.

The order of the cyclic subgroup generated by $ 3 $ is 2, which matches $ \varphi(4) = 2 $, the number of elements coprime with $ 4 $.

Note. In a cyclic group, the order of an element $ x $ is the smallest integer $ k $ such that $ x^k \equiv 1 \pmod{n} $. In this case, $ k = 2 $ because $$ 3^2 \equiv 9 \equiv 1 \pmod{4} $$.

Example 2

Now, let’s consider $ n = 8 $.

The set of numbers coprime with $ 8 $ forms the group $ U(\mathbb{Z}_8) = \{1,3,5,7\} $.

In this case, the group is not cyclic, meaning no single number generates the entire group through its powers.

Element 1 always has order 1: $$ 1^1 = 1 \equiv 1 \pmod{8} $$
Element 3 has order 2: $$ 3^1 \equiv 3 \pmod{8} $$ $$ 3^2 = 9 \equiv 1 \pmod{8} $$
Element 5 has order 2: $$ 5^1 \equiv 5 \pmod{8} $$ $$ 5^2 = 25 \equiv 1 \pmod{8} $$
Element 7 has order 2: $$ 7^1 \equiv 7 \pmod{8} $$ $$ 7^2 = 49 \equiv 1 \pmod{8} $$

Since the maximum order here is 2 (and not $ \varphi(8) = 4 $), there are no primitive roots modulo 8.

Additional Notes

Some key insights about primitive roots modulo $ n $.

If a primitive root exists, there are exactly $ \varphi(\varphi(n)) $ of them.
If a primitive root exists modulo $ n $, then there are precisely $ \varphi(\varphi(n)) $ of them, and they can be found by taking powers of a known primitive root. Once one primitive root is identified, the others can be determined by computing the powers $ g^m \pmod{n} $, where $ m $ is coprime to $ \varphi(n) $.

Example. For $ n = 7 $, there are $ \varphi(7) = 6 $ numbers coprime with $ n $. The number $ 3 $ is a primitive root modulo $ 7 $ because: $$ 3^1 \equiv 3 \pmod{7} $$ $$ 3^2 = 9 \equiv 2 \pmod{7} $$ $$ 3^3 = 27 \equiv 6 \pmod{7} $$ $$ 3^4 = 81 \equiv 4 \pmod{7} $$ $$ 3^5 = 3^2 \cdot 3^3 = 2 \cdot 6 = 12 \equiv 5 \pmod{7} $$ $$ 3^6 = 3^3 \cdot 3^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$ Since $ 3 $ generates all of $ U(\mathbb{Z}_7) $, it is a primitive root. There are exactly $ \varphi(\varphi(7)) = \varphi(6) = 2 $ primitive roots modulo $ 7 $, which can be found by selecting exponents $ m $ such that $ \gcd(m,6) = 1 $. In this case, they are $ 3^1 = 3 \pmod{7} $ and $ 3^5 = 5 \pmod{7} $.
If $ n $ is prime, there is always at least one primitive root
Whenever $ n $ is prime, there is always at least one primitive root modulo $ n $. This means that there exists at least one integer smaller than $ n $ whose successive modular powers generate all invertible elements of $ \mathbb{Z}_n $.
Some composite numbers do not have primitive roots
This happens when the group $ U(\mathbb{Z}_n) $ is not cyclic, meaning no element has order $ \varphi(n) $.

Criterion for the Existence of Primitive Roots
A positive integer $ n $ has at least one primitive root if and only if it falls into one of the following categories:

$ n = 2 $
$ n = 4 $
$ n = p^h $, where $ p $ is an odd prime and $ h $ is a positive integer
$ n = 2p^h $, where $ p $ is an odd prime and $ h $ is a positive integer

Example. This theorem identifies all numbers $ n $ that have at least one primitive root modulo $ n $. For example, if $ n $ is a power of an odd prime—falling under the $ p^h $ category (e.g., $ 3, 9, 27, 5, 25, 125, \dots $)—then it has at least one primitive root. Similarly, if $ n $ is twice a power of an odd prime, meaning $ n = 2p^h $ (e.g., $ 6, 10, 18, 50, 250, \dots $), then it also has at least one primitive root. However, not all integers have primitive roots. For instance, numbers like $ n = 6, 8, 12, 15 $ do not, as they do not fit any of the conditions outlined in the theorem.

n	Has at least one primitive root?
2	✅ Yes
3	✅ Yes (case $ p^h = 3^1 $)
4	✅ Yes
5	✅ Yes (case $ p^h = 5^1 $)
6	❌ No
7	✅ Yes (case $ p^h = 7^1 $)
8	❌ No
9	✅ Yes (case $ p^h = 3^2 $)
10	✅ Yes (case $ 2p^h = 2 \cdot 5^1 $)
11	✅ Yes (case $ p^h = 11^1 $)
12	❌ No
13	✅ Yes (case $ p^h = 13^1 $)
14	✅ Yes (case $ 2p^h = 2 \cdot 7^1 $)
15	❌ No

Primitive Roots Modulo $ p^2 $
If $ p $ is an odd prime and $ r $ is a primitive root modulo $ p $ but not modulo $ p^2 $, then the number $ r + p $ serves as a primitive root modulo $ p^2 $.
In other words, given a primitive root $ r $ modulo $ p $, we can easily find a primitive root modulo $ p^2 $ by simply adding $ p $ to $ r $. This new root remains valid for both $ p $ and $ p^2 $. Not only does this confirm that primitive roots exist modulo $ p^2 $, but it also guarantees that at least one of them works for both $ p $ and $ p^2 $.

Example
If $ r = 2 $ is a primitive root modulo $ p = 3 $, we can construct a primitive root modulo $ p^2 = 9 $ as follows: \[ r + p = 2 + 3 = 5 \] Verifying the calculations, we see that $ 5 $ is indeed a primitive root modulo $ 9 $.
Theorem on the Propagation of Primitive Roots to Prime Powers
If $ r $ is a primitive root modulo $ p $ and modulo $ p^2 $, then it remains a primitive root for all higher powers $ p^h $ with $ h \geq 2 $. In other words, once $ r $ reaches the maximum possible order modulo $ p^2 $, it retains this order for all higher powers of $ p $. This means there's no need to search for new primitive roots for each $ p^h $, the same root works for all powers.

Example. Consider an odd prime $ p = 3 $. A primitive root modulo $ 3 $ is $ r = 2 $, which is also a primitive root modulo $ 3^2 = 9 $. By this theorem, $ r = 2 $ remains a primitive root for all higher powers, such as modulo $ 3^3 $, $ 3^4 $, $ 3^5 $, and beyond.

And so on.

n	Has at least one primitive root?
2	✅ Yes
3	✅ Yes (case \( p^h = 3^1 \))
4	✅ Yes
5	✅ Yes (case \( p^h = 5^1 \))
6	❌ No
7	✅ Yes (case \( p^h = 7^1 \))
8	❌ No
9	✅ Yes (case \( p^h = 3^2 \))
10	✅ Yes (case \( 2p^h = 2 \cdot 5^1 \))
11	✅ Yes (case \( p^h = 11^1 \))
12	❌ No
13	✅ Yes (case \( p^h = 13^1 \))
14	✅ Yes (case \( 2p^h = 2 \cdot 7^1 \))
15	❌ No