Exercise (6.3).11

Determine the integers $a$ such that $1 \le a \le 16$ and $ax^6 \equiv 8 \pmod {17}$ has solutions.

We re-use the table of indices from Exercise (6.3).8, using as a primitive root modulo 17.

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

We use Propositions (6.15) and (6.16) on $ax^6 \equiv 8 \pmod {17}$ to give

$$ \begin{align} \text{ind}_3 (a)+  6 \; \text{ind}_3 (x)  & \equiv \text{ind}_3 (8) \pmod {\phi(17)} \\ \\   6 \; \text{ind}_3 (x)  & \equiv 10 - \text{ind}_3 (a) \pmod {16}  \end{align} $$

For this linear congruence to have a solution, we $\gcd(16, 6)=2$ must divide $10 - \text{ind}_3 (a)$.

The following table shows these calculations for $1 \le a \le 16$.

a mod 17	Ind_3(a)	10 – ind_3(a) mod 2
1	16	0
2	14	0
3	1	1
4	12	0
5	5	1
6	15	1
7	11	1
8	10	0
9	2	0
10	3	1
11	7	1
12	13	1
13	4	0
14	9	1
15	6	0
16	8	0

We can see the values of $1 \le a \le 16$ such that $ax^6 \equiv 8 \pmod {17}$ has solutions are

$$ a = 1, 2, 4, 8, 9, 13, 15, 16 $$