The primitive root theorem

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 m if and only if m=2, m=4, m=p^t or m=2p^t where p is an odd prime number and t 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 2 and 4 have primitive roots. Thus the direction \Longleftarrow of the primitive root theorem has been established. In this post we prove the direction \Longrightarrow, showing that if there exists a primitive root modulo p, then p 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 a and b be positive integers. The least common multiple of a and b is denoted by \text{LCM}(a,b) and is defined as the least positive integer that is divisible by both a and b. For example, \text{LCM}(16,18)=144. We can also express \text{LCM}(a,b) as follows:

    \displaystyle \text{LCM}(a,b)=\frac{a \cdot b}{\text{GCD}(a,b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where \text{GCD}(a,b) is the greatest common divisor of a and b. 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 a and b are relatively prime, i.e., \text{GCD}(a,b)=1, we have \displaystyle \text{LCM}(a,b)=a \cdot b.

Another way to look at LCM is that it is the product of multiplying together the highest power of each prime number. For example, 48=2^4 \cdot 3 and 18=2 \cdot 3^2. Then \text{LCM}(16,18)=2^4 \cdot 3^2=144.

The least common divisor of the numbers a_1,a_2,\cdots,a_n is denoted by \text{LCM}(a_1,a_2,\cdots,a_n) and is defined similarly. It is the least positive integer that is divisible by all a_j. Since the product of all the numbers a_j is one integer that is divisible by each a_k, we have:

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le a_1 \cdot a_2 \cdots a_n  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

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 48=2^4 \cdot 3, 18=2 \cdot 3^2 and 45=3^2 \cdot 5 is 2^4 \cdot 3^2 \cdot 5=720.

For a special case, there is a simple expression of LCM.

    Lemma 1

      Let a_1,a_2,\cdots,a_n be positive integers.

      Then \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=a_1 \cdot a_2 \cdots a_n if and only if the numbers a_1,a_2,\cdots,a_n are pairwise relatively prime, i.e., a_i and a_j are relatively prime whenever i \ne j.

Proof of Lemma 1
\Longleftarrow
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 a_1,a_2 \cdots,a_n.

\Longrightarrow
Suppose a_i and a_j are not relatively prime for some i \ne j. As a result, d=\text{GCD}(a_i,a_j)>1. It follows that

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le \frac{a_1 \cdot a_2 \cdots a_n}{d} < a_1 \cdot a_2,\cdots a_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

To give a sense of why the above is true, let’s look at a simple case of d=\text{GCD}(a_i,a_j)=p^u where p is a prime number and u \ge 1. Assume that a_i=a_1, a_j=a_2 and p^u is part of the prime factorization of a_1. Furthermore, note that \displaystyle \text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) is identical to \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n). The following derivation confirms (3):

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=\text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) \le \frac{a_1}{p^u} \cdot a_2 \cdots a_n < a_1 \cdot a_2,\cdots a_n

With the above clarification, the lemma is established. \blacksquare

___________________________________________________________________________________________________________________

Other Tools

We need to two more lemmas to help us prove the main theorem.

    Lemma 2

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).
    Lemma 3

      The number a is a primitive root modulo m if and only if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m).

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 \Longrightarrow of the primitive root theorem is done in the following lemmas and theorems.

    Lemma 4

      Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of the positive integer m. Let a be a primitive root modulo m. Then the numbers \phi(p_1^{e_1}), \phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}) are pairwise relatively prime.

Proof of Lemma 4
Note that a is relatively prime to m. So a is relatively prime to each p_j^{e_j}. By Euler’s theorem, we have \displaystyle a^{\phi(p_j^{e_j})} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. Let \displaystyle W=\text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t})).

By definition of LCM, \phi(p_j^{e_j}) \ \lvert \ W for each j. So \displaystyle a^{W} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. By the Chinese remainder theorem (Lemma 2 above), \displaystyle a^{W} \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it must be that \phi(m) \le W. Interestingly, we have:

    \displaystyle \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})=\phi(m) \le W \le \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})

Thus \displaystyle \text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}))=\phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t}). By Lemma 1, the numbers \phi(p_j^{e_j}) are relatively prime. \blacksquare

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 m, then m cannot have two distinct prime divisors.

Proof of Theorem 5
Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of m where t \ge 2.

If p_i and p_j are odd prime with i \ne j, then \phi(p_i^{e_i})=p_i^{e_i-1}(p_i-1) and \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1) are both even and thus not relatively prime. If there exists a primitive root modulo m, \phi(p_i^{e_i}) and \phi(p_j^{e_j}) must be relatively prime (see Lemma 4). Since we assume that there exists a primitive root modulo m, m cannot have two distinct odd prime divisors. \blacksquare

    Theorem 6

      Suppose that there exists a primitive root modulo m and that m has exactly one odd prime factor p. Then m must be of the form p^e or 2p^e where e \ge 1.

Proof of Theorem 6
By Theorem 5, the prime factorization of m must be m=2^{e_1} p^{e_2} where e_1 \ge 0 and e_2 \ge 1.

We claim that e_1=0 or e_1=1. Suppose e_1 \ge 2. Then \phi(2^{e_1})=2^{e_1-1} and \phi(p^{e_2})=p^{e_2-1}(p-1) are both even and thus not relatively prime. Lemma 4 tells us that there does not exist a primitive root modulo m. So if there exists a primitive root modulo m, then it must be the case that e_1=0 or e_2=1.

If e_1=0, then m=p^{e_2}. If e_1=1, then m=2p^{e_2}. \blacksquare

    Lemma 7

      Let n=2^k where k \ge 3. Then \displaystyle a^{\frac{\phi(n)}{2}} \equiv 1 \ (\text{mod} \ n) for any a that is relatively prime to n.

Proof of Lemma 7
We prove this by induction on k. Let k=3. Then n=8 and \displaystyle \frac{\phi(8)}{2}=2. For any odd a with 1 \le a <8, it can be shown that a^2 \equiv 1 \ (\text{mod} \ 8).

Suppose that the lemma holds for k where k \ge 3. We show that it holds for k+1. Note that \phi(2^k)=2^{k-1} and \displaystyle \frac{\phi(2^k)}{2}=2^{k-2}. Since the lemma holds for k, we have \displaystyle v^{2^{k-2}} \equiv 1 \ (\text{mod} \ 2^k) for any v that is relatively prime to 2^k. We can translate this congruence into the equation v^{2^{k-2}}=1+2^k y for some integer y.

