Determine all the incongruent primitive roots of the following primes:
(a) 7 (b) 11 (c) 17 (d) 23
Let's remind ourselves of Corollary (6.9):
Let $a$ modulo $n$ have order $k$. If $\gcd (s, k) = 1$ then $a^s$ has order $k$ where $s$ is a positive integer.
Let's also remind ourselves that if the order of $a$ modulo $n$ is $\phi(n)$, then $a$ is a primitive root of $n$.
Proposition (6.18) is Corollary (6.9) but specifically for prime modulo.
Let $r$ be a primitive root modulo $p$ where $p$ is prime. Then $r^m \pmod p$ is also a primitive root modulo $p$, provided $\gcd(m, p-1) = 1$.
(a) From Exercise (6.3).1 we know that 3 and 5 are primitive roots of 7.
Starting with $3$ as a known primitive root of 7, Proposition (6.18) tells is that $3^m \pmod 7$ is also a primitive root modulo 7, provided $\gcd(m,6)=1$. This gives $m=1,5$.
And so the following are primitives roots of 7,
$ 3^1 \equiv 1 \pmod 7 $
$ 3^5 \equiv 243 \equiv 5 \pmod 7$
The incongruent primitive roots of 7 are 3 and 5.
(b) From Exercise (6.3).2 we know that 7 is a primitive root of 11.
Starting with $7$ as a known primitive root of 11, Proposition (6.18) tells is that $7^m \pmod {11}$ is also a primitive root modulo 11, provided $\gcd(m,10)=1$. This gives $m=1,3, 7, 9$.
And so the following are primitive roots of 7,
$ 7^1 \equiv 7 \pmod {11} $
$ 7^3 \equiv 343 \equiv 2 \pmod {11} $
$ 7^7 \equiv 823543 \equiv 6 \pmod {11} $
$ 7^9 \equiv 40353607 \equiv 8 \pmod {11} $
The incongruent primitive roots of 11 are 2, 6, 7, 8.
(c) From Exercise (6.3).8 we know that 3 is a primitive root of 17.
Starting with $3$ as a known primitive root of 17, Proposition (6.18) tells is that $3^m \pmod {17}$ is also a primitive root modulo 17, provided $\gcd(m,16)=1$. This gives $m=1, 3,5, 7, 9, 11, 13, 15$.
The following table shows the calculation of the primitive roots of 17.
| m | 3^m | 3^m mod 17 |
| 1 | 3 | 3 |
| 3 | 27 | 10 |
| 5 | 243 | 5 |
| 7 | 2187 | 11 |
| 9 | 19683 | 14 |
| 11 | 177147 | 7 |
| 13 | 1594323 | 12 |
| 15 | 14348907 | 6 |
The incongruent primitive roots of 17 are 3, 5, 6, 7, 10, 11, 12, 14.
(d) No previous exercise gives us a primitive root of 23, so we need to find one first.
A primitive root $r$ modulo 23 has an order $\phi(23)=22$. More generally the order of any number divides $\phi(n)$, so we only need to test positive factors of 22, which are 1, 2, 11, 22.
The following table of calculations shows that 2 and 3 are not primitive roots of 23, but 5 is.
| index i | 2^i mod 23 | 3^i mod 23 | 5^i mod 23 |
| 1 | 2 | 3 | 5 |
| 2 | 4 | 9 | 2 |
| 11 | 1 | 1 | 22 |
| 22 | 1 |
Starting with $5$ as a known primitive root of 23, Proposition (6.18) tells is that $5^m \pmod {23}$ is also a primitive root modulo 23, provided $\gcd(m,22)=1$. This gives $m=1, 3, 5, 7, 9, 13, 15, 17, 19, 21$.
The following table shows the calculation of the primitive roots of 23.
| m | 5^m | 5^m mod 23 |
| 1 | 5 | 5 |
| 3 | 125 | 10 |
| 5 | 3125 | 20 |
| 7 | 78125 | 17 |
| 9 | 1953125 | 11 |
| 13 | 1220703125 | 21 |
| 15 | 30517578125 | 19 |
| 17 | 762939453125 | 15 |
| 19 | 19073486328125 | 7 |
| 21 | 476837158203125 | 14 |
The incongruent primitive roots of 23 are 5, 7, 10, 11, 14, 15, 17, 19, 20, 21.