Consider the congruence
$$ x^d - 1 \equiv 0 \pmod {19} $$
Solve this congruence for all $d$ which are the positive factors of $\phi(19)$.
What do you notice about your result when $d = \phi(19)$?
The positive factors of $\phi(19)=18$ are 1, 2, 3, 6, 9, 18. The congruences we need to solve are
(a) $ x^1 \equiv 1 \pmod {19} $
(b) $ x^2 \equiv 1 \pmod {19} $
(c) $ x^3 \equiv 1 \pmod {19} $
(d) $ x^6 \equiv 1 \pmod {19} $
(e) $ x^9 \equiv 1 \pmod {19} $
(f) $ x^{18} \equiv 1 \pmod {19} $
From Exercise (6.3).7 we know that 2 is primitive root of 19. The following is a table of indices of root 2.
| ind_2 (a) | a = 2^ind_r(a) mod 19 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 13 |
| 6 | 7 |
| 7 | 14 |
| 8 | 9 |
| 9 | 18 |
| 10 | 17 |
| 11 | 15 |
| 12 | 11 |
| 13 | 3 |
| 14 | 6 |
| 15 | 12 |
| 16 | 5 |
| 17 | 10 |
| 18 | 1 |
(a) Using Proposition (6.19), we have $1 \mid 18$, and so the congruence $ x^1 \equiv 1 \pmod {19} $ has 1 incongruent solution.
We can immediately see that $x \equiv 1 \pmod {19}$ is a solution.
(b) Using Proposition (6.19), we have $2 \mid 18$, and so the congruence $ x^2 \equiv 1 \pmod {19} $ has 2 incongruent solutions.
Applying Propositions (6.15) and (6.16) to the congruence gives
$$ 2 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$
Simplifying
$$ \text{ind}_r (x) \equiv 0 \pmod {9} $$
This gives is $\text{ind}_r(a) \equiv 9, 18 \pmod {18}$.
The table of indices gives us the 2 incongruent solutions $x \equiv 1, 18 \pmod {19}$.
(c) Using Proposition (6.19), we have $3 \mid 18$, and so the congruence $ x^3 \equiv 1 \pmod {19} $ has 3 incongruent solutions.
Applying Propositions (6.15) and (6.16) to the congruence gives
$$ 3 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$
Simplifying
$$ \text{ind}_r (x) \equiv 0 \pmod {6} $$
This gives is $\text{ind}_r(a) \equiv 6, 12, 18 \pmod {18}$.
The table of indices gives us the 3 incongruent solutions $x \equiv 1, 7, 11 \pmod {19}$.
(d) Using Proposition (6.19), we have $6 \mid 18$, and so the congruence $ x^6 \equiv 1 \pmod {19} $ has 6 incongruent solutions.
Applying Propositions (6.15) and (6.16) to the congruence gives
$$ 6 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$
Simplifying
$$ \text{ind}_r (x) \equiv 0 \pmod {3} $$
This gives is $\text{ind}_r(a) \equiv 3, 6, 9, 12, 15, 18 \pmod {18}$.
The table of indices gives us the 6 incongruent solutions $x \equiv 1, 7, 8, 11, 12, 18 \pmod {19}$.
(e) Using Proposition (6.19), we have $9 \mid 18$, and so the congruence $ x^9 \equiv 1 \pmod {19} $ has 9 incongruent solutions.
Applying Propositions (6.15) and (6.16) to the congruence gives
$$ 9 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$
Simplifying
$$ \text{ind}_r (x) \equiv 0 \pmod {2} $$
This gives is $\text{ind}_r(a) \equiv 2, 4, 6, 8, 10, 12, 14, 16, 18 \pmod {18}$.
The table of indices gives us the 9 incongruent solutions $x \equiv 1, 4, 5, 6, 7, 9, 11, 16, 17 \pmod {19}$.
(f) Using Proposition (6.19), we have $18 \mid 18$, and so the congruence $ x^{18} \equiv 1 \pmod {19} $ has 18 incongruent solutions.
Applying Propositions (6.15) and (6.16) to the congruence gives
$$ 18 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$
Simplifying
$$ \text{ind}_r (x) \equiv 0 \pmod {1} $$
This gives is $\text{ind}_r(a) \equiv 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 \pmod {18}$.
The table of indices gives us the 18 incongruent solutions $x \equiv 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 \pmod {19}$.
When $d=\phi(19)=18$, Fermat's Little Theorem applies, where $a^{p-1} \equiv 1 \pmod p$ for prime $p$ and $\gcd(a,1)=1$.