In the previous post Finding Primitive Roots, we demonstrate one approach for finding all primitive roots of a prime modulus. In this post, we summarize the ideas behind that example.
Throughout this discussion is a positive integer that is used as the modulus for modular arithmetic, and is assumed to be a positive integer that is relatively prime to such that .
According to Fermat’s little theorem, if the modulus is prime, then . If the modulus is relaxed to include non-prime integers as well, then we have Euler’s theorem which states that where is Euler’s phi function. For any modulus , is simply the numbers of possible values of that are relatively prime to . For example, if and if .
So it is always the case that . Another way to say this is that the number is always a solution to the following congruence equation.
With this above discussion in mind, we define the notion of order. The order of modulo is the least positive integer solution to the congruence equation (1).
Furthermore, the number is said to be a primitive root modulo if the least positive integer solution to (1) is .
Note that even though the notions of order and primitive root are defined here for integers that are relatively prime to with , the definitions are also valid for positive outside the range . Relaxing the definitions can make some proofs go easier (e.g. Theorem 2 below).
An Approach in Finding Primitive Roots
We now summarize the ideas discussed in the previous post Finding Primitive Roots.
Recall that is a positive integer less than that is relatively prime to . How do we check if is a primitive root? On the face of it, we need to check that no positive integer less than is a solution to equation (1). It turns out that we only need to check positive integers less than that are divisors of . We have the following theorem.
The following conditions are equivalent.
- The number is a primitive root modulo .
- Every positive divisor of with is not a solution of the congruence equation (1).
If we know that there exists a primitive root for a modulus, the followng theorem tells us how to find the other primitive roots.
Suppose the number is a primitive root modulo . Then there are exactly many primitive roots modulo . They are obtained by finding the least residues of the numbers where the exponents are taken from the following set.
Thus the above two theorems taken together form an algorithm for finding primitve roots of a modulus (if one is known to exist to begin with). We can use Theorem 1 to find a primitive root. Once we have found one, we can raise it to exponents that are relatively prime to the number to find the remaining primitive roots. Since there are many positive integers that are less than and relatively prime to , there are many primitive roots modulo (if one exists).
Before proving the theorems, let’s look at a quick example.
For , . The candidates for primitive roots modulo are in the set . The divisors of are . According to Theorem 1, we only need to raise these numbers to exponents that are divisors of .
Note that , and . Thus is a primitive root modulo .
The positive integers that are less than and that are relatively prime to are . So there are four primitive roots modulo . They are:
Proof of Theorems
Proof of Theorem 1
The direction is clear. If is a primitive root modulo , then by definition, no positive integer less than can be a solution to the congruence equation (1).
Let be the order of modulo . The key to the proof is that must be a divisor of (see Theorem 4 and Corollary 5 in the post Defining Primitive Root). For the sake of completeness, we provide the proof here.
Since is the least positive solution of the congruence equation (1), . Using the division algorithm, we have for some integers and where . We have the following calculation.
So we have and . Since is the least positive solution of (1), the only possibility is that . Hence and is a divisor of .
Now back to the proof for . We claim that , implying that is a primitive root modulo . If , then is a positive divisor of with such that is a solution of the congruence equation (1) (i.e. the condition 2 does not hold). Thus if condition 2 holds, condition 1 must hold.
Proof of Theorem 2
Theorem 2 is the combined result of Theorem 6 and Corollary 7 in the post Defining Primitive Root. To make this post as self contained as possible, we repeat the proof, showing just the essential parts.
We do need one theorem from the previous post Defining Primitive Root. Let be a positive integer that is relatively prime to the modulus . Let be the order of modulo . Theorem 4 in this post states that for any , if and only if .
There are exactly many elements in the above set indicated by (2). So there are these many powers of . The first thing to show is that the powers are all distinct congruent modulo . Hence their least residues are also distinct.
To see this, suppose where with . We want to show . Suppose that . Since is relatively prime to , we can cancel out on both sides and obtain . Since and is a primitive root modulo , . So . Thus if , then .
The next thing to show is that is a primitive root modulo for any in the above set (2). Suppose is one such element of the set (2). Then and are relatively prime.
Let be the order of modulo . We have . Since is a primitive root modulo , it follows that (according Theorem 4 in Defining Primitive Root). Since and are relatively prime, .
On the other hand, . Since is the order of , it follows that (also using Theorem 4 in Defining Primitive Root).
With and , we have . Thus is a primitive root modulo and so is its least residue.