Note that \phi(2^{k+1})=2^{k} and \displaystyle \frac{\phi(2^{k+1})}{2}=2^{k-1}. It is also the case that (v^{2^{k-2}})^2=v^{2^{k-1}}. Thus we have:

    \displaystyle v^{2^{k-1}}=(1+2^k y)^2=1+2^{k+1} y+2^{2k} y^2=1+2^{k+1}(y+2^{k-1} y^2)

The above derivation shows that \displaystyle v^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any v that is relatively prime to 2^k.

On the other hand, a is relatively prime to 2^{k+1} if and only if a is relatively prime to 2^k. So \displaystyle a^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any a that is relatively prime to 2^{k+1}. Thus the lemma is established. \blacksquare

    Theorem 8

      Suppose that there exists a primitive root modulo m and that m=2^e where e \ge 1. Then m=2^e where e=1 or e=2.

Proof of Theorem 8
Suppose m=2^e where e \ge 3. By Lemma 7, \displaystyle a^{\frac{\phi(m)}{2}} \equiv 1 \ (\text{mod} \ n) for any a relatively prime to m. Since 2 is the only prime divisor of m, by Lemma 3, there cannot be primitive root modulo m. Thus if there exists a primitive root modulo m and that m=2^e where e \ge 1, then the exponent e can be at most 2. \blacksquare

___________________________________________________________________________________________________________________

Putting It All Together

We now put all the pieces together to prove the \Longrightarrow 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 m. Consider the following three cases about the modulus m.

  1. m has no odd prime divisor.
  2. m has exactly one odd prime divisor.
  3. m has at least two odd prime divisors.

\text{ }
Suppose Case 1 is true. Then m=2^e where e \ge 1. By Theorem 8, m=2 or m=4.

Suppose Case 2 is true. Then Theorem 6 indicates that m 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 \Longrightarrow of the Main Theorem is proved. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

More about checking for primitive roots

Finding primitive roots modulo a number is of great interest in number theory, both in a theoretical standpoint and in a computational standpoint. In this post we compare and contrast three different ways of checking for primitive roots, continuing a discussion in an earlier post An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Background

Let m be a positive integer. Let a be a positive integer that is relative prime to m. Let \phi be Euler’s phi function, which counts the number of least residues that are relatively prime to the modulus. For example, \phi(6)=2 as 1 and 5 are the only numbers relatively prime to 6 (out of the numbers 0,1,2,3,4,5). Furthermore, \phi(p)=p-1 for any prime number p. Previous posts on the phi function: Euler’s phi function, part 1 and Euler’s phi function, part 2.

Euler’s theorem tells us that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). By the order of a modulo m we mean the least positive exponent k such that a^{k} \equiv 1 \ (\text{mod} \ m) (Euler’s theorem indicates that this notion of order is well defined). The number a is said to be a primitive root modulo m if the order of a modulo m is \phi(m).

___________________________________________________________________________________________________________________

Three Checks

Let m be a positive integer. Let a be a positive integer that is relative prime to m. How can we determine whether the number a is a primitive root modulo m? We discuss three ways of answering this question.

    ____________________________________________________________________________________________
    Check # 1

      Check a^j \ (\text{mod} \ m) for all positive integers j<\phi(m).

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 1 is merely a restatement of the definition of primitive root. It is a dumb test as it requires too much calculation. For large moduli, it would be an inefficient method of checking for primitive roots. The following is a much better test.

    ____________________________________________________________________________________________
    Check # 2

      Check a^j \ (\text{mod} \ m) for all positive divisors j of \phi(m) with j<\phi(m).

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 2 narrows down the checking by quite a bit – simply checking a^j among the divisors of \phi(m). This works because the only possible numbers for the order modulo m of the number a are the divisors of \phi(m). So we can skip all j that are not divisors of \phi(m). The following lemma shows why this is so. Actually, the lemma proves something more general. It shows that if a^n \equiv 1 \ (\text{mod} \ m), then the order of a must be a divisor of n. Euler’s theorem says that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). So the order of a must be a divisor of \phi(m).

    Lemma 1

      Let k be the order of a modulo m. If a^n \equiv 1 \ (\text{mod} \ m), then k \ \lvert \ n.

Proof of Lemma 1
We have k \le n since k is least with the property a^k \equiv 1 \ (\text{mod} \ m). By the division algorithm, we have n=q \cdot k+r where q is some integer and 0 \le r <k. We have the following:

    1 \equiv a^{n} \equiv a^{q \cdot k+r} \equiv (a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

With a^r \equiv 1 \ (\text{mod} \ m) and r < k, it follows that r=0 and n=q \cdot k. Thus k is a divisor of n. \blacksquare

Though Check # 2 is definitely an improvement over Check # 1, the following further narrows the list of exponents to check.

    ____________________________________________________________________________________________
    Check # 3

      Find all prime divisors q of \phi(m). Then compute \displaystyle j=\frac{\phi(m)}{q} over all q.

      Check a^j \ (\text{mod} \ m) for all j calculated above.

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 3 further eliminates the exponents to try when we check a^j \ (\text{mod} \ m). Instead of checking over all the divisors of \phi(m), we only need to try the divisors of the form \displaystyle \frac{\phi(m)}{q} where q is a prime divisor of \phi(m). The following lemma shows why this works.

    Lemma 2

      The number a is a primitive root modulo m if and only if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m).

Proof of Lemma 2
The direction \Longrightarrow is clear.

To show \Longleftarrow, suppose a is not a primitive root modulo m. Then
\displaystyle a^{t} \equiv 1 \ (\text{mod} \ m) for some t that is a divisor of \phi(m). We have \phi(m)=t \cdot y for some integer y. Let q be a prime factor of y. Then \phi(m)=t \cdot q \cdot b for some integer b. Consider the following derivation.

    \displaystyle 1 \equiv (a^t)^b =(a^{\frac{\phi(m)}{qb}})^b \equiv a^{\frac{\phi(m)}{q}} \ (\text{mod} \ m)

Thus if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m), then a must be a primitive root modulo m. \blacksquare

___________________________________________________________________________________________________________________

Examples

We now work some examples using Check # 3. The modular arithmetic is done using an online calculator. It can also be done using the fast powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm).

Example 1
Consider m=37. Find all primitive roots modulo m=37.

First \phi(37)=36. The divisors of 36 are:

    1,2,3,4,6,9,12,18,36

To use Check # 2, in order to find out if a is a primitive root, we would need to calculate a^j nine times, one for each of the above divisors of \phi(37)=36.

