# Primitive roots of powers of odd primes

Let $p$ be an odd prime number. There exist primitive roots modulo $p$ (in fact there are $\phi(p-1)$ many). There are various strategies for finding primitive roots of a prime modulus, other than simply trying all candidates (discussed here and here). In this post we discuss how to obtain primitive roots of moduli that are power of odd primes. Starting from a given primitive root modulo $p$, we show how to get a primitive root modulo $p^2$. Next, starting with a primitive root modulo $p^2$, we show how to get a primitive root modulo $p^n$ for any integer $n \ge 3$. It follows from these results that there exist primitive roots modulo any power of any odd prime number. The results discussed in this post build up to the primitive root theorem. See the following posts for the rest of the proof of the primitive root theorem.

___________________________________________________________________________________________________________________

Example

We start the discussion with an example. There are two primitive roots for the odd prime modulus $p=7$. They are $3$ and $5$. Are $3$ and $5$ also primitive roots modulo $7^2=49$?

Note that $\phi(49)=\phi(7^2)=7(7-1)=42$. One way to find out is to check

$3^x \ (\text{mod} \ 49)$ and $5^x \ (\text{mod} \ 49)$

by letting $x$ be the proper divisors of $42$. The proper divisors of $42$ are $1$, $2$, $3$, $6$, $7$, $14$, and $21$. However, it is not necessary to check all $7$ proper divisors of $42$.

There is a better check that requires only checking $3$ divisors of $42$. According to a previous post, we only need to check the following:

$\displaystyle 3^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49)$ and $\displaystyle 3^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49)$ and $\displaystyle 3^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)$

$\displaystyle 5^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49)$ and $\displaystyle 5^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49)$ and $\displaystyle 5^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)$

To see why this works, see Check #3 in the post More about checking for primitive roots. Even this better check can be improved.

According to Lemma 1 discussed below, all we need to do is to check the following:

$3^6 \ (\text{mod} \ 49)$ and $5^6 \ (\text{mod} \ 49)$

If the congruence $\not \equiv 1 \ (\text{mod} \ 49)$, then the number in question is a primitive root modulo $49$. Otherwise, it is not a primitive root. Note that the exponent is $\phi(7)=6$.

We have $3^6 \equiv 43 \ (\text{mod} \ 49)$ and $5^6 \equiv 43 \ (\text{mod} \ 49)$. So the two numbers $3$ and $5$ are primitive roots modulo $49$.

Remarks
In general, given that $a$ is a primitive root modulo $p$, to check whether $a$ is a primitive root modulo $p^2$, all we need to do is to check $a^{p-1} \ (\text{mod} \ p^2)$. If it is $\not \equiv 1 \ (\text{mod} \ p^2)$, then $a$ is a primitive root modulo $p^2$. Otherwise, it is not a primitive root modulo $p^2$.

What makes this works is that if $a$ is a primitive root modulo $p$, the order of $a$ modulo $p^2$ can only be $p-1$ or $p(p-1)=\phi(p^2)$ (see Lemma 1 below). When $a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2)$, the order of $a$ modulo $p^2$ is not $p-1$ and is $p(p-1)=\phi(p^2)$, which means that $a$ is a primitive root modulo $p^2$. When $a^{p-1} \equiv 1 \ (\text{mod} \ p^2)$, the order of $a$ modulo $p^2$ is $p-1$, which means that $a$ is not a primitive root modulo $p^2$.

Furthermore, in the case that the order of $a$ modulo $p^2$ is $p-1$, even though the number $a$ is not a primitive root modulo $p^2$, the number $a+p$ is a primitive root modulo $p^2$ (see Theorem 2 below).

As an example, $31 \equiv 3 \ (\text{mod} \ 7)$. So $31$ is also a primitive root modulo $7$. But $31^6 \equiv 1 \ (\text{mod} \ 49)$. So $31$ is not a primitive root modulo $49$. However $38$ is a primitive root modulo $49$. Note that $38^6 \equiv 15 \ (\text{mod} \ 49)$. For more details, see Theorem 2 below.

Theorem 4 below states that any primitive root modulo $p^2$ is also a primitive root modulo any higher power of $p$. For example, $38$ is a primitive root modulo $7^n$ for any $n \ge 3$.

___________________________________________________________________________________________________________________

Square of an Odd Prime

We now show that there exist primitive roots modulo the square of an odd prime (Theorem 2 below). The starting point is that there is a given primitive root modulo a prime number (the existence is proved in Primitive roots of prime moduli).

Lemma 1

