Let be an odd prime number. There exist primitive roots modulo (in fact there are 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 , we show how to get a primitive root modulo . Next, starting with a primitive root modulo , we show how to get a primitive root modulo for any integer . 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 . They are and . Are and also primitive roots modulo ?
Note that . One way to find out is to check

and
by letting be the proper divisors of . The proper divisors of are , , , , , , and . However, it is not necessary to check all proper divisors of .
There is a better check that requires only checking divisors of . According to a previous post, we only need to check the following:

and and
and and
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:

and
If the congruence , then the number in question is a primitive root modulo . Otherwise, it is not a primitive root. Note that the exponent is .
We have and . So the two numbers and are primitive roots modulo .
Remarks
In general, given that is a primitive root modulo , to check whether is a primitive root modulo , all we need to do is to check . If it is , then is a primitive root modulo . Otherwise, it is not a primitive root modulo .
What makes this works is that if is a primitive root modulo , the order of modulo can only be or (see Lemma 1 below). When , the order of modulo is not and is , which means that is a primitive root modulo . When , the order of modulo is , which means that is not a primitive root modulo .
Furthermore, in the case that the order of modulo is , even though the number is not a primitive root modulo , the number is a primitive root modulo (see Theorem 2 below).
As an example, . So is also a primitive root modulo . But . So is not a primitive root modulo . However is a primitive root modulo . Note that . For more details, see Theorem 2 below.
Theorem 4 below states that any primitive root modulo is also a primitive root modulo any higher power of . For example, is a primitive root modulo for any .
___________________________________________________________________________________________________________________
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 be a prime number. Let be a primitive root modulo . Let be the order of modulo . Then either or .
Proof of Lemma 1
Immediately we know that . Furthermore, it follows that , which implies for some integer . In turn this equation implies that . We also have we have since the order of modulo is .
So we have and . In words, the integer is at least and at the same time is a divisor of . The only possibilities of are or .

Theorem 2

Let be an odd prime number. Let be a primitive root modulo . Then either or is a primitive root modulo . Thus there exist primitive roots modulo .
Proof of Theorem 2
Let be the order of modulo . By Lemma 1, we have or . Note that . Thus if it is the case that , then is a primitive root modulo . So in the remainder of the proof, we assume that .
Since , the number is a primitive root modulo . Let be the order of modulo . Using Lemma 1 again, there are only two possibilities for , namely or . If we can show that the case is not possible, then must be a primitive root modulo . To this end, we show .
Using the binomial theorem, we expand as follows:
All terms except the first two terms are divisible by . Recall that we assume above that (the order of modulo ). So in the following derivation, we use .
We now need to show that . Suppose that . Then we have .
Because , is the multiplicative inverse of modulo . Now multiply both sides of by , we get , which implies is divisible by , a contradiction. So . Thus is not possible. Then , which means that is a primitive root modulo .
___________________________________________________________________________________________________________________
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 be an odd prime number. If be a primitive root modulo , then is also a primitive root modulo .
Proof of Lemma 3
Let be a primitive root modulo where is an odd prime number. To show that be a primitive root modulo , we use the following result:

(*) A number is a primitive root modulo if and only if for all prime divisor of .

For proof of this statement, see Lemma 2 in the post More about checking for primitive roots.
Let be a prime divisor of . Then is a prime divisor of . By the result indicated by (*), we have . It follows that . Thus by the result indicated by (*), is a primitive root modulo . Note that if , then .

Theorem 4

Let is an odd prime number. Let be a primitive root modulo . Then is a primitive root modulo for all integers .
Proof of Theorem 4
Note that . Thus . By Lemma 3, the number is also a primitive root modulo . Thus . Thus for some integer . It is the case that cannot be a multiple of . Otherwise, we would have . We will use that fact that cannot be a multiple of at a later step in the proof.
Let be any integer with . Note that . We establish the following three claims.
Claim 1
Let be the order of modulo . The possibilities for are where .
Claim 2
It is the case that . To establish this, we show .
Claim 3
It is the case that for .
Once the three claims are established, the order of modulo must be . Hence is a primitive root modulo .
Claim 3 follows from Claim 2. Note that if where , then we can raise both sides of the equation by an appropriate power of to get .
Proof of Claim 1. Since is the order, we have , which leads to . These two congruences imply and .
Thus is at least and divides . With being a prime, can only be , , , .
Proof of Claim 2.
We show that . With derived at the beginning of the proof, we have . Upon using the binomial theorem to expand , we see that all terms except the first two are divisible by . We can discard them since we take congruence modulo . The following shows the first two terms:
We claim that . Suppose . Then , which implies for some integer . Cancelling out , we have , which contradicts the fact that cannot be a multiple of . So . This establish Claim 3 and the theorem is also established.
___________________________________________________________________________________________________________________
Pingback: The primitive root theorem revisited  Exploring Number Theory