To use Check # 3, only two of these nine divisors are needed. There are two prime divisors of 36, namely 2 and 3. We use \displaystyle \frac{36}{2}=18 and \displaystyle \frac{36}{3}=12. So we check a^{12} and a^{18} modulo 37. The calculation is presented in the following tables.

    \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&1  \\ 2&\text{ }&26&\text{ }&36  \\ 3&\text{ }&10&\text{ }&1  \\ 4&\text{ }&10&\text{ }&1  \\ 5&\text{ }&10&\text{ }&36  \\ 6&\text{ }&1&\text{ }&36 \\ 7&\text{ }&10&\text{ }&1 \\ 8&\text{ }&1&\text{ }&36 \\ 9&\text{ }&26&\text{ }&1 \\ 10&\text{ }&1&\text{ }&1   \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 11&\text{ }&1&\text{ }&1  \\ 12&\text{ }&26&\text{ }&1  \\ 13&\text{ }&10&\text{ }&36  \\ 14&\text{ }&1&\text{ }&36  \\ 15&\text{ }&26&\text{ }&36  \\ 16&\text{ }&26&\text{ }&1 \\ 17&\text{ }&26&\text{ }&36 \\ 18&\text{ }&10&\text{ }&36 \\ 19&\text{ }&10&\text{ }&36 \\ 20&\text{ }&26&\text{ }&36   \end{bmatrix}

    \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 21&\text{ }&26&\text{ }&1  \\ 22&\text{ }&26&\text{ }&36  \\ 23&\text{ }&1&\text{ }&36  \\ 24&\text{ }&10&\text{ }&36  \\ 25&\text{ }&26&\text{ }&1  \\ 26&\text{ }&1&\text{ }&1 \\ 27&\text{ }&1&\text{ }&1 \\ 28&\text{ }&26&\text{ }&1 \\ 29&\text{ }&1&\text{ }&36 \\ 30&\text{ }&10&\text{ }&1   \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 31&\text{ }&1&\text{ }&36  \\ 32&\text{ }&10&\text{ }&36  \\ 33&\text{ }&10&\text{ }&1  \\ 34&\text{ }&10&\text{ }&1  \\ 35&\text{ }&26&\text{ }&36  \\ 36&\text{ }&1&\text{ }&1 \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ }  \end{bmatrix}

The primitive roots are the rows with both congruences \not \equiv 1. They are:

    2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35

One comment about the above tables. The non-one values in the above table seem to follow a pattern. In the columns for the calculation for a^{18}, the values are either 1 or 36. The non-one value is 36. It turns out that it has order 2 modulo 37. The non-one values in the columns for a^{12} are 10 and 26. It turns out that they have order 3 modulo 37. See the exercise stated below.

Example 2
Consider m=17. Find all primitive roots modulo m=17.

Since \phi(17)=16=2^4, the only prime divisor of $latex \phi(17) is 2. We use \displaystyle \frac{16}{2}=8. For any a, we only need to calculate a^8.

    \displaystyle \begin{bmatrix} a&\text{ }&a^{8}&\text{ }&a&\text{ }&a^{8}  \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&11&\text{ }&16  \\ 2&\text{ }&1&\text{ }&12&\text{ }&16  \\ 3&\text{ }&16&\text{ }&13&\text{ }&1  \\ 4&\text{ }&1&\text{ }&14&\text{ }&16  \\ 5&\text{ }&16&\text{ }&15&\text{ }&1  \\ 6&\text{ }&16&\text{ }&16&\text{ }&1 \\ 7&\text{ }&16&\text{ }&\text{ } \\ 8&\text{ }&1&\text{ }&\text{ } \\ 9&\text{ }&1&\text{ }&\text{ } \\ 10&\text{ }&16&\text{ }&\text{ }     \end{bmatrix}

The primitive roots modulo 17 are:

    3, 5, 6, 7, 10, 11, 12, 14

Note that the non-one value 16 in the above table has order 2 modulo 17. See the exercise below.

___________________________________________________________________________________________________________________

Special Case

Based on Example 2, the following is a special case for Check # 3.

    ____________________________________________________________________________________________
    Check # 3 (A Special Case)

      Let p be a prime such that p-1=2^n for some positive integer n.

      Note that 2 is the only prime divisor of \phi(p)=p-1.

      Check a^j \ (\text{mod} \ p) where \displaystyle j=\frac{p-1}{2}.

      If a^j \not \equiv 1, then the number a is a primitive root modulo p.

    ____________________________________________________________________________________________

___________________________________________________________________________________________________________________

Exercise

This is the exercise mentioned at the end of Example 1.

Let p be a prime number. Let q be a prime divisor of p-1. Let a be an integer with 1 \le a \le p-1. Show that the number \displaystyle a^{\frac{p-1}{q}} is either \equiv 1 or has order q modulo p.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of prime moduli

In this post we show that if m is prime, then there exists a primitive root modulo m. It follows that there exist \phi(m-1) primitive roots modulo m where \phi 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 m=8, the least residues that are relatively prime are a=1,3,5,7. Thus \phi(8)=4. For each one of these values of a, a^2 \equiv 1 \ (\text{mod} \ 8). Thus every one of them has order 2 < \phi(8). Thus there are no primitive roots modulo m=8. We prove the following results.

    Theorem 1

      Let p be a prime number. Then there exists a primitive root modulo p.

    \text{ }

    Theorem 2

      Let p be a prime number. Then there are exactly \phi(m-1) many primitive roots modulo m.

\text{ }

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 m (not necessarily prime), then there exist exactly \phi(\phi(m)) many primitive roots modulo m (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 \phi(p)=p-1 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).

    Lemma 3

      Let a be an integer with 0 \le a \le m-1 such that a is relaively prime to the modulus m. Let k be the order of a modulo m. Then the following two conditions are equivalent for any positive integer n.

      1. The congruence condition a^n \equiv 1 \ (\text{mod} \ m) holds.
      2. The number k is a divisor of n.

The second result is that of polynomial congruence. Let f(x) be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation f(x) \equiv 0 \ (\text{mod} \ m).

    Lemma 4

      Let m be a prime number. Let f(x) be a polynomial of degree n. Then the equation

        f(x) \equiv 0 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

      \text{ }

      has at most n solutions.

Proof of Lemma 4

Suppose f(x)=a_n x^n +a_{n-1} x^{n-1} + \cdots+a_2 x^2+a_1 x + a_0 where a_n \not \equiv 0 \ (\text{mod} \ m). We prove the lemma by induction on the degree n.

Suppose n=1. We have f(x)=a_1 x +a_0 \equiv 0 \ (\text{mod} \ m). Since m is prime and a_1 \not \equiv 0 \ (\text{mod} \ m), the coefficient a_1 must be relatively prime to m. Then the congruence equation a_1 x +a_0 \equiv 0 \ (\text{mod} \ m) has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of x and the modulus m (see Theorem 2 in the post Solving Linear Congruences).

