# 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 . 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}$