Determine which of the following numbers are a primitive root of 11:
(a) 3 (b) 5 (c) 7
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,11)=1$, the order exists.
The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.
The following calculations show the order of $3 \pmod {11}$ is 5.
| n | 3^n | 3^n mod 11 |
| 2 | 9 | 9 |
| 5 | 243 | 1 |
| 10 | 59049 | 1 |
The order is not $\phi(11)=10$, and so 3 is not a primitive root of 11.
(b) Since $\gcd(5,11)=1$, the order exists.
The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.
The following calculations show the order of $5 \pmod {11}$ is 5.
| n | 5^n | 5^n mod 11 |
| 2 | 25 | 3 |
| 5 | 3125 | 1 |
| 10 | 9765625 | 1 |
The order is not $\phi(11)=10$, and so 5 is not a primitive root of 11.
(c) Since $\gcd(7,11)=1$, the order exists.
The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.
The following calculations show the order of $7 \pmod {11}$ is 10.
| n | 7^n | 7^n mod 11 |
| 2 | 49 | 5 |
| 5 | 16807 | 10 |
| 10 | 282475249 | 1 |
The order is $\phi(11)=10$, and so 7 is a primitive root of 11.