Suppose the lemma is true for polynomials of degree n-1. 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 b is a solution to equation (1). It follows that f(b) \equiv 0 \ (\text{mod} \ m) and that b is a least residue modulo m.

Our next goal is to factor the polynomial f(x) into a product of a first degree polynomial and a polynomial of degree n-1. To this end, note that x-b is a factor of x^w-b^w for w=1,2,3,\cdots,n. We have the following derivation

    \displaystyle \begin{aligned} f(x)&\equiv f(x)-f(b) \\&\equiv a_n (x^n-b^n) +a_{n-1} (x^{n-1}-b^{n-1}) + \cdots+a_2 (x^2-b^2)+a_1 (x-b) \\&\equiv (x-b) \cdot h(x) \ (\text{mod} \ m) \end{aligned}

where h(x) is a polynomial of degree n-1.

Whenever f(x) \equiv 0 \ (\text{mod} \ m), we have m \ \lvert \ (x-b) \cdot h(x). Using the fact that m is prime and Euclid’s lemma, either m \ \lvert \ (x-b) or m \ \lvert \ h(x). In terms of congruence, either x-b \equiv 0 \ (\text{mod} \ m) or h(x) \equiv 0 \ (\text{mod} \ m). The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most n-1 solutions. Together, equation (1) has at most n solutions. \blacksquare

    Lemma 5

      Let m be a prime number. If d \ \lvert \ (p-1), then the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has exactly d many solutions.

Proof of Lemma 5

Suppose d \ \lvert \ (p-1). Fermat’s little theorem tells us that x^{m-1}-1 \equiv 0 \ (\text{mod} \ m) has exactly m-1 solutions, namely 1,2,3,\cdots,m-1. We can factor the polynomial x^{m-1}-1 as follows:

    g(x)=x^{m-1}-1=(x^d-1) \cdot (x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)

Let t(x)=(x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1). Whenever g(x) \equiv 0 \ (\text{mod} \ m), m \ \lvert \ g(x)=x^{m-1}-1=(x^d-1) \cdot t(x). By Euclid’s lemma, m \ \lvert \ (x^d-1) or m \ \lvert \ t(x). In terms of congruence, x^d \equiv 1 \ (\text{mod} \ m) or t(x) \equiv 0 \ (\text{mod} \ m).

By Lemma 4, the congruence t(x) \equiv 0 \ (\text{mod} \ m) has at most m-1-d solutions. Since x^{m-1}-1 \equiv 0 \ (\text{mod} \ m) has exactly m-1 solutions, the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has at least d many solutions.

By Lemma 4, the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has at most d solutions. Thus x^d \equiv 1 \ (\text{mod} \ m) has exactly d many solutions. \blacksquare

We need one more lemma before proving Theorem 1.

    Lemma 6

      Let a and b be integers with 0 \le a,b \le m-1. Let \alpha be the order of a modulo m. Let \beta be the order of b modulo m.

      Suppose that \alpha and \beta are relatively prime. Then \alpha \cdot \beta is the order of a \cdot b modulo m.

Proof of Lemma 6

Let \gamma be the order of a \cdot b modulo m. We show that \gamma=\alpha \beta. The following derivation shows that \alpha \ \lvert \ \gamma.

    1 \equiv 1^\beta \equiv ((ab)^\gamma)^\beta =(ab)^{\gamma \beta}=(a)^{\gamma \beta} (b)^{\gamma \beta}=(a)^{\gamma \beta} (b^{\gamma})^{\beta} \equiv a^{\gamma \beta} \ (\text{mod} \ m)

Since a^{\gamma \beta} \equiv 1 \ (\text{mod} \ m), we have \alpha \ \lvert \ \gamma \beta (by Lemma 3). Since \alpha and \beta are relatively prime, \alpha \ \lvert \ \gamma. By a symmetrical argument, it can also be shown that \beta \ \lvert \ \gamma.

Since \alpha \ \lvert \ \gamma, we have \gamma=\alpha \cdot t for some integer t. Since \beta \ \lvert \alpha \cdot t, it follows that \beta \ \lvert t (Euclid’s lemma). So t=\beta \cdot z for some integer z. Now \gamma=\alpha \cdot \beta \cdot z. This means that \alpha \beta \ \lvert \ \gamma.

On the other hand, we have \gamma \ \lvert \alpha \beta. This follows from the following derivation and from Lemma 3.

    (ab)^{\alpha \beta}=(a^\alpha)^\beta \cdot (b^\beta)^\alpha \equiv 1 \ (\text{mod} \ m)

It follows that \gamma= \alpha \beta. \blacksquare

Remark
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 p-1.

    \displaystyle p-1=w_1^{e_1} \cdot w_2^{e_2} \cdot w_3^{e_3} \cdots w_n^{e_n}

In the above factorization, the numbers w_i are distinct prime numbers and the exponents e_i \ge 1.

