Primitive Roots

Let \( n \) be a positive integer. A primitive root mod \( n \) is an integer \( g \) such that every integer relatively prime to \( n \) is congruent to a power of \( g \) mod \( n \). That is, the integer \( g \) is a primitive root (mod \(n\)) if for every number \(a\) relatively prime to \(n\) there is an integer \(z\) such that \(a \equiv \big(g^z \pmod{n}\big).\)

\( 2 \) is a primitive root mod \( 5 \), because for every number \(a\) relatively prime to 5, there is an integer \(z\) such that \(2^z \equiv a\).
All the numbers relatively prime to 5 are 1, 2, 3, 4, and each of these (mod 5) is itself \((\)for instance 2 (mod 5) = 2\():\)

• \( 2^0 = 1,\,\,\) \(1\pmod{5} = 1\), so \(2^0 \equiv 1\)
• \( 2^1 = 2,\,\,\) \(2\pmod{5} = 2\), so \(2^1 \equiv 2\)
• \( 2^3 = 8,\,\,\) \(8\pmod{5} = 3\), so \(2^3 \equiv 3\)
• \( 2^2 = 4,\,\,\) \(4\pmod{5} = 4\), so \(2^2 \equiv 4.\)

For every integer relatively prime to \( 5,\) there is a power of \(2\) that is congruent.

\( 4 \) is not a primitive root mod \( 5 \), because for every number relatively prime to 5 (again, 1, 2, 3, 4) there is not a power of \( 4 \) that is congruent. Powers of 4 (mod 5) are only congruent to 1 or 4. There is no power of 4 that is congruent to 2 or 3:

• \(4^0 = 1,\,\,\) \(1\pmod{5} = 1\)
• \(4^1 = 4,\,\,\) \(4\pmod{5} = 4\)
• \(4^2 = 16,\,\,\) \(16\pmod{5} = 1\)
• \(4^3 = 64,\,\,\) \(64 \pmod{5}= 4\)

and the pattern continues...

When primitive roots exist, it is often very convenient to use them in proofs and explicit constructions; for instance, if \( p \) is an odd prime and \( g \) is a primitive root mod \( p \), the quadratic residues mod \( p \) are precisely the even powers of the primitive root. Primitive roots are also important in cryptological applications involving the discrete log problem, most notably the Diffie-Hellman key exchange protocol.

Define

\[ {\mathbb Z}_n^* = \{ a \in {\mathbb N} \colon 1 \le a < n, \text{gcd}(a,n) = 1 \}. \]

So \( {\mathbb Z}_n^* \) has \( \phi(n) \) elements, where \( \phi \) is Euler's totient function.

A primitive root mod \(n \) is an element \( g \in {\mathbb Z}_n^*\) whose powers generate all of \( {\mathbb Z}_n^* \). That is, every element \( b \in {\mathbb Z}_n^* \) can be written as \( g^x \) mod \( n \), for some integer \( x \).

The set \( {\mathbb Z}_n^*\) has an important property: it is closed under multiplication mod \(n\). That is, if \( a,b \in {\mathbb Z}_n^* \), and \( c \) is the positive integer less than \( n \) which is congruent to \( ab\) mod \( n\), then \( c \in {\mathbb Z}_n^*\) as well. This is because \( ab\) and \(n \) have no common factor (by unique factorization), so \( c \) and \(n \) have no common factor either \((\)because if \( d|c \) and \( d|n \), then \( d|ab \) as well, because \( ab = c+nx \) for some integer \(x).\)

This property, together with other basic properties of multiplication mod \( n \), implies that \({\mathbb Z}_n^* \) is a group under multiplication.

For any element \( a \in {\mathbb Z}_n^* \), consider the sequence of its powers \( 1,a,a^2,a^3,\ldots\) mod \( n \). All of the powers of \( a \) are in the finite set \( {\mathbb Z}_n^*\), so the sequence of powers of \( a \) repeats eventually. In fact, Euler's theorem implies that it repeats with period \( \phi(n):\)

\[a^0 \equiv 1 \equiv a^{\phi(n)} \pmod n.\]

So another characterization of primitive roots in terms of this sequence is this: Primitive roots are the elements \( a \in {\mathbb Z}_n^* \) for which the sequence of powers of \( a \) has minimum period \( \phi(n) \).

The minimum period of the sequence of powers of \( a\) is called the order of \( a\). So \( a \) is a primitive root mod \( n \) if and only if the order of \( a \) is \( \phi(n)\).

\( {\mathbb Z}_9^* = \{ 1,2,4,5,7,8 \}. \)

• The powers of \( 1 \) are \( 1,1,1,\ldots \). The order of \( 1 \) is \( 1 \).
• The powers of \( 2 \) are \( 2,4,8,7,5,1, \ldots \). The order of \( 2 \) is \( 6 \).
• The powers of \( 4 \) are \( 4,7,1,\ldots \). The order of \( 4 \) is \( 3 \).
• The powers of \( 5 \) are \( 5,7,8,4,2,1, \ldots \). The order of \( 5 \) is \( 6 \).
• The powers of \( 7 \) are \( 7,4,1, \ldots \). The order of \( 7 \) is \( 3 \).
• The powers of \( 8 \) are \( 8,1, \ldots \). The order of \( 8 \) is \( 2 \).

So the primitive roots mod \( 9 \) are \( 2 \) and \( 5 \).

Primitive roots do not necessarily exist mod \( n \) for any \( n \). Here is a complete classification:

