# Index arithmetic for $9x^8 \equiv b \pmod{17}$

I wish to find all b such that $9x^8 \equiv b \pmod{17}$ has a solution using index arithmetic. I have figured out that 3 is a primitive root, giving:

$$\text{ind}_39+8\text{ind}_3x \equiv 2+8\text{ind}_3x \equiv \text{ind}_3b \pmod{16}$$

But, where can I go from here? A hint would be appreciated.

• $$x^8\in\{-1,0,1\}\pmod{17},$$ can you guess why? – Jack D'Aurizio Dec 19 '17 at 2:26
• No, can you explain further? – zz20s Dec 19 '17 at 2:27
• en.wikipedia.org/wiki/Fermat%27s_little_theorem – DanielV Dec 19 '17 at 2:31
• AH! Yes. Thank you. That clears it right up. Does anyone know of a way to salvage my approach, though? – zz20s Dec 19 '17 at 2:32
• @zz20s: for any odd prime $p$ (and $17$ is an odd prime) $$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$$ is the Legendre symbol, which equals zero if $a$ is a multiple of $p$ and $\pm 1$ otherwise, according to $a$ being a quadratic residue $\!\pmod{p}$ or not. In particular the given problem has a solution iff $b\in\{0,8,9\}\pmod{17}$. – Jack D'Aurizio Dec 19 '17 at 2:34

Clearly, if $17|b,17\mid x$
$$\text{ind}_3b-2\equiv8\text{ind}_3x \pmod{16}\begin{cases}0 &\mbox{if } \text{ind}_3x \text{ is even}\iff b\equiv3^2\pmod{17} \\8& \mbox{if }\text{ind}_3x \text{ is odd}\iff b\equiv3^{8+2}\end{cases}$$