For each i, it is clear that w_i^{e_i} \ \lvert \ (p-1). By Lemma 5, the congruence equation

    \displaystyle x^{w_i^{e_i}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

has exactly w_i^{e_i} many solutions. Note that the w_i^{e_i} many solutions are integers in the interval 0 \le x \le p-1. Furthermore, the order modulo p of each of these solutions to (2) is a divisor of w_i^{e_i} (by Lemma 3).

In fact, from Lemma 3, we can say that for any integer x in the interval 0 \le x \le p-1, the number x is a solution of equation (2) if and only if the order modulo p of x is a divisor of w_i^{e_i}. We have the following claim.

Claim
For each i, we claim that there exists at least one integer a_i in the interval 0 \le x \le p-1 such that the order of a_i modulo p is w_i^{e_i}.

To see the above claim, the congruence equation

    \displaystyle x^{w_i^{e_i-1}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

has exactly w_i^{e_i-1} many solutions in the interval 0 \le x \le p-1 (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of w_i^{e_i-1}.

In fact, from Lemma 3, we can also say that for any integer x in the interval 0 \le x \le p-1, the number x is a solution of equation (3) if and only if the order modulo p of x is a divisor of w_i^{e_i-1}.

Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of w_i^{e_i-1} are also divisors of w_i^{e_i}.

Thus there are w_i^{e_i}-w_i^{e_i-1} many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it a_i. Let k be the order of a_i modulo p. There are three possibilities for k:

    k \le w_i^{e_i-1} \ \ \ \ \ w_i^{e_i-1}<k<w_i^{e_i} \ \ \ \ \  k=w_i^{e_i}

Since a_i is a solution to (2), the number k is a divisor of w_i^{e_i}. Note that there are no divisors of w_i^{e_i} within the interval w_i^{e_i-1}<y<w_i^{e_i} since w_i is a prime number. So w_i^{e_i-1}<k<w_i^{e_i} is not possible.

Since a_i is not a solution to (3), the number k is not a divisor of w_i^{e_i-1}. This means that k \le w_i^{e_i-1} is not possible. Since w_i is prime, k must be a power of w_i. Since k must be a power of w_i, if k \le w_i^{e_i-1}, k is then a divisor of w_i^{e_i-1}.

So the only possibility is that k=w_i^{e_i}. This establishes the above claim.

Let g=a_1 \cdot a_2 \cdots a_n. The primitive root modulo p we are looking for is either g if g<p or the least residue of g if g \ge p.

According to the above claim, the order modulo p of a_i is w_i^{e_i}. Clearly w_i^{e_i} and w_j^{e_j} are relatively prime for i \ne j. As a corollary of Lemma 6, the order of the product g=a_1 \cdot a_2 \cdots a_n is the products of w_i^{e_i}, namely p-1. Thus g=a_1 \cdot a_2 \cdots a_n or its least residue modulo p is a primitive root. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

An elementary algorithm for finding primitive roots

In the previous post Finding Primitive Roots, we demonstrate one approach for finding all primitive roots of a prime modulus. In this post, we summarize the ideas behind that example.

Throughout this discussion m is a positive integer that is used as the modulus for modular arithmetic, and a is assumed to be a positive integer that is relatively prime to m such that 0 \le a \le m-1.

According to Fermat’s little theorem, if the modulus m is prime, then a^{m-1} \equiv 1 \ (\text{mod} \ m). If the modulus is relaxed to include non-prime integers as well, then we have Euler’s theorem which states that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) where \phi(m) is Euler’s phi function. For any modulus m, \phi(m) is simply the numbers of possible values of a that are relatively prime to m. For example, \phi(m)=10 if m=11 and \phi(m)=4 if m=10.

So it is always the case that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). Another way to say this is that the number \phi(m) is always a solution to the following congruence equation.

    \displaystyle a^x \equiv 1 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

With this above discussion in mind, we define the notion of order. The order of a modulo m is the least positive integer solution to the congruence equation (1).

Furthermore, the number a is said to be a primitive root modulo m if the least positive integer solution to (1) is \phi(m).

Note that even though the notions of order and primitive root are defined here for integers a that are relatively prime to m with 0 \le a \le m-1, the definitions are also valid for positive a outside the range 0 \le a \le m-1. Relaxing the definitions can make some proofs go easier (e.g. Theorem 2 below).

___________________________________________________________________________________________________________________

An Approach in Finding Primitive Roots

We now summarize the ideas discussed in the previous post Finding Primitive Roots.

Recall that a is a positive integer less than m that is relatively prime to m. How do we check if a is a primitive root? On the face of it, we need to check that no positive integer less than \phi(m) is a solution to equation (1). It turns out that we only need to check positive integers less than \phi(m) that are divisors of \phi(m). We have the following theorem.

    Theorem 1

      The following conditions are equivalent.

      1. The number a is a primitive root modulo m.
      2. Every positive divisor k of \phi(m) with k < \phi(m) is not a solution of the congruence equation (1).

\text{ }
If we know that there exists a primitive root for a modulus, the followng theorem tells us how to find the other primitive roots.

    Theorem 2

      Suppose the number a is a primitive root modulo m. Then there are exactly \phi(\phi(m)) many primitive roots modulo m. They are obtained by finding the least residues of the numbers a^j where the exponents j are taken from the following set.

        \left\{j: 1 \le j \le \phi(m) \text{ and } j \text{ is relatively prime to } \phi(m) \right\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Thus the above two theorems taken together form an algorithm for finding primitve roots of a modulus (if one is known to exist to begin with). We can use Theorem 1 to find a primitive root. Once we have found one, we can raise it to exponents that are relatively prime to the number \phi(m) to find the remaining primitive roots. Since there are \phi(\phi(m)) many positive integers that are less than \phi(m) and relatively prime to \phi(m), there are \phi(\phi(m)) many primitive roots modulo m (if one exists).

Before proving the theorems, let’s look at a quick example.

For m=11, \phi(11)=10. The candidates for primitive roots modulo m=11 are in the set \left\{2,3,4,\cdots,10 \right\}. The divisors of \phi(11)=10 are 1,2,5. According to Theorem 1, we only need to raise these numbers to exponents that are divisors of \phi(11)=10.

Note that 2^1 \equiv 2 \ (\text{mod} \ 11), 2^2 \equiv 4 \ (\text{mod} \ 11) and 2^5 \equiv 10 \ (\text{mod} \ 11). Thus a=2 is a primitive root modulo m=11.

The positive integers that are less than \phi(11)=10 and that are relatively prime to \phi(11)=10 are 1, 3, 7, 9. So there are four primitive roots modulo m=11. They are:

    \displaystyle \begin{aligned} \text{ }&2^1 \equiv 2 \ (\text{mod} \ 11) \\&2^3 \equiv 8 \ (\text{mod} \ 11) \\&2^7 \equiv 7 \ (\text{mod} \ 11) \\&2^9 \equiv 6 \ (\text{mod} \ 11) \end{aligned}

___________________________________________________________________________________________________________________

Proof of Theorems

Proof of Theorem 1

The direction 1 \Longrightarrow 2 is clear. If a is a primitive root modulo m, then by definition, no positive integer less than \phi(m) can be a solution to the congruence equation (1).

2 \Longrightarrow 1
Let h be the order of a modulo m. The key to the proof is that h must be a divisor of \phi(m) (see Theorem 4 and Corollary 5 in the post Defining Primitive Root). For the sake of completeness, we provide the proof here.

Since h is the least positive solution of the congruence equation (1), h \le \phi(m). Using the division algorithm, we have \phi(m)=q \cdot h+r for some integers q and r where 0 \le r <h. We have the following calculation.

    1 \equiv a^{\phi(m)}=(a^h)^q \cdot a^r \equiv (1)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

So we have a^r \equiv 1 \ (\text{mod} \ m) and 0 \le r <h. Since h is the least positive solution of (1), the only possibility is that r=0. Hence \phi(m)=q \cdot h and h is a divisor of \phi(m).

Now back to the proof for 2 \Longrightarrow 1. We claim that h=\phi(m), implying that a is a primitive root modulo m. If h<\phi(m), then h is a positive divisor of \phi(m) with h<\phi(m) such that h is a solution of the congruence equation (1) (i.e. the condition 2 does not hold). Thus if condition 2 holds, condition 1 must hold. \blacksquare

Proof of Theorem 2
Theorem 2 is the combined result of Theorem 6 and Corollary 7 in the post Defining Primitive Root. To make this post as self contained as possible, we repeat the proof, showing just the essential parts.

We do need one theorem from the previous post Defining Primitive Root. Let w be a positive integer that is relatively prime to the modulus m. Let k be the order of w modulo m. Theorem 4 in this post states that for any , w^n \equiv 1 \ (\text{mod} \ m) if and only if k \ \lvert \ n.

There are exactly \phi(\phi(m)) many elements in the above set indicated by (2). So there are these many powers of a. The first thing to show is that the powers a^j are all distinct congruent modulo m. Hence their least residues are also distinct.

To see this, suppose a^j \equiv a^i \ (\text{mod} \ m) where i, j \le \phi(m) with i \le j. We want to show i=j. Suppose that i<j. Since a^i is relatively prime to m, we can cancel out a^i on both sides and obtain a^{j-i} \equiv 1 \ (\text{mod} \ m). Since j-i<\phi(m) and a is a primitive root modulo m, a^{j-i} \not \equiv 1 \ (\text{mod} \ m). So i=j. Thus if i \ne j, then a^j \not \equiv a^i \ (\text{mod} \ m).

The next thing to show is that a^j is a primitive root modulo m for any j in the above set (2). Suppose j is one such element of the set (2). Then j and \phi(m) are relatively prime.

Let h be the order of a^j modulo m. We have a^{j \cdot h}=(a^h)^j \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it follows that \phi(m) \ \lvert \ j \cdot h (according Theorem 4 in Defining Primitive Root). Since \phi(m) and j are relatively prime, \phi(m) \ \lvert \ h.

On the other hand, (a^j)^{\phi(m)}=(a^{\phi(m)})^j \equiv 1 \ (\text{mod} \ m). Since h is the order of a^j, it follows that h \ \lvert \ \phi(m) (also using Theorem 4 in Defining Primitive Root).

With \phi(m) \ \lvert \ h and h \ \lvert \ \phi(m), we have h=\phi(m). Thus a^j is a primitive root modulo m and so is its least residue. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

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 m is a prime number, there exist primitive roots modulo m. 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 m=277, 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 m, let \mathbb{Z}_m be the set \left\{0,1,2,\cdots,m-1 \right\}. Let (\mathbb{Z}_m)^* be the set of all numbers a in \mathbb{Z}_m that is relatively prime to m. Euler’s phi function \phi(m) is the count of the elements in the set (\mathbb{Z}_m)^*. Euler’s theorem states that for any a \in (\mathbb{Z}_m)^*, a^{\phi(m)} \equiv 1 \ (\text{mod} \ m).

Euler’s theorem establishes a solution for the congruence equation a^{x} \equiv 1 \ (\text{mod} \ m) where x is a positive integer. Whenever \phi(m) is the smallest positive solution to a^{x} \equiv 1 \ (\text{mod} \ m), the number a is said to be a primitive root modulo m.

In general, the smallest positive solution to the equation a^{x} \equiv 1 \ (\text{mod} \ m) is called the order of a modulo m. Thus, in terms of the notion of order, any number a \in (\mathbb{Z}_m)^* is a primitive root modulo m whenever the order of a and \phi(m) coincide.

__________________________________________________________________________________________________________________

Finding One Primitive Root

For the modulus m=277, \mathbb{Z}_m=\left\{0,1,2,\cdots,276 \right\} and (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}. So \phi(277)=276. According to Euler’s theorem, a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277) for all a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}.