Let $p$ be a prime number. Let $g$ be a primitive root modulo $p$. Let $t$ be the order of $g$ modulo $p^2$. Then either $t=p$ or $t=p(p-1)$.

Proof of Lemma 1
Immediately we know that $t \ \lvert \ \phi(p^2)=p(p-1)$. Furthermore, it follows that $g^t \equiv 1 \ (\text{mod} \ p^2)$, which implies $g^t=1+p^2 y$ for some integer $y$. In turn this equation implies that $g^t \equiv 1 \ (\text{mod} \ p)$. We also have we have $p-1 \ \lvert \ t$ since the order of $g$ modulo $p$ is $p-1$.

So we have $p-1 \ \lvert \ t$ and $t \ \lvert \ p(p-1)$. In words, the integer $t$ is at least $p-1$ and at the same time $t$ is a divisor of $p(p-1)$. The only possibilities of $t$ are $t=p-1$ or $t=p(p-1)$. $\blacksquare$

Theorem 2

Let $p$ be an odd prime number. Let $a$ be a primitive root modulo $p$. Then either $a$ or $a+p$ is a primitive root modulo $p^2$. Thus there exist primitive roots modulo $p^2$.

Proof of Theorem 2
Let $k$ be the order of $a$ modulo $p^2$. By Lemma 1, we have $k=p-1$ or $k=\ p(p-1)$. Note that $\phi(p^2)=p(p-1)$. Thus if it is the case that $k=\ p(p-1)$, then $a$ is a primitive root modulo $p^2$. So in the remainder of the proof, we assume that $k=p-1$.

Since $a+p \equiv a \ (\text{mod} \ p)$, the number $a+p$ is a primitive root modulo $p$. Let $h$ be the order of $a+p$ modulo $p^2$. Using Lemma 1 again, there are only two possibilities for $h$, namely $h=p-1$ or $h=\ p(p-1)=\phi(p^2)$. If we can show that the case $h=p-1$ is not possible, then $a+p$ must be a primitive root modulo $p^2$. To this end, we show $(a+p)^{p-1} \not \equiv 1 \ (\text{mod} \ p)$.

Using the binomial theorem, we expand $(a+p)^{p-1}$ as follows:

$\displaystyle (a+p)^{p-1}=a^{p-1}+\binom{p-1}{1}a^{p-2}p+\binom{p-1}{2}a^{p-3}p^2+\binom{p-1}{3}a^{p-4}p^3 +\cdots+p^{p-1}$

All terms except the first two terms are divisible by $p^2$. Recall that we assume above that $k=p-1$ (the order of $a$ modulo $p^2$). So in the following derivation, we use $a^{p-1} \equiv 1 \ (\text{mod} \ p^2)$.

\displaystyle \begin{aligned} (a+p)^{p-1}&\equiv a^{p-1}+\binom{p-1}{1}a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+(p-1)a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+p^2 a^{p-2}-p a^{p-2} \ (\text{mod} \ p^2) \\&\equiv 1+0-p a^{p-2} \ (\text{mod} \ p^2) \\&\equiv 1-p a^{p-2} \ (\text{mod} \ p^2) \end{aligned}

We now need to show that $1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2)$. Suppose that $1-p a^{p-2} \equiv 1 \ (\text{mod} \ p^2)$. Then we have $-p a^{p-2} \equiv 0 \ (\text{mod} \ p^2)$.

Because $a^{p-1} \equiv 1 \ (\text{mod} \ p^2)$, $a^{p-2}$ is the multiplicative inverse of $a$ modulo $p^2$. Now multiply both sides of $-p a^{p-2} \equiv 0 \ (\text{mod} \ p^2)$ by $a$, we get $-p \equiv 0 \ (\text{mod} \ p^2)$, which implies $p$ is divisible by $p^2$, a contradiction. So $(a+p)^{p-1} \equiv 1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2)$. Thus $h=p-1$ is not possible. Then $h=p(p-1)$, which means that $a+p$ is a primitive root modulo $p^2$. $\blacksquare$

___________________________________________________________________________________________________________________

Higher Powers of an Odd Prime

In this section, we show that there exist primitive roots modulo any higher power of an odd prime.

Lemma 3

Let $p$ be an odd prime number. If $g$ be a primitive root modulo $p^2$, then $g$ is also a primitive root modulo $p$.

Proof of Lemma 3
Let $g$ be a primitive root modulo $p^2$ where $p$ is an odd prime number. To show that $g$ be a primitive root modulo $p$, we use the following result:

(*) A number $h$ is a primitive root modulo $m$ if and only if $\displaystyle h^{\frac{\phi(m)}{t}} \not \equiv 1 \ (\text{mod} \ m)$ for all prime divisor $t$ of $\phi(m)$.

