The primitive root theorem identifies all the positive integers for which primitive roots exist. The list of such integers is a restrictive list. This post along with two previous posts give a complete proof of this theorem using only elementary number theory. We prove the following theorem.

Main Theorem (The Primitive Root Theorem)

There exists a primitive root modulo if and only if , , or where is an odd prime number and is a positive integer.
The theorem essentially gives a list of the moduli that have primitive roots. Any modulus outside this restrictive list does not have primitive roots. For example, any integer that is a product of two odd prime factors is not on this list and hence has no primitive roots. In the post Primitive roots of powers of odd primes, we show that the powers of an odd prime have primitive roots. In the post Primitive roots of twice the powers of odd primes, we show that the moduli that are twice the power of an odd prime have primitive roots. It is easy to verify that the moduli and have primitive roots. Thus the direction of the primitive root theorem has been established. In this post we prove the direction , showing that if there exists a primitive root modulo , then must be one of the moduli in the list stated in the theorem.
___________________________________________________________________________________________________________________
LCM
The proof below makes use of the notion of the least common multiple. Let and be positive integers. The least common multiple of and is denoted by and is defined as the least positive integer that is divisible by both and . For example, . We can also express as follows:
where is the greatest common divisor of and . The above formula reduces the calculation of LCM to that of calculating the GCD. To compute the LCM of two numbers, we can simply remove the common prime factors between the two numbers. When the number and are relatively prime, i.e., , we have .
Another way to look at LCM is that it is the product of multiplying together the highest power of each prime number. For example, and . Then .
The least common divisor of the numbers is denoted by and is defined similarly. It is the least positive integer that is divisible by all . Since the product of all the numbers is one integer that is divisible by each , we have:
As in the case of two numbers, the LCM of more than two numbers can be thought as the product of multiplying together the highest power of each prime number. For example, the LCM of , and is .
For a special case, there is a simple expression of LCM.

Lemma 1

Let be positive integers.
Then if and only if the numbers are pairwise relatively prime, i.e., and are relatively prime whenever .
Proof of Lemma 1
Suppose the numbers are pairwise relatively prime. Then there are no common prime factors in common between any two numbers on the list. Then multiplying together the highest power of each prime factor is the same as multiplying the individual numbers .
Suppose and are not relatively prime for some . As a result, . It follows that
To give a sense of why the above is true, let’s look at a simple case of where is a prime number and . Assume that , and is part of the prime factorization of . Furthermore, note that is identical to . The following derivation confirms (3):
With the above clarification, the lemma is established.
___________________________________________________________________________________________________________________
Other Tools
We need to two more lemmas to help us prove the main theorem.

Lemma 2

Let and be positive integers that are relatively prime. Then and if and only if .

Lemma 3

The number is a primitive root modulo if and only if for all prime divisors of .
Lemma 2 a version of the Chinese Remainder Theorem and is proved a previous post (see Theorem 2 in Primitive roots of twice the powers of odd primes or see Theorem 2 in Proving Chinese Remainder Theorem). Lemma 3 is also proved in a previous post (see Lemma 2 in More about checking for primitive roots).
___________________________________________________________________________________________________________________
Breaking It Up Into Smaller Pieces
The proof of the direction of the primitive root theorem is done in the following lemmas and theorems.

Lemma 4

Let be the prime factorization of the positive integer . Let be a primitive root modulo . Then the numbers are pairwise relatively prime.
Proof of Lemma 4
Note that is relatively prime to . So is relatively prime to each . By Euler’s theorem, we have for each . Let .
By definition of LCM, for each . So for each . By the Chinese remainder theorem (Lemma 2 above), . Since is a primitive root modulo , it must be that . Interestingly, we have:
Thus . By Lemma 1, the numbers are relatively prime.
The following theorems follow from Lemma 4. The main theorem is a corollary of these theorems.

Theorem 5

If there exists a primitive root modulo , then cannot have two distinct prime divisors.
Proof of Theorem 5
Let be the prime factorization of where .
If and are odd prime with , then and are both even and thus not relatively prime. If there exists a primitive root modulo , and must be relatively prime (see Lemma 4). Since we assume that there exists a primitive root modulo , cannot have two distinct odd prime divisors.

Theorem 6

Suppose that there exists a primitive root modulo and that has exactly one odd prime factor . Then must be of the form or where .
Proof of Theorem 6
By Theorem 5, the prime factorization of must be where and .
We claim that or . Suppose . Then and are both even and thus not relatively prime. Lemma 4 tells us that there does not exist a primitive root modulo . So if there exists a primitive root modulo , then it must be the case that or .
If , then . If , then .

Lemma 7

Let where . Then for any that is relatively prime to .
Proof of Lemma 7
We prove this by induction on . Let . Then and . For any odd with , it can be shown that .
Suppose that the lemma holds for where . We show that it holds for . Note that and . Since the lemma holds for , we have for any that is relatively prime to . We can translate this congruence into the equation for some integer .
Note that and . It is also the case that . Thus we have:
The above derivation shows that for any that is relatively prime to .
On the other hand, is relatively prime to if and only if is relatively prime to . So for any that is relatively prime to . Thus the lemma is established.
Theorem 8

Suppose that there exists a primitive root modulo and that where . Then where or .
Proof of Theorem 8
Suppose where . By Lemma 7, for any relatively prime to . Since is the only prime divisor of , by Lemma 3, there cannot be primitive root modulo . Thus if there exists a primitive root modulo and that where , then the exponent can be at most .
___________________________________________________________________________________________________________________
Putting It All Together
We now put all the pieces together to prove the of the Main Theorem. It is a matter of invoking the above theorems.
Proof of Main Theorem
Suppose that there exists a primitive root modulo . Consider the following three cases about the modulus .
 has no odd prime divisor.
 has exactly one odd prime divisor.
 has at least two odd prime divisors.
Suppose Case 1 is true. Then where . By Theorem 8, or .
Suppose Case 2 is true. Then Theorem 6 indicates that must be the power of an odd prime or twice the power of an odd prime.
Theorem 5 indicates that Case 3 is never true. Thus the direction of the Main Theorem is proved.
___________________________________________________________________________________________________________________
Pingback: The primitive root theorem revisited  Exploring Number Theory