Finding Other Primitive Roots (mod p)

Suppose that we have a primitive root, g. For example, 2 is a primitive root of 59. Then it turns out for any integer relatively prime to 59-1, let's call it b, then $2^b (mod 59)$ is also a primitive root of 59.

Example 1

Given that 2 is a primitive root of 59, find 17 other primitive roots of 59.

We know that 3, 5, 7, 11, 13, 17, and 19 are all relatively prime to 58. That is (3, 58) = (5, 58) = (7, 58) = (11, 58) = (13, 58) = (17, 58) = (19, 58) = 1. It thus follows that since we know 2 is a primitive root, then 2³ (mod 59), 2⁵ (mod 59), …, 2¹⁹ (mod 59) are also primitive roots of 59:

(1)

\begin{align} 2^3 \equiv 8 \pmod {59} \\ 2^5 \equiv 32 \pmod {59} \\ 2^7 = 128 \equiv 10 \pmod {59} \\ 2^{11} = 2048 \equiv 42 \pmod {59} \\ 2^{13} = 8192 \equiv 50 \pmod {59} \\ 2^{17} = 131072 \equiv 33 \pmod {59} \\ 2^{19} = 524228 \equiv 14 \pmod {59} \end{align}

Hence, 8, 32, 10, 42, 50, 33, and 14 are all primitive roots (mod 59).

Example 2

Given that 3 is a primitive root of 113, find 5 other primitive roots.

We first want to find five positive integers that are relatively prime to 112. We will choose the primes 5, 11, 13, 17, and 19, since all of them are relatively prime to 112. Now:

(2)

\begin{align} 3^5 = 243 \equiv 17 \pmod {113} \\ 3^{11} = 177147 \equiv 76 \pmod {113} \\ 3^{13} = 1594323 \equiv 6 \pmod {113} \\ 3^{17} = 129140163 \equiv 34 \pmod {113} \\ 3^{19} = 1162261467 \equiv 80 \pmod {113} \end{align}

Hence, 17, 76, 6, 34, and 80 are primitive roots of 113.

Example 3

Given that 6 is a primitive root of 79, find 5 other primitive roots.

Once again, we want to find 5 positive integers that are relatively prime to 78. We will choose 5, 7, 11, 17, and 19. Now:

(3)

\begin{align} 6^5 = 7776 \equiv 34 \pmod {79} \\ 6^7 = 279936 \equiv 39 \pmod {79} \\ 6^{11} = 362797056 \equiv 63 \pmod {79} \\ 6^{17} \equiv 54 \pmod {79} \\ 6^{19} \equiv 48 \pmod {79} \end{align}

Hence, 34, 39, 63, 54, 48 are primitive roots (mod 79).