# Primitive roots of prime moduli

In this post we show that if $m$ is prime, then there exists a primitive root modulo $m$. It follows that there exist $\phi(m-1)$ primitive roots modulo $m$ where $\phi$ is Euler’s phi function.

For a basic discussion of the notion of primitive roots, see Defining Primitive Root. A basic discussion of the phi function is found in the post Euler’s phi function, part 1 and in the post Euler’s phi function, part 2.

In modular arithmetic, not all moduli have primitive roots. For example, for the modulus $m=8$, the least residues that are relatively prime are $a=1,3,5,7$. Thus $\phi(8)=4$. For each one of these values of $a$, $a^2 \equiv 1 \ (\text{mod} \ 8)$. Thus every one of them has order $2 < \phi(8)$. Thus there are no primitive roots modulo $m=8$. We prove the following results.

Theorem 1

Let $p$ be a prime number. Then there exists a primitive root modulo $p$.

$\text{ }$

Theorem 2

Let $p$ be a prime number. Then there are exactly $\phi(m-1)$ many primitive roots modulo $m$.

$\text{ }$

Theorem 1 is the main theorem in this post. Theorem 2 follows from Theorem 1 and from a result proved in a previous post. The previous result is that if there exists a primitive root modulo $m$ (not necessarily prime), then there exist exactly $\phi(\phi(m))$ many primitive roots modulo $m$ (see Theorem 6 and Corollary 7 in Defining Primitive Root). Since Theorem 1 provides the existence of a primitive root, Theorem 2 follows from Theorem 1 and from the previous result and from the fact that $\phi(p)=p-1$ for any prime number.

___________________________________________________________________________________________________________________

Proving the Main Theorem

Our proof of the existence of a primitive root of any prime modulus uses only elementary techniques. Most of the results we need are developed here in this post. The first result is proved in a previous post (see Theorem 4 in Defining Primitive Root).

Lemma 3

Let $a$ be an integer with $0 \le a \le m-1$ such that $a$ is relaively prime to the modulus $m$. Let $k$ be the order of $a$ modulo $m$. Then the following two conditions are equivalent for any positive integer $n$.

1. The congruence condition $a^n \equiv 1 \ (\text{mod} \ m)$ holds.
2. The number $k$ is a divisor of $n$.

The second result is that of polynomial congruence. Let $f(x)$ be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation $f(x) \equiv 0 \ (\text{mod} \ m)$.

Lemma 4

Let $m$ be a prime number. Let $f(x)$ be a polynomial of degree $n$. Then the equation

$f(x) \equiv 0 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$\text{ }$

has at most $n$ solutions.

Proof of Lemma 4

Suppose $f(x)=a_n x^n +a_{n-1} x^{n-1} + \cdots+a_2 x^2+a_1 x + a_0$ where $a_n \not \equiv 0 \ (\text{mod} \ m)$. We prove the lemma by induction on the degree $n$.

Suppose $n=1$. We have $f(x)=a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$. Since $m$ is prime and $a_1 \not \equiv 0 \ (\text{mod} \ m)$, the coefficient $a_1$ must be relatively prime to $m$. Then the congruence equation $a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$ has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of $x$ and the modulus $m$ (see Theorem 2 in the post Solving Linear Congruences).

Suppose the lemma is true for polynomials of degree $n-1$. Consider two cases – either equation (1) has no solution or equation (1) has a solution. If the first case is true, then the conclusion of the lemma is true.

Suppose the second case is true. Suppose $b$ is a solution to equation (1). It follows that $f(b) \equiv 0 \ (\text{mod} \ m)$ and that $b$ is a least residue modulo $m$.

Our next goal is to factor the polynomial $f(x)$ into a product of a first degree polynomial and a polynomial of degree $n-1$. To this end, note that $x-b$ is a factor of $x^w-b^w$ for $w=1,2,3,\cdots,n$. We have the following derivation

