# The primitive root theorem revisited

The primitive root theorem lists out all possible values of $m$ for which primitive roots exist in the modulo $m$ arithmetic. The theorem is proved in this previous post and several blog posts leading to it. In this post, we reorganize the proof and add some additional information. The proof of the primitive root theorem detailed below shows that the list of values of the moduli $m$ is very restrictive and, in addition, that such moduli $m$ are such that there are no extra square root beside 1 and -1. The crux of the argument is a lemma that indicates that most moduli have a third square root of 1 in addition to 1 and -1. The proof is also an opportunity for applying the Chinese remainder theorem (usually abbreviated CRT).

____________________________________________________________________________

The primitive root theorem

In this post, $m$ is a positive integer that serves as the modulus. Given $m$, it is of interest to know all the integers $a$ where $1 \le a and that $a$ and the modulus $m$ are relatively prime. The number of such values of $a$ is denoted by $\phi(m)$ (this is called the phi function). For example, for $m=11$, $\phi(11)=10$. For $m=10$, $\phi(10)=4$ since there are only 4 numbers that are relatively prime to 10, namely 1, 3, 7, and 9.

A positive integer $g$ is said to be a primitive root modulo $m$ if $\phi(m)$ is the least positive integer $x$ such that $g^x \equiv 1 \ (\text{mod} \ m)$. If $g$ is said to be a primitive root modulo $m$, it is necessary that $g$ and the modulus $m$ are relatively prime. This is because of this basic fact: $a$ and the modulus $m$ are relatively prime if and only $a \cdot b \equiv 1 \ (\text{mod} \ m)$ if and only of $a^t \equiv 1 \ (\text{mod} \ m)$ for some integer $t$. The middle condition is saying that $a$ has a multiplicative modulo $m$.

The following lemma is alluded to at the beginning. The idea will used through the proof of the primitive root theorem. So it is extracted as a lemma to make the argument easier to follow.

Lemma 1
Let $c$ and $d$ be integers such that $c>2$ and $d>2$ and such that $c$ and $d$ are relatively prime. Let $m=c \cdot d$. Then there exist $x_0$ such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$ and such that $x_0^2 \equiv 1 \ (\text{mod} \ m)$, i.e. $x_0$ is a third square root of 1 modulo $m$ that is neither 1 nor -1.

Proof
Consider the two equations $x \equiv 1 \ (\text{mod} \ c)$ and $x \equiv -1 \ (\text{mod} \ d)$. By the Chinese remainder theorem, there is a solution $x_0$ to this system of equations. We have $x_0^2 \equiv 1 \ (\text{mod} \ c)$ and $x_0^2 \equiv 1 \ (\text{mod} \ d)$. By the Chinese remainder theorem again, $x_0^2 \equiv 1 \ (\text{mod} \ m)$. There are three possibilities for $x_0$, 1, -1 or another value. If $x_0 \equiv 1 \ (\text{mod} \ m)$, then $1 \equiv -1 \ (\text{mod} \ d)$, which means $d \lvert 2$, contradicting that $d>2$. Similarly, $x_0 \equiv -1 \ (\text{mod} \ m)$ would lead to $c \lvert 2$, which contradicts $c>2$. The only possibility is that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$. $\square$

The proof of Lemma 1 makes use of CRT twice. Lemma 1 will be used several times in the proof of $2 \longrightarrow 3$ in the primitive root theorem.

The Primitive Root Theorem
Let $m$ be a positive integer. Then the following conditions are equivalent:

1. There exists a primitive root modulo $m$.
2. The equation $x^2 \equiv 1 \ (\text{mod} \ m)$ has no solution outside of $\pm 1$ modulo $m$. In other words, the only square roots of 1 modulo $m$ are $\pm 1$.
3. The only possibilities for $m$ are:
• $m=2$,
• $m=4$,
• $m$ is the power of an odd prime,
• $m$ is twice the power of an odd prime.

Proof
$1 \longrightarrow 2$
Suppose that $g$ is a primitive root modulo $m$. Suppose that condition 2 does not hold. As a result, there exists some positive integer $a \not \equiv \pm 1 \ (\text{mod} \ m)$ such that $a^2 \equiv 1 \ (\text{mod} \ m)$. Since $g$ is a primitive root modulo $m$, $a \equiv g^h \ (\text{mod} \ m)$ for some integer integer $h$ with $1 \le h < \phi(m)$ (see Theorem 5 here). If $h = \phi(m)$, then $a \equiv 1 \ (\text{mod} \ m)$. Thus $1 \le h < \phi(m)$.