Obviously a=1 can never be a primitive root. Thus candidates for primitive roots are the 275 numbers in the set \left\{2,3,\cdots,276 \right\}. As we will see below, we only need to find one primitive root a from this list. Our plan is to find the smallest primitive root a from this list.

Since a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277), showing that a is a primitive root modulo m=277 requires verifying that a^j \not \equiv 1 \ (\text{mod} \ 277) for each j \in \left\{2,3,\cdots,275 \right\}. We can get by with less computation.

If x=k is the smallest positive integer solution to a^{x} \equiv 1 \ (\text{mod} \ m), then k \ \lvert \ \phi(m) (see Theorem 4 and Corollary 5 in the post Defining Primitive Root).

So the order of a number a can only be the numbers j in the set \left\{2,3,\cdots,275 \right\} that are divisors of \phi(277)=276. If a^j \not \equiv 1 \ (\text{mod} \ 277) for all such j, then the number a is a primitive root modulo m=277. If a^j \equiv 1 \ (\text{mod} \ 277) for one such j, then the number a is not a primitive root modulo m=277. This is the approach we take to find one primitive root modulo m=277.

Note that 276=2^2 \cdot 3 \cdot 23, which has eleven divisors that are less than 276. They are:

    \displaystyle \begin{aligned} \text{divisors of } 276&=1 \\&=2 \\&=3 \\&=4 \\&=6 \\&=12 \\&=23 \\&=46 \\&=69 \\&=92 \\&=138 \end{aligned}

We start with a=2 and check a^j where j is from the above list of divisors. The first a where a^j \not \equiv 1 \ (\text{mod} \ 277) for all eleven j is a primitive root.

We have the following calculation:

    2^{92} \equiv 1 \ (\text{mod} \ 277)

    3^{69} \equiv 1 \ (\text{mod} \ 277)

    4^{46} \equiv 1 \ (\text{mod} \ 277)

So a=2,3,4 are not primitive root modulo m=277. For a=5, a^j \not \equiv 1 \ (\text{mod} \ 277) for all eleven j. Thus a=5 is the smallest primitive root modulo m=277.

__________________________________________________________________________________________________________________

Finding the Other Primitive Roots

If there is one primitive root for a modulus m, there are exactly \phi(\phi(m)) many primitive roots (see Corollary 7 in the post Defining Primitive Root). For the modulus m=277, there are \phi(\phi(277))=\phi(276)=88 primitive roots.

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

So in this example, for the exponents we only need to find the numbers in the set \left\{1,2,3,\cdots,276 \right\} that are relatively prime to \phi(277)=276.

