# Prove x is not congruent

If $\,x \not\equiv15\pmod{17},\text{ then }x^5 \not\equiv2\pmod{17}.$

I tried to take the contrapositive:

If $\,x^5 \equiv2\pmod{17},\text{ then }x \equiv15\pmod{17}$ and

then I assume that $x^5=17y+2$ for some integer $y$

But I am not what to do after this step.

How do I continue?

-

Proving the contrapositive is a good idea.

The key observation is that if $x$ is not divisible by $17$, then $x^{16} \equiv 1(mod\ 17)$ by Euler's theorem. If we assume $x^5 \equiv 2(mod\ 17)$, then it follows that $$15 \equiv -2 \equiv -2 \cdot x^{16} \equiv -2\cdot(x^5)^3\cdot x \equiv -2 \cdot 2^3 \cdot x \equiv -16x \equiv x\ (mod\ 17).$$

-

Will Fermat's Little Theorem do? If $x^5\equiv2\pmod{17}$, then $x^{20}\equiv-1\pmod{17}$ and $x^{40}\equiv1\pmod{17}$. We then have

$$x^{65}\equiv x\equiv2(-1)(1)\equiv-2\equiv15\pmod{17}$$

-

HINT:

$$a\equiv\pm1, a^5\equiv\pm1$$
$$a\equiv\pm2, a^5\equiv\pm32\equiv\mp2$$ and so on