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.