Finding Primitive Roots

In the previous post called Defining Primitive Root, we define and discuss the notion of primitive roots and prove some elementary theorems. In this post we use these theorems to find primitive roots modulo a prime number. The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

It is a theorem that if the modulus is a prime number, there exist primitive roots modulo . But the theorem does not provide an algorithm of how to find one. We demonstrate a process of how to find all the primitive roots of a prime modulus. We use the prime modulus , a number that is small enough to make the calculation not too lengthy and is big enough to make the demonstration meaningful.

The modular arithmetic calculation discussed below can be programmed in a computer or done using a hand-held calculator using the fast powering algorithm (which is discussed in this post).

__________________________________________________________________________________________________________________

Background

For any positive integer , let be the set . Let be the set of all numbers in that is relatively prime to . Euler’s phi function is the count of the elements in the set . Euler’s theorem states that for any , .

Euler’s theorem establishes a solution for the congruence equation where is a positive integer. Whenever is the smallest positive solution to , the number is said to be a primitive root modulo .

In general, the smallest positive solution to the equation is called the order of modulo . Thus, in terms of the notion of order, any number is a primitive root modulo whenever the order of and coincide.

__________________________________________________________________________________________________________________

Finding One Primitive Root

For the modulus , and . So . According to Euler’s theorem, for all .

Obviously can never be a primitive root. Thus candidates for primitive roots are the numbers in the set . As we will see below, we only need to find one primitive root from this list. Our plan is to find the smallest primitive root from this list.

Since , showing that is a primitive root modulo requires verifying that for each . We can get by with less computation.

If is the smallest positive integer solution to , then (see Theorem 4 and Corollary 5 in the post Defining Primitive Root).

So the order of a number can only be the numbers in the set that are divisors of . If for all such , then the number is a primitive root modulo . If for one such , then the number is not a primitive root modulo . This is the approach we take to find one primitive root modulo .

Note that , which has eleven divisors that are less than . They are:

We start with and check where is from the above list of divisors. The first where for all eleven is a primitive root.

We have the following calculation:

So are not primitive root modulo . For , for all eleven . Thus is the smallest primitive root modulo .

__________________________________________________________________________________________________________________

Finding the Other Primitive Roots

If there is one primitive root for a modulus , there are exactly many primitive roots (see Corollary 7 in the post Defining Primitive Root). For the modulus , there are primitive roots.

Theorem 6 in that same post says that if is a primitive root modulo , then (or the least residue of it) is also a primitive root for all integers that are relatively prime to .

So in this example, for the exponents we only need to find the numbers in the set that are relatively prime to .

To find the numbers that are relatively prime to , we can list out the numbers . Since the prime factors of are , we cross out the multiples of , the multiples of , and finally the multiples of . The following matrix shows the numbers that remain.

From the last section, we know that is a primitive root modulo . For each number in the above matrix, we calculate the least residue of modulo . The following shows the results.

For example, the following calculation gives the ten results in the first row of the above matrix.

The following matrix shows the primitive roots sorted in increasing order.

__________________________________________________________________________________________________________________

Exercise

We leave with an exercise (for any interested reader).

Find all the primitive roots modulo . Answers are show below.

The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Advertisements