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