Solve the following congruences:
(a) $ x^3 \equiv 1 \pmod 7 $
(b) $ x^4 \equiv 1 \pmod {13} $
(c) $ x^{11} \equiv 1 \pmod {23} $
We will use Proposition (6.19), a specialisation of Proposition (6.17) to prime modulo.
Let $p$ be prime and $d \mid (p-1)$. The congruence $x^d \equiv 1 \pmod p$ has exactly $d$ incongruent solutions.
(a) Using Proposition (6.19), we have $3 \mid 6$ and so the congruence $x^3 \equiv 1 \pmod 7$ has 3 incongruent solutions.
We know from Exercise (6.4).1 that 3 is a primitive root of 7. We will use a table of indices of root 3.
| ind_3 (a) | a = 3^ind_r(a) mod 7 |
| 1 | 3 |
| 2 | 2 |
| 3 | 6 |
| 4 | 4 |
| 5 | 5 |
| 6 | 1 |
| 7 | 3 |
| 8 | 2 |
| 9 | 6 |
| 10 | 4 |
Applying Propositions (6.15) and (6.16) to $x^3 \equiv 1 \pmod 7$ gives
$$ 3 \times \text{ind}_3(x) \equiv 0 \pmod 6 $$
Simplifying
$$ \text{ind}_3(x) \equiv 0 \pmod 2 $$
This gives us $\text{ind}_3(x) \equiv 2, 4, 6$ as solutions.
The table of indices gives us the 3 incongruent solutions $x \equiv 1, 2, 4 \pmod 7$.
(b) Using Proposition (6.19), we have $4 \mid 12$ and so the congruence $x^4 \equiv 1 \pmod {13}$ has $4$ incongruent solutions.
We know from Example 6.19 that 2 is a primitive root of 13. We will use a table of indices of root 2.
| ind_2 (a) | a = 2^ind_r(a) mod 13 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 3 |
| 5 | 6 |
| 6 | 12 |
| 7 | 11 |
| 8 | 9 |
| 9 | 5 |
| 10 | 10 |
| 11 | 7 |
| 12 | 1 |
Applying Propositions (6.15) and (6.16) to $x^4 \equiv 1 \pmod {13}$ gives
$$ 4 \times \text{ind}_2(x) \equiv 0 \pmod {12} $$
Simplifying
$$ \text{ind}_2(x) \equiv 0 \pmod 3 $$
This gives us $\text{ind}_2(x) \equiv 3, 6, 9, 12$ as solutions.
The table of indices gives us the 4 incongruent solutions $x \equiv 1, 5, 8, 12 \pmod 13$.
(c) Using Proposition (6.19), we have $11 \mid2$ and so the congruence $x^11 \equiv 1 \pmod 7$ has 11 incongruent solutions.
We know from Exercise (6.4).1 that 5 is a primitive root of 7. We will use a table of indices of root 5.
| ind_5 (a) | a = 5^ind_r(a) mod 23 |
| 1 | 5 |
| 2 | 2 |
| 3 | 10 |
| 4 | 4 |
| 5 | 20 |
| 6 | 8 |
| 7 | 17 |
| 8 | 16 |
| 9 | 11 |
| 10 | 9 |
| 11 | 22 |
| 12 | 18 |
| 13 | 21 |
| 14 | 13 |
| 15 | 19 |
| 16 | 3 |
| 17 | 15 |
| 18 | 6 |
| 19 | 7 |
| 20 | 12 |
| 21 | 14 |
| 22 | 1 |
Applying Propositions (6.15) and (6.16) to $x^{11} \equiv 1 \pmod {23}$ gives
$$11 \times \text{ind}_5(x) \equiv 0 \pmod {22} $$
Simplifying
$$ \text{ind}_5(x) \equiv 0 \pmod {2} $$
This gives us $\text{ind}_5(x) \equiv 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22$ as solutions.
The table of indices gives us the11 incongruent solutions $x \equiv 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \pmod {23}$.