Primitive Roots Modulo $p$

Recall: Order of an Element Modulo $p$

Let $p$ be a prime number. Recall from our previous work that the order of an integer $a$ modulo $p$ (where $\gcd(a,p) = 1$), denoted $\text{ord}_p(a)$, is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{p}$. By Fermat's Little Theorem, the order always divides $p-1$.

For example, modulo $7$: $\text{ord}_7(2) = 3$ and $\text{ord}_7(3) = 6$.

Definition and Motivation

Notice in the example above that $3$ has order $6 = 7-1$ modulo $7$. Elements with this maximal order have a special name and important properties.

Definition (Primitive Root)

Let $p$ be a prime. An integer $a$ is called a primitive root modulo $p$ if $\gcd(a, p) = 1$ and $\text{ord}_p(a) = p-1$.

In other words, $a$ is a primitive root modulo $p$ if the smallest positive power of $a$ that is congruent to $1$ modulo $p$ is $a^{p-1}$.

Why are primitive roots important?

If $a$ is a primitive root modulo $p$, then the powers $a^0, a^1, a^2, \ldots, a^{p-2}$ modulo $p$ generate all elements of $\mathbb{Z}_p^\times = \{1, 2, \ldots, p-1\}$. This means every non-zero element modulo $p$ can be expressed as a power of $a$, making primitive roots extremely useful for:

Cryptography (e.g., Diffie-Hellman key exchange)
Understanding the multiplicative structure of $\mathbb{Z}_p^\times$

There are other reasons, but we will content ourselves with this for now.

Examples:

$p = 7$: We saw that $3$ has order $6$, so $3$ is a primitive root modulo $7$. Also, $5$ is a primitive root modulo $7$ (you can verify: $5^1 = 5$, $5^2 = 4$, $5^3 = 6$, $5^4 = 2$, $5^5 = 3$, $5^6 = 1$ mod $7$).
$p = 11$: The number $2$ is a primitive root modulo $11$ because $\text{ord}_{11}(2) = 10$.
$p = 13$: The number $2$ is a primitive root modulo $13$ because $\text{ord}_{13}(2) = 12$.

Checking for Primitive Roots

Let's verify that primitive roots exist for several primes by checking computationally.

Primitive Roots Generate All Units

A key property of primitive roots is that their powers generate all non-zero elements modulo $p$.

Proposition

If $a$ is a primitive root modulo $p$, then every element of $\mathbb{Z}_p^\times = \{1, 2, \ldots, p-1\}$ can be written as $a^k \pmod{p}$ for some $k \in \{0, 1, 2, \ldots, p-2\}$.

In other words, the set $\{a^0, a^1, a^2, \ldots, a^{p-2}\}$ modulo $p$ equals the set $\{1, 2, 3, \ldots, p-1\}$ (in some order).

Let's verify this with an example:

Existence Theorem

The computational evidence above suggests that primitive roots always exist. This is indeed true, and was proven by Gauss.

Theorem (Existence of Primitive Roots)

For every prime $p$, there exists a primitive root modulo $p$.

Here, $\varphi$ is Euler's totient function. For example:

$p = 7$: There are $\varphi(6) = \varphi(2 \cdot 3) = \varphi(2)\varphi(3) = 1 \cdot 2 = 2$ primitive roots mod $7$ (namely, $3$ and $5$).
$p = 11$: There are $\varphi(10) = \varphi(2 \cdot 5) = \varphi(2)\varphi(5) = 1 \cdot 4 = 4$ primitive roots mod $11$ (namely, $2, 6, 7, 8$).

Proof Sketch: The proof uses properties of cyclic groups and polynomial equations over finite fields. The key insight is that the multiplicative group $\mathbb{Z}_p^\times$ is cyclic of order $p-1$, which guarantees the existence of elements of order $p-1$ (i.e., generators of the group). We will cover the full proof in class.

Practice Problems

Exercise 1

Show that $2$ is a primitive root modulo $13$ by computing all its powers modulo $13$.

Exercise 2

Find all primitive roots modulo $13$. Verify that there are $\varphi(12) = 4$ primitive roots.