\displaystyle \begin{aligned} f(x)&\equiv f(x)-f(b) \\&\equiv a_n (x^n-b^n) +a_{n-1} (x^{n-1}-b^{n-1}) + \cdots+a_2 (x^2-b^2)+a_1 (x-b) \\&\equiv (x-b) \cdot h(x) \ (\text{mod} \ m) \end{aligned}

where $h(x)$ is a polynomial of degree $n-1$.

Whenever $f(x) \equiv 0 \ (\text{mod} \ m)$, we have $m \ \lvert \ (x-b) \cdot h(x)$. Using the fact that $m$ is prime and Euclid’s lemma, either $m \ \lvert \ (x-b)$ or $m \ \lvert \ h(x)$. In terms of congruence, either $x-b \equiv 0 \ (\text{mod} \ m)$ or $h(x) \equiv 0 \ (\text{mod} \ m)$. The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most $n-1$ solutions. Together, equation (1) has at most $n$ solutions. $\blacksquare$

Lemma 5

Let $m$ be a prime number. If $d \ \lvert \ (p-1)$, then the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has exactly $d$ many solutions.

Proof of Lemma 5

Suppose $d \ \lvert \ (p-1)$. Fermat’s little theorem tells us that $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, namely $1,2,3,\cdots,m-1$. We can factor the polynomial $x^{m-1}-1$ as follows:

$g(x)=x^{m-1}-1=(x^d-1) \cdot (x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$

Let $t(x)=(x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$. Whenever $g(x) \equiv 0 \ (\text{mod} \ m)$, $m \ \lvert \ g(x)=x^{m-1}-1=(x^d-1) \cdot t(x)$. By Euclid’s lemma, $m \ \lvert \ (x^d-1)$ or $m \ \lvert \ t(x)$. In terms of congruence, $x^d \equiv 1 \ (\text{mod} \ m)$ or $t(x) \equiv 0 \ (\text{mod} \ m)$.

By Lemma 4, the congruence $t(x) \equiv 0 \ (\text{mod} \ m)$ has at most $m-1-d$ solutions. Since $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at least $d$ many solutions.

By Lemma 4, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at most $d$ solutions. Thus $x^d \equiv 1 \ (\text{mod} \ m)$ has exactly $d$ many solutions. $\blacksquare$

We need one more lemma before proving Theorem 1.

Lemma 6

Let $a$ and $b$ be integers with $0 \le a,b \le m-1$. Let $\alpha$ be the order of $a$ modulo $m$. Let $\beta$ be the order of $b$ modulo $m$.

Suppose that $\alpha$ and $\beta$ are relatively prime. Then $\alpha \cdot \beta$ is the order of $a \cdot b$ modulo $m$.

Proof of Lemma 6

Let $\gamma$ be the order of $a \cdot b$ modulo $m$. We show that $\gamma=\alpha \beta$. The following derivation shows that $\alpha \ \lvert \ \gamma$.

$1 \equiv 1^\beta \equiv ((ab)^\gamma)^\beta =(ab)^{\gamma \beta}=(a)^{\gamma \beta} (b)^{\gamma \beta}=(a)^{\gamma \beta} (b^{\gamma})^{\beta} \equiv a^{\gamma \beta} \ (\text{mod} \ m)$

Since $a^{\gamma \beta} \equiv 1 \ (\text{mod} \ m)$, we have $\alpha \ \lvert \ \gamma \beta$ (by Lemma 3). Since $\alpha$ and $\beta$ are relatively prime, $\alpha \ \lvert \ \gamma$. By a symmetrical argument, it can also be shown that $\beta \ \lvert \ \gamma$.

Since $\alpha \ \lvert \ \gamma$, we have $\gamma=\alpha \cdot t$ for some integer $t$. Since $\beta \ \lvert \alpha \cdot t$, it follows that $\beta \ \lvert t$ (Euclid’s lemma). So $t=\beta \cdot z$ for some integer $z$. Now $\gamma=\alpha \cdot \beta \cdot z$. This means that $\alpha \beta \ \lvert \ \gamma$.

On the other hand, we have $\gamma \ \lvert \alpha \beta$. This follows from the following derivation and from Lemma 3.

$(ab)^{\alpha \beta}=(a^\alpha)^\beta \cdot (b^\beta)^\alpha \equiv 1 \ (\text{mod} \ m)$

It follows that $\gamma= \alpha \beta$. $\blacksquare$

Remark
Lemma 6 indicates that the orders of two numbers are multiplicative as long as the two orders are relatively prime. As a corollary of Lemma 6, it follows that the order of a product of finitely many numbers (for the same modulus) is the product of the individual orders provided that the orders are pairwise relatively prime. This fact will be used in the proof of Theorem 1 below.

Proof of Theorem 1

We start off with a prime factorization of the number $p-1$.

$\displaystyle p-1=w_1^{e_1} \cdot w_2^{e_2} \cdot w_3^{e_3} \cdots w_n^{e_n}$

In the above factorization, the numbers $w_i$ are distinct prime numbers and the exponents $e_i \ge 1$.

For each $i$, it is clear that $w_i^{e_i} \ \lvert \ (p-1)$. By Lemma 5, the congruence equation

$\displaystyle x^{w_i^{e_i}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

has exactly $w_i^{e_i}$ many solutions. Note that the $w_i^{e_i}$ many solutions are integers in the interval $0 \le x \le p-1$. Furthermore, the order modulo $p$ of each of these solutions to (2) is a divisor of $w_i^{e_i}$ (by Lemma 3).

In fact, from Lemma 3, we can say that for any integer $x$ in the interval $0 \le x \le p-1$, the number $x$ is a solution of equation (2) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i}$. We have the following claim.

Claim
For each $i$, we claim that there exists at least one integer $a_i$ in the interval $0 \le x \le p-1$ such that the order of $a_i$ modulo $p$ is $w_i^{e_i}$.

To see the above claim, the congruence equation

$\displaystyle x^{w_i^{e_i-1}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

has exactly $w_i^{e_i-1}$ many solutions in the interval $0 \le x \le p-1$ (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of $w_i^{e_i-1}$.

In fact, from Lemma 3, we can also say that for any integer $x$ in the interval $0 \le x \le p-1$, the number $x$ is a solution of equation (3) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i-1}$.

Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of $w_i^{e_i-1}$ are also divisors of $w_i^{e_i}$.

Thus there are $w_i^{e_i}-w_i^{e_i-1}$ many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it $a_i$. Let $k$ be the order of $a_i$ modulo $p$. There are three possibilities for $k$:

$k \le w_i^{e_i-1} \ \ \ \ \ w_i^{e_i-1}

Since $a_i$ is a solution to (2), the number $k$ is a divisor of $w_i^{e_i}$. Note that there are no divisors of $w_i^{e_i}$ within the interval $w_i^{e_i-1} since $w_i$ is a prime number. So $w_i^{e_i-1} is not possible.

Since $a_i$ is not a solution to (3), the number $k$ is not a divisor of $w_i^{e_i-1}$. This means that $k \le w_i^{e_i-1}$ is not possible. Since $w_i$ is prime, $k$ must be a power of $w_i$. Since $k$ must be a power of $w_i$, if $k \le w_i^{e_i-1}$, $k$ is then a divisor of $w_i^{e_i-1}$.

So the only possibility is that $k=w_i^{e_i}$. This establishes the above claim.

Let $g=a_1 \cdot a_2 \cdots a_n$. The primitive root modulo $p$ we are looking for is either $g$ if $g or the least residue of $g$ if $g \ge p$.

According to the above claim, the order modulo $p$ of $a_i$ is $w_i^{e_i}$. Clearly $w_i^{e_i}$ and $w_j^{e_j}$ are relatively prime for $i \ne j$. As a corollary of Lemma 6, the order of the product $g=a_1 \cdot a_2 \cdots a_n$ is the products of $w_i^{e_i}$, namely $p-1$. Thus $g=a_1 \cdot a_2 \cdots a_n$ or its least residue modulo $p$ is a primitive root. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$