To find the 88 numbers that are relatively prime to \phi(277)=276, we can list out the numbers 1,2,3,\cdots,276. Since the prime factors of 276 are 2,3,23, we cross out the multiples of 2, the multiples of 3, and finally the multiples of 23. The following matrix shows the 88 numbers that remain.

    \displaystyle \begin{bmatrix} 1&5&7&11&13&17&19&25&29&31     \\ 35&37&41&43&47&49&53&55&59&61 \\ 65&67&71&73&77&79&83&85&89&91 \\ 95&97&101&103&107&109&113&119&121&125 \\ 127&131&133&137&139&143&145&149&151&155 \\ 157&163&167&169&173&175&179&181&185&187 \\ 191&193&197&199&203&205&209&211&215&217 \\ 221&223&227&229&233&235&239&241&245&247 \\ 251&257&259&263&265&269&271&275&\text{ }&\text{ }  \end{bmatrix}

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

    \displaystyle \begin{bmatrix} 5&78&11&227&135&167&20&44&77&263     \\ 114&80&140&176&31&221&179&43&6&150 \\ 124&53&162&172&24&46&219&212&94&134 \\ 96&184&45&17&99&259&107&180&68&119 \\ 205&151&174&166&272&199&266&50&142&110 \\ 257&233&200&14&163&197&137&101&246&56 \\ 98&234&271&127&153&224&115&105&253&231 \\ 58&65&183&143&181&93&232&260&178&18 \\ 170&97&209&158&72&126&103&111&\text{ }&\text{ }  \end{bmatrix}

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

    5^{1} \equiv 5 \ (\text{mod} \ 277)

    5^{5} \equiv 78 \ (\text{mod} \ 277)

    5^{7} \equiv 11 \ (\text{mod} \ 277)

    5^{11} \equiv 227 \ (\text{mod} \ 277)

    5^{13} \equiv 135 \ (\text{mod} \ 277)

    5^{17} \equiv 167 \ (\text{mod} \ 277)

    5^{19} \equiv 20 \ (\text{mod} \ 277)

    5^{25} \equiv 44 \ (\text{mod} \ 277)

    5^{29} \equiv 77 \ (\text{mod} \ 277)

    5^{31} \equiv 263 \ (\text{mod} \ 277)

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

    \displaystyle \begin{bmatrix} 5&6&11&14&17&18&20&24&31&43     \\ 44&45&46&50&53&56&58&65&68&72 \\ 77&78&80&93&94&96&97&98&99&101 \\ 103&105&107&110&111&114&115&119&124&126 \\ 127&134&135&137&140&142&143&150&151&153 \\ 158&162&163&166&167&170&172&174&176&178 \\ 179&180&181&183&184&197&199&200&205&209 \\ 212&219&221&224&227&231&232&233&234&246 \\ 253&257&259&260&263&266&271&272&\text{ }&\text{ }  \end{bmatrix}

__________________________________________________________________________________________________________________

Exercise

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

Find all the primitive roots modulo m=127. Answers are show below.

\text{ }

\text{ }

\text{ }

\text{ }

    \displaystyle \begin{bmatrix} 3&6&7&12&14&23&29&39&43&45     \\ 46&48&53&55&56&57&58&65&67&78 \\ 83&85&86&91&92&93&96&97&101&106 \\ 109&110&112&114&116&118&\text{ }&\text{ }&\text{ }&\text{ }  \end{bmatrix}

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

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Defining Primitive Root

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 a and b 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, a=9 and b=14 are relatively prime, as are a=9 and b=35. If a and b are relatively prime, we also say that a is relatively prime to b or b is relatively prime to a. Our notation for greatest common divisor is \text{GCD}(a,b).

In working with modular arithmetic where the modulus is the positive integer m, every integer is congruent modulo m to exactly one number in the set \left\{0,1,2,\cdots,m-1 \right\}. The numbers in this set are called the least residues modulo m. In doing modulus m calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}.

An even more interesting set is the set of all integers a in \mathbb{Z}_m such that a and the modulus m are relatively prime. To facilitate the discussion, we describe this set as follows:

    \displaystyle \begin{aligned} (\mathbb{Z}_m)^*&=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\} \\&=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\}  \end{aligned}

When the modulus m is a prime number, (\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}, the non-zero elements of \mathbb{Z}_m. The following theorem gives some indication why (\mathbb{Z}_m)^* is an interesting set, which provides alternative characterizations of (\mathbb{Z}_m)^*.

    Theorem 1

      Let a be an integer in \mathbb{Z}_m. The following conditions are equivalent.

      1. \text{GCD}(a,m)=1.
      2. There is a b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m).
      3. Some positive power of a modulo m is 1, i.e., a^n \equiv 1 \ (\text{mod} \ m) for some positive integer n.

\text{ }

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

The Euler’s phi function, denoted by \phi(m), is the number of integers a where 0 \le a \le m-1 such that a and the modulus m are relatively prime. In light of the above discussion, \phi(m) is the number of elements in the set (\mathbb{Z}_m)^*. It is also the case that \phi(m) is the number of elements in \mathbb{Z}_m 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 m, 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 m be a prime number. Then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is relatively prime to m.

\text{ }

    Theorem 3 (Euler’s theorem)

      It is the case that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) for any integer a that is relatively prime to m.

\text{ }

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 a be an integer in \mathbb{Z}_m that is relatively prime to the modulus m. Based on the above theorems, a^k \equiv 1 \ (\text{mod} \ m) for some positive integer k. By the order of a modulo m, we mean the least positive integer k such that a^k \equiv 1 \ (\text{mod} \ m). The number a is a primitive root modulo m if the order of a modulo m is the number \phi(m).

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

One comment. The notions of order and primitive roots are defined above for integers in \mathbb{Z}_m. 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 \mathbb{Z}_m. In some cases, it will be helpful to think of orders of numbers outside of \mathbb{Z}_m and think of numbers outside of \mathbb{Z}_m as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus m is a prime number. Fermat’s little theorem tells us that a^{m-1} \equiv 1 \ (\text{mod} \ m) for any a that is relatively prime to m. Is m-1 the only exponent for which the power of a is one? Take m=11. The following table gives the powers of a modulus m=11 where 1 \le a \le 10.

    \displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10}  \\\text{ }&\text{ }&\text{ }   \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}

The above table shows that for a=2,6,7,8, the number 10 is the least exponent for which the power of a is one. In other words, the order for these a is \phi(11)=10. The numbers a=2,6,7,8 are primitive roots modulo m=11. The other values of a are not primitive roots. The order for a=1 is 1. The order for a=10 is 2. The order for a=3,4,5,9 is 5.

Note that in the above table, for the numbers a that are primitive roots, the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(11)} \right\} equals the set \left\{1,2,3,\cdots,10 \right\}. 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 m=10. The following table gives the powers of a modulus m=10 where 1 \le a \le 9.

    \displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9  \\\text{ }&\text{ }&\text{ }   \\ 1&1&1&1&1&1&1&1&1 \\ 2&4&8&6&2&4&8&6&2 \\ 3&9&7&1&3&9&7&1&3 \\ 4&6&4&6&4&6&4&6&4 \\ 5&5&5&5&5&5&5&5&5 \\ 6&6&6&6&6&6&6&6&6 \\ 7&9&3&1&7&9&3&1&7 \\ 8&4&2&6&8&4&2&6&8 \\ 9&1&9&1&9&1&9&1&9  \end{bmatrix}

