Determining if r is a Primitive Root of N

Suppose that we wanted to determine if 5 was a primitive root of 107? We would need to check all possible orders of 105 on 5, and if 106 was the smallest integer such that $5^{106} \equiv 1 \pmod {105}$, then we would know that 5 is in fact a primitive root (mod 107).

Example 1

Determine if 5 is a primitive root of 107.

We first note that the possible order of 5 must be a positive divisor of 1 less than 107 (a divisor of 106). These divisors of 106 are 1, 2, 53, and 101.

Clearly 5 does not have order 1, since $5 \not \equiv 1 \pmod {107}$. Furthermore, 5 does not have order 2, since $5^2 = 25 \not \equiv 1 \pmod {107}$. We must now test to see if 5 has order 53. This can be done with successive squaring and multiplication:

(1)

\begin{align} 5^2 \equiv 25 \not \equiv 1 \pmod {107} \\ 5^4 \equiv (25)^2 = 625 \equiv 90 \pmod {107} \\ 5^8 \equiv (90)^2 = 8100 \equiv 75 \pmod {107} \\ 5^{16} \equiv (75)^2 = 5625 \equiv 61 \pmod {107} \\ 5^{32} \equiv (61)^2 = 3721 \equiv 83 \pmod {107} \\ 5^{53} = 5^{32} \cdot 5^{16} \cdot 5^{4} \cdot 5 \equiv (83)(61)(90)(5) = 2278350 \equiv 106 \pmod {107} \end{align}

Hence, $5^{53} \equiv 106 \pmod {107}$. So 5 does NOT have order 53. Since 5 does not have order 1, 2, or 53, it goes that by Fermat's theorem that 5 has order 106. We can even verify this to be true since $5^{106} \equiv (106)^2 = 11236 \equiv 1 \pmod {107}$. Hence 5 is a primitive root of 107.

Example 2

Determine if 30 is a primitive root of 107.

Once again, the possible orders of 30 (mod 107) are positive divisors of 106, namely 1, 2, 53, and 106. Clearly $30 \not \equiv 1 \pmod {107}$. We must now test to see if 30 has order 2:

(2)

\begin{align} 30^2 = 900 \equiv 44 \not \equiv 1 \pmod {107} \end{align}

Hence 30 does not have order 2 (mod 107). We must now test to see if 30 has order 53, which can be done with successive squaring once again.

(3)

\begin{align} 30^4 \equiv (44)^2 = 1936 \equiv 10 \pmod {107} \\ 30^8 \equiv (10)^2 = 100 \equiv 100 \pmod {107} \\ 30^{16} \equiv (100)^2 = 10000 \equiv 49 \pmod {107} \\ 30^{32} \equiv (49)^2 = 2401 \equiv 47 \pmod {107} \\ 30^{53} = 30^{32} \cdot 30^{16} \cdot 30^{4} \cdot 30 \equiv (47)(49)(10)(30) = 690900 \equiv 1 \pmod {107} \end{align}

Since $30^{53} \equiv 1 \pmod {107}$, then 30 has order 53 (mod 107). Hence 30 is NOT a primitive root of 107.

Example 3

Determine if 44 is a primitive root of 113.

The divisors of 112 (and possible orders of 44) are 1, 2, 4, 7, 8, 14, 16, 28, 56, 112. There are a lot of orders to go through, though, we don't need to go through them all. We note that if the positive integer C is not the order of 44, then any divisor of C is also not the order of 44. We will strike off possible orders as we go along to proceed answering this question.

Firstly, the order of 44 is not 1, since $44 \not \equiv 1 \pmod {113}$. (1, 2, 4, 7, 8, 14, 16, 28, 56, 112). Now let's see if 56 is the order of 44 (mod 103). Once again, we will do this with successive squaring:

(4)

\begin{align} 44^2 \equiv 1936 \equiv 15 \pmod {113} \\ 44^4 \equiv (15)^2 = 225 \equiv 112 \pmod {113} \\ 44^8 \equiv (112)^2 = 12544 \equiv 1 \pmod {113} \end{align}

We note that while we were successively squaring, we found that $44^8 \equiv 1 \pmod {113}$. Hence, we do not need to go further since 44 has order 8. 44 is NOT a primitive root of 113.

Example 4

Determine if 23 is a primitive root of 127.

The possible orders of 23 are divisors of 126, namely 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126. We will now test these powers to see if 127 is a primitive root.

(5)

\begin{align} 23^1 \equiv 23 \pmod {127} \\ 23^2 = 529 \equiv 21 \pmod {127} \\ 23^3 = 23^2 \cdot 23 \equiv (23)(21) = 483 \equiv 102 \pmod {127} \\ 23^6 \equiv (102)^2 = 10404 \equiv 117 \pmod {127} \\ 23^7 = 23^6 \cdot 23 \equiv (117)(23) = 2691 \equiv 24 \pmod {127} \\ 23^9 = 23^7 \cdot 23^2 \equiv (24)(21) = 504 \equiv 123 \pmod {127} \\ 23^{14} = 23^9 \cdot 23^3 + 23^2 \equiv (123)(102)(21) = 263466 \equiv 68 \pmod {127} \\ 23^{18} = 23^{14} \cdot 23^3 \cdot 23 \equiv (68)(102)(23) = 159528 \equiv 16 \pmod {127} \\ 23^{21} = 23^{18} \cdot 23^{3} \equiv (16)(102) = 1632 \equiv 108 \pmod {127} \\ 23^{42} \equiv (108)^2 = 11664 \equiv 107 \pmod {127} \\ 23^{63} \equiv 23^{42} \cdot 23^{21} \equiv (107)(108) = 11556 \equiv 126 \pmod {127} \end{align}

As we can see, the order of 23 is not 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, or 63. Hence by Fermat's theorem, it must be 126, as we show here:

(6)

\begin{align} 23^{126} \equiv (126)^2 = 15876 \equiv 1 \pmod {127} \end{align}

Hence 23 is a primitive root of 127.