The primitive root theorem lists out all possible values of for which primitive roots exist in the modulo arithmetic. The theorem is proved in this previous post and several blog posts leading to it. In this post, we reorganize the proof and add some additional information. The proof of the primitive root theorem detailed below shows that the list of values of the moduli is very restrictive and, in addition, that such moduli are such that there are no extra square root beside 1 and -1. The crux of the argument is a lemma that indicates that most moduli have a third square root of 1 in addition to 1 and -1. The proof is also an opportunity for applying the Chinese remainder theorem (usually abbreviated CRT).
The primitive root theorem
In this post, is a positive integer that serves as the modulus. Given , it is of interest to know all the integers where and that and the modulus are relatively prime. The number of such values of is denoted by (this is called the phi function). For example, for , . For , since there are only 4 numbers that are relatively prime to 10, namely 1, 3, 7, and 9.
A positive integer is said to be a primitive root modulo if is the least positive integer such that . If is said to be a primitive root modulo , it is necessary that and the modulus are relatively prime. This is because of this basic fact: and the modulus are relatively prime if and only if and only of for some integer . The middle condition is saying that has a multiplicative modulo .
The following lemma is alluded to at the beginning. The idea will used through the proof of the primitive root theorem. So it is extracted as a lemma to make the argument easier to follow.
Let and be integers such that and and such that and are relatively prime. Let . Then there exist such that and such that , i.e. is a third square root of 1 modulo that is neither 1 nor -1.
Consider the two equations and . By the Chinese remainder theorem, there is a solution to this system of equations. We have and . By the Chinese remainder theorem again, . There are three possibilities for , 1, -1 or another value. If , then , which means , contradicting that . Similarly, would lead to , which contradicts . The only possibility is that .
The proof of Lemma 1 makes use of CRT twice. Lemma 1 will be used several times in the proof of in the primitive root theorem.
The Primitive Root Theorem
Let be a positive integer. Then the following conditions are equivalent:
- There exists a primitive root modulo .
- The equation has no solution outside of modulo . In other words, the only square roots of 1 modulo are .
- The only possibilities for are:
- is the power of an odd prime,
- is twice the power of an odd prime.
Suppose that is a primitive root modulo . Suppose that condition 2 does not hold. As a result, there exists some positive integer such that . Since is a primitive root modulo , for some integer integer with (see Theorem 5 here). If , then . Thus .
Furthermore, . We have , since is the least power such that is congruent to 1 modulo . Since , . We have since is the least power such that is congruent to 1 modulo . The last inequality leads to , contradicting the earlier observation of . Thus condition 2 must holds if condition 1 is true.
We show that for any outside of the four possibilities listed in condition 3, condition 2 does not hold. This means that if condition 2 holds for , must be one of the four possibilities. We consider the cases of even and odd separately.
Case 1. The modulus is odd. Since is not the power of one single odd prime, it must be the product of two or more powers of odd primes. Let where a power of an odd prime and is the product of one ore more powers of odd primes. It is clear that and are relatively prime. It is also the case that and since each of them has at least one odd prime factor. By Lemma 1, there exists a square root of 1 such that .
For the second case, is even. We break this up into two cases. One is that is a power of 2. The other is that is not a power of 2. In these two cases, the goal is still to show that if is outside of the four possibilities in condition 3, then condition 2 does not hold.
Case 2a. The modulus is a power of 2.
Then where . In this case, we can actually exhibit a square root that is neither 1 nor -1. Define . Since , . Consider the following derivation:
The above derivation shows that . It is clear that .
Case 2b. The modulus is not a power of 2.
Since is even and is not a power of 2, it must be that where is odd. Either is the power of an odd prime or it is not. If is the power of an odd prime, then . If is not the power of an odd prime (i.e. is of case 1 above), then . To make the argument clear, we consider the two sub cases separately.
Case 2b-1. The modulus where , and is an odd prime.
Let and . Note that . By Lemma 1, there exists a square root of 1 modulo such that .
Case 2b-2. The modulus where and is an odd integer that is not the power of an odd prime.
Consider the prime factorization of , say where . Let and . We can also apply Lemma 1 to obtain a square root of 1 modulo that is neither 1 nor -1.
Lemma 1 plays a prominent role in the proof of the direction . Lemma 1 shows that it is easy to find moduli that have a third square root of 1 (other than 1 and -1). As the primitive root theorem shows, having a third square root of 1 is the condition that kills the possibility of having a primitive root. Lemma 1 and the primitive root theorem speak to different sides of the same coin. One tells us that moduli with no primitive roots are easy to find. The other says that only in rare cases do you find moduli that admit primitive roots, namely the moduli that are not product of two factors, each of which is greater than 2, that are relatively prime. The proof of may seem tedious (by listing out all cases that satisfy Lemma 1). The key to understanding the proof is through Lemma 1.