Solve $9x^8\equiv 8\pmod{17}$

Question

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?

Answer 1

For even powers, you only ever need to test half the range anyway, eg

$$ (17-x)^2 = (17-x) (17-x) = 17(17-x)-17x+x^2 \equiv x^2 \bmod 17 $$

Then add $\{17-x_i\}$ into your answer set $\{x_i\}$

In this case, with $8=16/2$ (and $17$ prime), we also know that $x^{16} \equiv 1 \bmod 17$ (excluding $x=17k$) and that $x^8 \equiv \pm 1 \bmod 17$. We need $x^8\equiv -1 \bmod 17$ in this case. Testing the lower half of the digits, $x=\{1,2,3,4,5,6,7,8\}$ shows answers for $\{3,5,6,7\}$ which meet our needs.

---

Note that we could test whether any answer was feasible before we even started raising numbers to specific powers, which was a nice side effect of having $(p-1)/2$ as the exponent.