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