Furthermore, $a^2 \equiv g^{2h} \equiv 1 \ (\text{mod} \ m)$. We have $\phi(m) \le 2h$, since $\phi(m)$ is the least power $x$ such that $g^x$ is congruent to 1 modulo $m$. Since $g^{2h}=g^{\phi(m)} g^{2h-\phi(m)}$, $g^{2h} \equiv g^{2h-\phi(m)} \equiv 1 \ (\text{mod} \ m)$. We have $\phi(m) \le 2h-\phi(m)$ since $\phi(m)$ is the least power $x$ such that $g^x$ is congruent to 1 modulo $m$. The last inequality leads to $\phi(m) \le h$, contradicting the earlier observation of $h < \phi(m)$. Thus condition 2 must holds if condition 1 is true.

$2 \longrightarrow 3$
We show that for any $m$ outside of the four possibilities listed in condition 3, condition 2 does not hold. This means that if condition 2 holds for $m$, $m$ must be one of the four possibilities. We consider the cases of $m$ even and $m$ odd separately.

Case 1. The modulus $m$ is odd. Since $m$ is not the power of one single odd prime, it must be the product of two or more powers of odd primes. Let $m=c \cdot d$ where $c$ a power of an odd prime and $d$ is the product of one ore more powers of odd primes. It is clear that $c$ and $d$ are relatively prime. It is also the case that $c>2$ and $d>2$ since each of them has at least one odd prime factor. By Lemma 1, there exists a square root $x_0$ of 1 such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$.

For the second case, $m$ is even. We break this up into two cases. One is that $m$ is a power of 2. The other is that $m$ is not a power of 2. In these two cases, the goal is still to show that if $m$ is outside of the four possibilities in condition 3, then condition 2 does not hold.

Case 2a. The modulus $m$ is a power of 2.
Then $m=2^h$ where $h \ge 3$. In this case, we can actually exhibit a square root that is neither 1 nor -1. Define $x_0=2^{h-1}-1$. Since $h \ge 3$, $x_0>1$. Consider the following derivation:

$\displaystyle x_0^2=(2^{h-1}-1)^2=2^{2(h-1)}-2^h+1=2^h (2^{h-2}-1)+1$

The above derivation shows that $x_0^2 \equiv 1 \ (\text{mod} \ m=2^h)$. It is clear that $x_0 \not \equiv \pm 1 \ (\text{mod} \ 2^h)$.

Case 2b. The modulus $m$ is not a power of 2.
Since $m$ is even and $m$ is not a power of 2, it must be that $m=2^k \times q$ where $q$ is odd. Either $q$ is the power of an odd prime or it is not. If $q$ is the power of an odd prime, then $k \ge 2$. If $q$ is not the power of an odd prime (i.e. $q$ is of case 1 above), then $k \ge 1$. To make the argument clear, we consider the two sub cases separately.

Case 2b-1. The modulus $m=2^k \times p^j$ where $k \ge 2$, $j \ge 1$ and $p$ is an odd prime.
Let $c=2^k$ and $d=p^j$. Note that $m=c \cdot d$. By Lemma 1, there exists a square root $x_0$ of 1 modulo $m$ such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$.

Case 2b-2. The modulus $m=2^k \times b$ where $k \ge 1$ and $b$ is an odd integer that is not the power of an odd prime.
Consider the prime factorization of $b$, say $b=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$ where $t \ge 2$. Let $c=2^k \cdot p_1^{e_1}$ and $d=p_2^{e_2} \cdots p_t^{e_t}$. We can also apply Lemma 1 to obtain a square root of 1 modulo $m=c \cdot d$ that is neither 1 nor -1.

$3 \longrightarrow 1$
It is clear that there are primitive roots modulo both $m=2$ and $m=4$. For the case of power of an odd prime, see this previous post. For the case of twice the power of an odd prime, see this previous post. $\square$

____________________________________________________________________________

Lemma 1 plays a prominent role in the proof of the direction $2 \longrightarrow 3$. Lemma 1 shows that it is easy to find moduli that have a third square root of 1 (other than 1 and -1). As the primitive root theorem shows, having a third square root of 1 is the condition that kills the possibility of having a primitive root. Lemma 1 and the primitive root theorem speak to different sides of the same coin. One tells us that moduli with no primitive roots are easy to find. The other says that only in rare cases do you find moduli that admit primitive roots, namely the moduli that are not product of two factors, each of which is greater than 2, that are relatively prime. The proof of $2 \longrightarrow 3$ may seem tedious (by listing out all cases that satisfy Lemma 1). The key to understanding the proof is through Lemma 1.
$\copyright \ 2015 \text{ by Dan Ma}$