There are primitive roots mod \( n\) if and only if \(n = 1,2,4,p^k,\) or \( 2p^k,\) where \( p \) is an odd prime.

The proof of the theorem (part of which is presented below) is essentially non-constructive: that is, it does not give an effective way to find a primitive root when it exists. Once one primitive root \( g \) has been found, the others are easy to construct: simply take the powers \( g^a,\) where \( a\) is relatively prime to \( \phi(n)\). But finding a primitive root efficiently is a difficult computational problem in general.

There are some special cases when it is easier to find them. Here is an example:

Suppose \( p \) is a prime such that \( 2p+1 \) is also prime. (Such \( p \) are called Sophie Germain primes.) Show that if \( p \equiv 1 \) mod \(4\), then \(2 \) is a primitive root mod \( 2p+1 \).

---

The point is that the list of possible orders of elements of \( {\mathbb Z}_{2p+1}^* \) is very short: the order of \( 2 \) divides \( \phi(2p+1) = 2p \), so it is either \( 1,2,p,\) or \(2p\). It can't be \( 1 \) or \( 2 \), so we only need to rule out \( p \). But \( 2^p \equiv \left( \frac2{2p+1} \right) \) mod \( 2p+1 \), where \( \left( \frac2{2p+1} \right) \) is the Legendre symbol; this is by Euler's criterion. But by the second supplement to quadratic reciprocity, \( \left( \frac2{2p+1} \right) =-1\) because \( 2p+1 \equiv 3 \) mod \( 8 \).

So the only remaining possibility is that the order of \( 2 \) mod \( 2p+1 \) is \( 2p \). \(_\square \)

For instance, this shows that \( 2 \) is a primitive root mod \( 83 \).

When there is a primitive root \( g\) mod \( n \), the elements of \( {\mathbb Z}_n^* \) can be written as \( 1, g, g^2, \ldots, g^{\phi(n)-1} \). Multiplying two elements corresponds to adding their exponents mod \( \phi(n). \) That is, the multiplicative arithmetic in \( {\mathbb Z}_n^* \) reduces to additive arithmetic in \( {\mathbb Z}_{\phi(n)} \).

Let \( k \) be an integer and \( p \) an odd prime number. How many nonzero \(k^\text{th}\) powers are there mod \( p?\)

---

The question certainly depends on the relationship between \( k\) and \( p\). When \( k=2,\) the answer is \( \frac{p-1}2 \) (see quadratic residues), but when \( k = p-1, \) the answer is \( 1 \) (by Fermat's little theorem).

As an illustration, take \( k = 9, p = 13 \). Then it's easy to check that \( g=2 \) is a primitive root mod \( p\). The ninth powers mod \( p \) are \( 2^0, 2^9, 2^{18}, 2^{27}, \ldots \), but we can consider the exponents mod \( 12 \) because \( 2^{12} \equiv 1 \). So we get

\[2^0, 2^9, 2^6, 2^3, 2^0, \ldots,\]

so there are four \(9^\text{th}\) powers mod \( 13 \). The exponents are multiples of \( 3\), which is gcd\((9,13-1)\). There are \(\frac{13-1}3 = 4\) of these.

In general, since every nonzero element of \( {\mathbb Z}_p \) can be written as \( g^a \) mod \( p \) for some integer \( x \), the equation \( x^k \equiv y \) mod \( p \) can be rewritten \( (g^a)^k \equiv g^b, \) or \( g^{ak-b} \equiv 1 \) mod \( p \). Because \( g \) is a primitive root, this happens if and only if \( (p-1)|(ak-b) \), so \( ak \equiv b \) mod \( p -1 \).

So the question becomes, "As \( a \) ranges over \( {\mathbb Z}_{p-1} \), how many values can \( ak \) mod \( p-1 \) take on?" In fact, the extended Euclidean algorithm implies that \( \big\{ak+(p-1)c : k, c \in {\mathbb Z}\big\} \) is the set of multiples of gcd\((k,p-1)\). There are exactly

\[\frac{p-1}{\text{gcd}(k,p-1)}\]

such values, so this is the answer. \(_\square\)

Here is another problem where it can help to write the elements of \( {\mathbb Z}_p^* \) as powers of a primitive root.

One half of this theorem is not hard to prove: Suppose \( n = ab, \) where \( a\) and \( b\) are relatively prime and \( \ge 3 \). Suppose \( x \) is relatively prime to \( ab \). Then since \( x^{\phi(a)} \equiv 1 \) mod \( a \) and \( x^{\phi(b)} \equiv 1 \) mod \( b \), it follows that \(x^{\text{lcm}\big(\phi(a),\phi(b)\big)} \equiv 1 \) mod \( ab \).

But \( \phi(a) \) and \( \phi(b) \) are both even, so their LCM is strictly less than their product. So the order of \( x \) is strictly less than \( \phi(a)\phi(b) = \phi(ab) \). So there is no primitive root mod \( ab \).

The only \( n \) that cannot be written in this way are \( 1,2,4,p^k,2p^k,\) and higher powers of \( 2 \). But for any odd \( x \),

\[x^{2^{k-2}} \equiv 1 \pmod{2^k} \ (k \ge 3),\]

which can be proved by the LTE lemma (or by induction). Since \(\phi(2^k) = 2^{k-1}\), there is no primitive root mod \( 2^k \) for \( k \ge 3 \).

Some of the proof of the other direction can be found in the wiki on orders.