Assume that 2 is a primitive root of modulo 19. Solve the following:
(a) $6x^5 \equiv 7 \pmod {19}$
(b) $4x^9 \equiv 4 \pmod {19}$
(c) $x^6 \equiv 7 \pmod {19}$
We start by building a table of indices and the corresponding reduced residue system.
| ind_2(a) | a = 2^(ind_2) 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) We use Propositions (6.15) and (6.16) on $6x^5 \equiv 7 \pmod {19}$ to give
$$ \begin{align} \text{ind}_2 (6x^5) & \equiv \text{ind}_2 (7) \pmod {\phi(19)} \\ \\ \text{ind}_2 (6) + 5\;\text{ind}_2 (x) & \equiv \text{ind}_2 (7) \pmod {18} \\ \\ 5\;\text{ind}_2 (x) & \equiv 10 \pmod {18} \end{align} $$
Since $g = \gcd(18,5)=1$ and $g \mid 10$, this linear congruence has 1 incongruent solution modulo 18.
Dividing through by 5
$$ \text{ind}_2 (x) \equiv 2 \pmod {18} $$
This has one solution $\text{ind}_2 = 2$. The table gives us the general solution for $x$,
$$ x \equiv 4 \pmod {19} $$
(b) We use Propositions (6.15) and (6.16) on $4x^9 \equiv 4 \pmod {19}$ to give
$$ \begin{align} \text{ind}_2 (4) + 9\; \text{ind}_2 (x) & \equiv \text{ind}_2(4) \pmod {\phi(19)} \\ \\ 9\; \text{ind}_2 (x) & \equiv 0 \pmod {18} \end{align} $$
Since $\gcd(18,9)=9$ and $g \mid 0$, there are 9 incongruent solutions modulo 18.
Dividing through by 9
$$ \text{ind}_2 (x) \equiv 0 \pmod {2} $$
The nine solutions modulo 18 are $\text{ind}_2 (x) = 0, 2, 4, 6, 8, 10, 12, 14, 16$. The tables of indices gives us the solutions for $x$,
$$ x \equiv 1, 4, 16, 7, 9, 17, 11, 6, 5 \pmod {19} $$
(c) We use Propositions (6.15) and (6.16) on $x^6 \equiv 7 \pmod {19}$ to give
$$ \begin{align} 6 \; \text{ind}_2 (x) & \equiv \text{ind}_2 (7) \pmod {\phi(19)} \\ \\ 6 \; \text{ind}_2 (x) & \equiv 6 \pmod {18)} \end{align} $$
Since $\gcd(18,6)=6$ and $g \mid 6$, there are 6 incongruent solutions modulo 18.
Dividing through by 6
$$ \text{ind}_2 (x) \equiv 1 \pmod {3} $$
The six solutions modulo 18 are $\text{ind}_2 (x) = 1, 4, 7, 10, 13, 16$. The table of indices gives us the solutions for $x$,
$$ x \equiv 2, 16, 14, 17, 3, 5 $$