Note that \phi(10)=4 since (\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\} is the set of all the least residues that are relatively prime to m=10. In terms of powers of a, we should only focus on \left\{1,3,7,9 \right\}. The following is the reduced table.

    \displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9  \\\text{ }&\text{ }&\text{ }   \\ 1&1&1&1&1&1&1&1&1  \\ 3&9&7&1&3&9&7&1&3    \\ 7&9&3&1&7&9&3&1&7  \\ 9&1&9&1&9&1&9&1&9  \end{bmatrix}

Note that a^4 \equiv 1 \ (\text{mod} \ 10) for all four a. But only a=3,7 are primitive roots modulo m=10.

Also note that in the above table, for the numbers a that are primitive roots, the set \left\{a^1,a^2,a^3,a^4 \right\} equals the set \left\{1,3,7,9 \right\}. 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 m=8. The least residues that are relatively prime to m=8 are the set \left\{1,3,5,7 \right\}. Note that a^2 \equiv 1 \ (\text{mod} \ 8) for every a in this set. Thus no number a in this set can have order = \phi(8)=4.

___________________________________________________________________________________________________________________

Elementary Results

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

    Theorem 4

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. Suppose k is the order of the number a modulo m. Then a^n \equiv 1 \ (\text{mod} \ m) if and only if n is a multiple of k.

Proof of Theorem 4

\Longleftarrow
This direction is clear. If n=q \cdot k for some integer q, then a^n=(a^k)^q \equiv 1 \ (\text{mod} \ m).

\Longrightarrow
Suppose that a^n \equiv 1 \ (\text{mod} \ m). By the division algorithm, we have n=q \cdot k+r for some integers q and r where 0 \le r <k. We have the following:

    a^n=(a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

Since r<k and a^r \equiv 1 \ (\text{mod} \ m), it must be the case that r=0, implying that n=q \cdot k. \blacksquare

We have the following corollary.

    Corollary 5

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. Suppose k is the order of the number a modulo m. Then \phi(m) is a multiple of k.

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.

    Theorem 5

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. The following conditions are equivalent.

      1. The number a is a primitive root modulo m.
      2. The set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}, where each a^j is considered as the least residues modulo m, is precisely the set (\mathbb{Z}_m)^*.

\text{ }

Recall that (\mathbb{Z}_m)^* is the set of all a \in \mathbb{Z}_m=\left\{0,1,2,3,\cdots,m-1 \right\} such that a is relatively prime to m.

Proof of Theorem 5

1 \Longrightarrow 2
Suppose that the number a is a primitive root modulo m. The first step in showing condition 2 is to show that the \phi(m) numbers in the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are distinct congruent modulo m. Then it follows that their least residues modulo m are distinct too.

Suppose a^j \equiv a^i \ (\text{mod} \ m) where i,j  \le \phi(m). We want to show that i=j. Suppose i<j. Then cancel out a^i on both sides of the equation since a^i is relatively prime to m. We have a^{j-i} \equiv 1 \ (\text{mod} \ m). But j-i<\phi(m). Since a is a primitive root modulo m, we cannot have a^{j-i} \equiv 1 \ (\text{mod} \ m). So it must be the case that j=i. So if a^j \equiv a^i \ (\text{mod} \ m), then i=j. Equivalently, if i \ne j, a^j \not \equiv a^i \ (\text{mod} \ m). Thus the least residues modulo m of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are distinct too.

Since a^i is relatively prime to m, its least residue is also relatively prime to m. Now the least residues modulo m of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} consist of \phi(m) numbers inside (\mathbb{Z}_m)^*, which is also a set of \phi(m) many numbers. So the two sets must equal.

2 \Longrightarrow 1
We show the contrapositive of 2 \Longrightarrow 1. Suppose that the order of a modulo m is j where 1 \le j<\phi(m). So a^j \equiv 1 \ (\text{mod} \ m) and a^{j+1} \equiv a \ (\text{mod} \ m). So a and a^{j+1} are two elements in the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} that are congruent to each other. This means that the least residues of \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} have less than \phi(m) many values. In other words, the number a, through powering, cannot generate all the least residues that are relatively prime to the modulus m. \blacksquare

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

    Theorem 6

      Let a be a primitive root modulo m. Then for any positive integer k, the least residue of a^k is a primitive root modulo m if and only if k is relatively prime to \phi(m).

Proof of Theorem 6

\Longrightarrow
Suppose that k is not relatively prime to \phi(m). So d=\text{GCD}(k,\phi(m))>1. Then we have:

    \displaystyle (a^k)^{\frac{\phi(m)}{d}}=(a^{\phi(m)})^{\frac{k}{d}} \equiv 1 \ (\text{mod} \ m)

With \displaystyle b=\frac{\phi(m)}{d}<\phi(m) and (a^k)^b \equiv 1 \ (\text{mod} \ m), it follows that a^k is not a primitive root modulo m. Hence the least residue of a^k modulo m is also not a primitive root. Thus if the least residue of a^k is a primitive root modulo m, it must be that \text{GCD}(k,\phi(m))=1.

\Longleftarrow
Suppose \text{GCD}(k,\phi(m))=1. Let \alpha be the order of a^k modulo m. By the definition of order, a^{k \cdot \alpha}=(a^k)^\alpha \equiv 1 \ (\text{mod} \ m). Based on the fact that the order of a modulo m is \phi(m), we have \phi(m) \ \lvert \ k \cdot \alpha (also using Theorem 4). Since \text{GCD}(k,\phi(m))=1, it must be the case that \phi(m) \ \lvert \ \alpha.

On the other hand, (a^k)^{\phi(m)}=(a^{\phi(m)})^k \equiv 1 \ (\text{mod} \ m). Using the fact that the order of a^k is \alpha (and using Theorem 4), \alpha \ \lvert \ \phi(m).

With \phi(m) \ \lvert \ \alpha and \alpha \ \lvert \ \phi(m), it follows that \alpha = \phi(m). This implies that a^k is a primitive root modulo m, and so is its least residue modulo m. \blacksquare

    Corollary 7

      Suppose that there exists a primitive root modulo m. Then there are exactly \phi(\phi(m)) many primitive roots modulo m.

Proof of Corollary 7

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

Furthermore, according to Theorem 5, the least residues of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are all distinct. Thus the least residues of the powers a^k for the \phi(\phi(m)) many k are primitive roots modulo m. \blacksquare

___________________________________________________________________________________________________________________

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.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}