Show that 3 is a primitive root modulo 17. Complete the following table:
| a mod 17 | ind_3(a) |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | |
| 14 | |
| 15 | |
| 16 |
Solve the following equations:
(a) $x^4 \equiv 4 \pmod {17}$
(b) $12x^8 \equiv 5 \pmod {17}$
(c) $12x^8 \equiv 6 \pmod {17}$
(d) $5^x \equiv 3 \pmod {17}$
The table of indices is calculated as follows. It confirms that 3 is a primitive root modulo 17 because the order of 3 modulo 17 is $\phi(17)=16$.
| a mod 17 | ind_3(a) |
| 1 | 16 |
| 2 | 14 |
| 3 | 1 |
| 4 | 12 |
| 5 | 5 |
| 6 | 15 |
| 7 | 11 |
| 8 | 10 |
| 9 | 2 |
| 10 | 3 |
| 11 | 7 |
| 12 | 13 |
| 13 | 4 |
| 14 | 9 |
| 15 | 6 |
| 16 | 8 |
(a) We use Propositions (6.15) and (6.16) on $x^4 \equiv 4 \pmod {17}$ to give
$$ \begin{align} \text{ind}_3 (x^4) & \equiv \text{ind}_3 (4) \pmod {\phi(17)} \\ \\ 4 \; \text{ind}_3 (x) & \equiv 12 \pmod {16} \end{align} $$
Since $g = \gcd(16,4)=4$ and $g \mid 12$, this linear congruence has 4 incongruent solutions modulo 16.
Dividing through by 4
$$ \text{ind}_3 (x) \equiv 3 \pmod {4} $$
The four solutions modulo 16 are $\text{ind}_3(x) = 3, 7, 11, 15$. The table gives us the general solution for $x$,
$$ x \equiv 10, 11, 7, 6 \pmod {17} $$
(b) We use Propositions (6.15) and (6.16) on $12x^8 \equiv 5 \pmod {17}$ to give
$$ \begin{align} \text{ind}_3 (12x^8) & \equiv \text{ind}_3 (5) \pmod {\phi(17)} \\ \\ 13 + 8 \; \text{ind}_3 (x) & \equiv 5 \pmod {16} \\ \\ 8 \; \text{ind}_3 (x) & \equiv 8 \pmod {16} \end{align} $$
Since $g = \gcd(16,8)=8$ and $g \mid 8$, this linear congruence has 8 incongruent solutions modulo 16.
Dividing through by 8
$$ \text{ind}_3 (x) \equiv 1 \pmod {2} $$
The 8 solutions modulo 16 are $\text{ind}_3(x) = 1, 3, 5, 7, 9, 11, 13, 15$. The table gives us the general solution for $x$,
$$ x \equiv 3, 10, 5, 11, 14, 7, 12, 6 \pmod {17} $$
(c) We use Propositions (6.15) and (6.16) on $12x^8 \equiv 6 \pmod {17}$ to give
$$ \begin{align} \text{ind}_3 (12x^8) & \equiv \text{ind}_3 (6) \pmod {\phi(17)} \\ \\ 13 + 8 \; \text{ind}_3 (x) & \equiv 15 \pmod {16} \\ \\ 8 \; \text{ind}_3 (x) & \equiv 2 \pmod {16} \end{align} $$
Since $g = \gcd(16,8)=8$ but $g \not \mid 2$, this linear congruence has no solutions.
(d) We use Propositions (6.15) and (6.16) on $5^x \equiv 3 \pmod {17}$ to give
$$ \begin{align} x \; \text{ind}_3 (5) & \equiv \text{ind}_3 (3) \pmod {\phi(17)} \\ \\ 5x & \equiv 1 \pmod {16} \end{align} $$
Since $g = \gcd(16,5)=1$ and $g \mid 1$, this linear congruence has 1 incongruent solution modulo 16.
Testing values between 1 and 15 gives us the solution
$$ x \equiv 13 \pmod{16} $$