Let $t$ be a prime divisor of $\phi(p)=p-1$. Then $t$ is a prime divisor of $\phi(p^2)=p(p-1)$. By the result indicated by (*), we have $\displaystyle g^{\frac{p(p-1)}{t}} \not \equiv 1 \ (\text{mod} \ p^2)$. It follows that $\displaystyle g^{\frac{p-1}{t}} \not \equiv 1 \ (\text{mod} \ p)$. Thus by the result indicated by (*), $g$ is a primitive root modulo $p$. Note that if $\displaystyle g^{\frac{p-1}{t}} \equiv 1 \ (\text{mod} \ p)$, then $\displaystyle (g^{\frac{p-1}{t}})^p \equiv 1 \ (\text{mod} \ p)$. $\blacksquare$

Theorem 4

Let $p$ is an odd prime number. Let $a$ be a primitive root modulo $p^2$. Then $a$ is a primitive root modulo $p^{j}$ for all integers $j \ge 3$.

Proof of Theorem 4
Note that $\phi(p^2)=p(p-1)$. Thus $a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2)$. By Lemma 3, the number $a$ is also a primitive root modulo $p$. Thus $a^{p-1} \equiv 1 \ (\text{mod} \ p)$. Thus $a^{p-1}=1+wp$ for some integer $w$. It is the case that $w$ cannot be a multiple of $p$. Otherwise, we would have $a^{p-1} \equiv 1 \ (\text{mod} \ p^2)$. We will use that fact that $w$ cannot be a multiple of $p$ at a later step in the proof.

Let $j$ be any integer with $j \ge 3$. Note that $\phi(p^j)=p^{j-1}(p-1)$. We establish the following three claims.

Claim 1
Let $k$ be the order of $a$ modulo $p^j$. The possibilities for $k$ are $p^n(p-1)$ where $n=1,2,3,\cdots,j-1$.

Claim 2
It is the case that $k \ne p^{j-2}(p-1)$. To establish this, we show $\displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j)$.

Claim 3
It is the case that $k \ne p^{n}(p-1)$ for $n=1,2,3,\cdots,j-3$.

Once the three claims are established, the order of $a$ modulo $p^j$ must be $\phi(p^j)=p^{j-1}(p-1)$. Hence $a$ is a primitive root modulo $p^j$.

Claim 3 follows from Claim 2. Note that if $\displaystyle a^{p^{n}(p-1)} \equiv 1 \ (\text{mod} \ p^j)$ where $n=0,1,2,3,\cdots,j-3$, then we can raise both sides of the equation by an appropriate power of $p$ to get $\displaystyle a^{p^{j-2}(p-1)} \equiv 1 \ (\text{mod} \ p^j)$.

Proof of Claim 1. Since $k$ is the order, we have $\displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^j)$, which leads to $\displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^2)$. These two congruences imply $k \ \lvert \ \phi(p^j)=p^{j-1}(p-1)$ and $p(p-1) \ \lvert \ k$.

Thus $k$ is at least $p(p-1)$ and divides $p^{j-1}(p-1)$. With $p$ being a prime, $k$ can only be $p(p-1)$, $p^{2}(p-1)$, $\cdots$, $p^{j-1}(p-1)$.

Proof of Claim 2.
We show that $\displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j)$. With $a^{p-1}=1+wp$ derived at the beginning of the proof, we have $\displaystyle a^{p^{j-2}(p-1)}=(1+wp)^{p^{j-2}}$. Upon using the binomial theorem to expand $\displaystyle (1+wp)^{p^{j-2}}$, we see that all terms except the first two are divisible by $p^j$. We can discard them since we take congruence modulo $p^j$. The following shows the first two terms:

\displaystyle \begin{aligned} a^{p^{j-2}(p-1)}&= (1+wp)^{p^{j-2}} \\&\equiv 1+p^{j-2} wp \ (\text{mod} \ p^j) \\&\equiv 1+wp^{j-1} \ (\text{mod} \ p^j) \end{aligned}

We claim that $1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j)$. Suppose $1+wp^{j-1} \equiv 1 \ (\text{mod} \ p^j)$. Then $wp^{j-1} \equiv 0 \ (\text{mod} \ p^j)$, which implies $wp^{j-1}=p^j c$ for some integer $c$. Cancelling out $p^{j-1}$, we have $w=p c$, which contradicts the fact that $w$ cannot be a multiple of $p$. So $1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j)$. This establish Claim 3 and the theorem is also established. $\blacksquare$

___________________________________________________________________________________________________________________

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