In this post, we define the notion of primitive root and prove some elementary results. Instead of jumping right into the definition, we take a leisurely approach by first looking at some of the related basic notions.

___________________________________________________________________________________________________________________

**Setting Up the Scene**

Two positive integers and are relatively prime if they do not share any prime factors, i.e., their greatest common divisor is one (the only positive integer that can divide both numbers is one). For example, and are relatively prime, as are and . If and are relatively prime, we also say that is relatively prime to or is relatively prime to . Our notation for greatest common divisor is .

In working with modular arithmetic where the modulus is the positive integer , every integer is congruent modulo to exactly one number in the set . The numbers in this set are called the least residues modulo . In doing modulus calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation .

An even more interesting set is the set of all integers in such that and the modulus are relatively prime. To facilitate the discussion, we describe this set as follows:

When the modulus is a prime number, , the non-zero elements of . The following theorem gives some indication why is an interesting set, which provides alternative characterizations of .

- .
- There is a such that .
- Some positive power of modulo is , i.e., for some positive integer .

**Theorem 1**-
Let be an integer in . The following conditions are equivalent.

The proof of Theorem 1 can be found in the post Euler’s phi function, part 1.

The Euler’s phi function, denoted by , is the number of integers where such that and the modulus are relatively prime. In light of the above discussion, is the number of elements in the set . It is also the case that is the number of elements in that satisfies any one of the three conditions in Theorem 1.

___________________________________________________________________________________________________________________

**Defining Primitive Root**

When we are interested in the power of a number being one congruence modulo , according to Theorem 1, the base has to be a number that is relatively prime to the modulus. We have already come across two such situations – Fermat’s little theorem and its generalization, Euler’s theorem.

**Theorem 2 (Fermat’s little theorem)**-
Let the modulus be a prime number. Then for any integer that is relatively prime to .

**Theorem 3 (Euler’s theorem)**-
It is the case that for any integer that is relatively prime to .

Theorem 2 follows from Theorem 3, which is proved in the post Euler’s phi function, part 1.

**Definitions**

We now define the notion of primitive root. Let be an integer in that is relatively prime to the modulus . Based on the above theorems, for some positive integer . By the order of modulo , we mean the least positive integer such that . The number is a primitive root modulo if the order of modulo is the number .

By Theorem 3, the order of modulo is always . We will see below that the order always divides (see Theorem 4).

One comment. The notions of order and primitive roots are defined above for integers in . In actuality, the two notations can be defined for all positive integers. It is just that we are interested in finding primitive roots among the residues, i.e., the elements of the set . In some cases, it will be helpful to think of orders of numbers outside of and think of numbers outside of as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus is a prime number. Fermat’s little theorem tells us that for any that is relatively prime to . Is the only exponent for which the power of is one? Take . The following table gives the powers of modulus where .

The above table shows that for , the number is the least exponent for which the power of is one. In other words, the order for these is . The numbers are primitive roots modulo . The other values of are not primitive roots. The order for is . The order for is . The order for is .

Note that in the above table, for the numbers that are primitive roots, the set equals the set . So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Let’s look at a modulus that is not prime. Take . The following table gives the powers of modulus where .

Note that since is the set of all the least residues that are relatively prime to . In terms of powers of , we should only focus on . The following is the reduced table.

Note that for all four . But only are primitive roots modulo .

Also note that in the above table, for the numbers that are primitive roots, the set equals the set . So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Not all moduli have primitive roots. Take . The least residues that are relatively prime to are the set . Note that for every in this set. Thus no number in this set can have order = .

___________________________________________________________________________________________________________________

**Elementary Results**

One observation can be made about the above small tables for and is that all exponents for which the power of is one are the multiples of the order. We have the following theorem.

**Theorem 4**-
Let be an integer where such that is relatively prime to the modulus . Suppose is the order of the number modulo . Then if and only if is a multiple of .

**Proof of Theorem 4**

This direction is clear. If for some integer , then .

Suppose that . By the division algorithm, we have for some integers and where . We have the following:

Since and , it must be the case that , implying that .

We have the following corollary.

**Corollary 5**-
Let be an integer where such that is relatively prime to the modulus . Suppose is the order of the number modulo . Then is a multiple of .

Another observation from the above small tables is that a primitive root, through powering, is a generator of the least residues that are relatively prime to the modulus.

- The number is a primitive root modulo .
- The set , where each is considered as the least residues modulo , is precisely the set .

**Theorem 5**-
Let be an integer where such that is relatively prime to the modulus . The following conditions are equivalent.

Recall that is the set of all such that is relatively prime to .

**Proof of Theorem 5**

Suppose that the number is a primitive root modulo . The first step in showing condition 2 is to show that the numbers in the set are distinct congruent modulo . Then it follows that their least residues modulo are distinct too.

Suppose where . We want to show that . Suppose . Then cancel out on both sides of the equation since is relatively prime to . We have . But . Since is a primitive root modulo , we cannot have . So it must be the case that . So if , then . Equivalently, if , . Thus the least residues modulo of the values in are distinct too.

Since is relatively prime to , its least residue is also relatively prime to . Now the least residues modulo of the values in consist of numbers inside , which is also a set of many numbers. So the two sets must equal.

We show the contrapositive of . Suppose that the order of modulo is where . So and . So and are two elements in the set that are congruent to each other. This means that the least residues of have less than many values. In other words, the number , through powering, cannot generate all the least residues that are relatively prime to the modulus .

The following theorem and corollary give the number of primitive root modulo as long as it is known that there is a primitive root modulo .

**Theorem 6**-
Let be a primitive root modulo . Then for any positive integer , the least residue of is a primitive root modulo if and only if is relatively prime to .

**Proof of Theorem 6**

Suppose that is not relatively prime to . So . Then we have:

With and , it follows that is not a primitive root modulo . Hence the least residue of modulo is also not a primitive root. Thus if the least residue of is a primitive root modulo , it must be that .

Suppose . Let be the order of modulo . By the definition of order, . Based on the fact that the order of modulo is , we have (also using Theorem 4). Since , it must be the case that .

On the other hand, . Using the fact that the order of is (and using Theorem 4), .

With and , it follows that . This implies that is a primitive root modulo , and so is its least residue modulo .

**Corollary 7**-
Suppose that there exists a primitive root modulo . Then there are exactly many primitive roots modulo .

**Proof of Corollary 7**

Let be a primitive root modulo . By Theorem 6, the least residue of is a primitive roots modulo if and only if is relatively prime to the number . There are precisely many such numbers .

Furthermore, according to Theorem 5, the least residues of the values in are all distinct. Thus the least residues of the powers for the many are primitive roots modulo .

**An Algorithm**

The theorems and corollaries in this post form an elementary algorithm for finding primitive roots of a modulus (if one is known to exist). The algorithm is described in the post An elementary algorithm for finding primitive roots. An example is given in the post Finding Primitive Roots.