# Primitive roots of twice the powers of odd primes

In a previous post, we show that there exist primitive roots modulo the power of an odd prime number (see Primitive roots of powers of odd primes). In this post we show that there exist primitive roots modulo two times the power of an odd prime number. Specifically we prove the following theorem.

Theorem 1

Let $p$ be an odd prime number. Let $j$ be any positive integer. Then there exist primitive roots modulo $p^j$.

We make use of the Chinese Remainder Theorem (CRT) in proving Theorem 1. We use the following version of CRT (also found in this post)

Theorem 2 (CRT)

Let $m$ and $n$ be positive integers that are relatively prime. Then $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$ if and only if $a \equiv b \ (\text{mod} \ mn)$.

Proof of Theorem 2
$\Longrightarrow$
Suppose $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$. Converting these into equations, we have $a=b+mx$ and $a=b+ny$ for some integers $x$ and $y$. It follows that $mx=ny$. This implies that $m \ \lvert \ ny$. Since $m$ and $n$ and relatively prime, $m \ \lvert \ y$ and $y=mt$ for some integer $t$. Now the equation $a=b+ny$ can be written as $a=b+mnt$, which implies that $a \equiv b \ (\text{mod} \ mn)$.

$\Longleftarrow$
Suppose $a \equiv b \ (\text{mod} \ mn)$. Then $a=b+mns$ for some integer $s$, which implies both congruences $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$. $\blacksquare$

Proof of Theorem 1
Let $a$ be a primitive root modulo $p^j$ (shown to exist in the post Primitive roots of powers of odd primes). When $a$ is odd, we show that $a$ is a primitive root modulo $2p^j$. When $a$ is even, we show that $a+p^j$ is a primitive root modulo $2p^j$.

First the odd case. Since $a$ is a primitive root modulo $p^j$, $a^k \not \equiv 1 \ (\text{mod} \ p^j)$ for all positive $k<\phi(p^j)$. Since $a$ is odd, $a^k$ is odd for all integers $k \ge 1$. So $a^k \equiv 1 \ (\text{mod} \ 2)$ for all integers $k \ge 1$. By CRT (Theorem 2), $a^k \not \equiv 1 \ (\text{mod} \ 2p^j)$ for all positive $k<\phi(p^j)=\phi(2 p^j)$. This implies that $a$ is a primitive root modulo $2p^j$.

Now the even case. Note that $a+p^j$ is odd (even + odd is odd). It is also the case that $(a+p^j)^k$ is odd for all $k \ge 1$. Thus $(a+p^j)^k \equiv 1 \ (\text{mod} \ 2)$ for all $k \ge 1$.

In expanding $(a+p^j)^k$ using the binomial theorem, all terms except the first term $a^k$ is divisible by $p^j$. So $(a+p^j)^k \equiv a^k \ (\text{mod} \ p^j)$. Furthermore, $a^k \not \equiv 1 \ (\text{mod} \ p^j)$ for all positive $k<\phi(p^j)$ since $a$ is a primitive root modulo $p^j$. So $(a+p^j)^k \not \equiv 1 \ (\text{mod} \ p^j)$ for all positive $k<\phi(p^j)$.

By CRT (Theorem 2), we have $(a+p^j)^k \not \equiv 1 \ (\text{mod} \ 2p^j)$ for all positive $k<\phi(p^j)=\phi(2p^j)$. This implies that $a+p^j$ is a primitive root modulo $2p^j$. $\blacksquare$

The remainder of the proof of the primitive root theorem is found in The primitive root theorem.

___________________________________________________________________________________________________________________

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