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.
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.