Determine which of the following numbers are a primitive root of 7:
(a) 3 (b) 5
We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.
(a) Since $\gcd(3,7)=1$ then the order exists.
Here $\phi(n)=6$. The order of 3 is a factor of $\phi(n)=6$. These factors are 1,2, 3, 6. These are the only ones we need to test.
The following calculations show the order of 3 is 6 modulo 7.
| n | 3^n | 3^n mod 7 |
| 2 | 9 | 2 |
| 3 | 27 | 6 |
| 6 | 729 | 1 |
Since the order is also $\phi(7)=6$, then 3 is a primitive root of 7.
(b) Since $\gcd(5,7)=1$ then the order exists.
Here $\phi(n)=6$. The order of 5 is a factor of $\phi(n)=6$. These factors are 1,2, 3, 6. These are the only ones we need to test.
The following calculations show the order of 5 is 6 modulo 7.
| n | 5^n | 5^n mod 7 |
| 2 | 25 | 4 |
| 3 | 125 | 6 |
| 6 | 15625 | 1 |
Since the order is also $\phi(7)=6$, then 5 is a primitive root of 7.