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 be an odd prime number. Let be any positive integer. Then there exist primitive roots modulo .

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 and be positive integers that are relatively prime. Then and if and only if .

**Proof of Theorem 2**

Suppose and . Converting these into equations, we have and for some integers and . It follows that . This implies that . Since and and relatively prime, and for some integer . Now the equation can be written as , which implies that .

Suppose . Then for some integer , which implies both congruences and .

**Proof of Theorem 1**

Let be a primitive root modulo (shown to exist in the post *Primitive roots of powers of odd primes*). When is odd, we show that is a primitive root modulo . When is even, we show that is a primitive root modulo .

First the odd case. Since is a primitive root modulo , for all positive . Since is odd, is odd for all integers . So for all integers . By CRT (Theorem 2), for all positive . This implies that is a primitive root modulo .

Now the even case. Note that is odd (even + odd is odd). It is also the case that is odd for all . Thus for all .

In expanding using the binomial theorem, all terms except the first term is divisible by . So . Furthermore, for all positive since is a primitive root modulo . So for all positive .

By CRT (Theorem 2), we have for all positive . This implies that is a primitive root modulo .

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

___________________________________________________________________________________________________________________

Pingback: The primitive root theorem revisited | Exploring Number Theory