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}

Advertisements

2 thoughts on “More about checking for primitive roots

  1. What a wonderful article! I really like this presentation and plan to make notes for myself from the material. I’m a Java/Scala programmer brushing up on number theory in the context of pseudo random number generators, where number theory talks, and ignorance walks.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s