# 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^{3} (mod 59), 2^{5} (mod 59), …, 2^{19} (mod 59) are also primitive roots of 59:

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)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)Hence, 34, 39, 63, 54, 48 are primitive roots (mod 79).