In this post we show that if is prime, then there exists a primitive root modulo . It follows that there exist primitive roots modulo where is Euler’s phi function.
For a basic discussion of the notion of primitive roots, see Defining Primitive Root. A basic discussion of the phi function is found in the post Euler’s phi function, part 1 and in the post Euler’s phi function, part 2.
In modular arithmetic, not all moduli have primitive roots. For example, for the modulus , the least residues that are relatively prime are . Thus . For each one of these values of , . Thus every one of them has order . Thus there are no primitive roots modulo . We prove the following results.
Let be a prime number. Then there exists a primitive root modulo .
Let be a prime number. Then there are exactly many primitive roots modulo .
Theorem 1 is the main theorem in this post. Theorem 2 follows from Theorem 1 and from a result proved in a previous post. The previous result is that if there exists a primitive root modulo (not necessarily prime), then there exist exactly many primitive roots modulo (see Theorem 6 and Corollary 7 in Defining Primitive Root). Since Theorem 1 provides the existence of a primitive root, Theorem 2 follows from Theorem 1 and from the previous result and from the fact that for any prime number.
Proving the Main Theorem
Our proof of the existence of a primitive root of any prime modulus uses only elementary techniques. Most of the results we need are developed here in this post. The first result is proved in a previous post (see Theorem 4 in Defining Primitive Root).
Let be an integer with such that is relaively prime to the modulus . Let be the order of modulo . Then the following two conditions are equivalent for any positive integer .
- The congruence condition holds.
- The number is a divisor of .
The second result is that of polynomial congruence. Let be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation .
Let be a prime number. Let be a polynomial of degree . Then the equation
has at most solutions.
Proof of Lemma 4
Suppose where . We prove the lemma by induction on the degree .
Suppose . We have . Since is prime and , the coefficient must be relatively prime to . Then the congruence equation has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of and the modulus (see Theorem 2 in the post Solving Linear Congruences).
Suppose the lemma is true for polynomials of degree . Consider two cases – either equation (1) has no solution or equation (1) has a solution. If the first case is true, then the conclusion of the lemma is true.
Suppose the second case is true. Suppose is a solution to equation (1). It follows that and that is a least residue modulo .
Our next goal is to factor the polynomial into a product of a first degree polynomial and a polynomial of degree . To this end, note that is a factor of for . We have the following derivation
where is a polynomial of degree .
Whenever , we have . Using the fact that is prime and Euclid’s lemma, either or . In terms of congruence, either or . The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most solutions. Together, equation (1) has at most solutions.
Let be a prime number. If , then the congruence equation has exactly many solutions.
Proof of Lemma 5
Suppose . Fermat’s little theorem tells us that has exactly solutions, namely . We can factor the polynomial as follows:
Let . Whenever , . By Euclid’s lemma, or . In terms of congruence, or .
By Lemma 4, the congruence has at most solutions. Since has exactly solutions, the congruence equation has at least many solutions.
By Lemma 4, the congruence equation has at most solutions. Thus has exactly many solutions.
We need one more lemma before proving Theorem 1.
Let and be integers with . Let be the order of modulo . Let be the order of modulo .
Suppose that and are relatively prime. Then is the order of modulo .
Proof of Lemma 6
Let be the order of modulo . We show that . The following derivation shows that .
Since , we have (by Lemma 3). Since and are relatively prime, . By a symmetrical argument, it can also be shown that .
Since , we have for some integer . Since , it follows that (Euclid’s lemma). So for some integer . Now . This means that .
On the other hand, we have . This follows from the following derivation and from Lemma 3.
It follows that .
Lemma 6 indicates that the orders of two numbers are multiplicative as long as the two orders are relatively prime. As a corollary of Lemma 6, it follows that the order of a product of finitely many numbers (for the same modulus) is the product of the individual orders provided that the orders are pairwise relatively prime. This fact will be used in the proof of Theorem 1 below.
Proof of Theorem 1
We start off with a prime factorization of the number .
In the above factorization, the numbers are distinct prime numbers and the exponents .
For each , it is clear that . By Lemma 5, the congruence equation
has exactly many solutions. Note that the many solutions are integers in the interval . Furthermore, the order modulo of each of these solutions to (2) is a divisor of (by Lemma 3).
In fact, from Lemma 3, we can say that for any integer in the interval , the number is a solution of equation (2) if and only if the order modulo of is a divisor of . We have the following claim.
For each , we claim that there exists at least one integer in the interval such that the order of modulo is .
To see the above claim, the congruence equation
has exactly many solutions in the interval (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of .
In fact, from Lemma 3, we can also say that for any integer in the interval , the number is a solution of equation (3) if and only if the order modulo of is a divisor of .
Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of are also divisors of .
Thus there are many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it . Let be the order of modulo . There are three possibilities for :
Since is a solution to (2), the number is a divisor of . Note that there are no divisors of within the interval since is a prime number. So is not possible.
Since is not a solution to (3), the number is not a divisor of . This means that is not possible. Since is prime, must be a power of . Since must be a power of , if , is then a divisor of .
So the only possibility is that . This establishes the above claim.
Let . The primitive root modulo we are looking for is either if or the least residue of if .
According to the above claim, the order modulo of is . Clearly and are relatively prime for . As a corollary of Lemma 6, the order of the product is the products of , namely . Thus or its least residue modulo is a primitive root.