Find all incongruent solutions of $x^8\equiv3\pmod{13}$. Find all incongruent solutions of $x^8\equiv3\pmod{13}$.
I know that $2$ is a primitive root of $13$ and that $2^4\equiv3\pmod{13}$, so we want to solve $x^8\equiv2^4\pmod{13}$.
Now, $\gcd(8,\phi(13))=\gcd(8,12)=4$ divides the exponent of $2$, which is $4$, so $x^8\equiv3\pmod{13}$ has exactly $4$ incongruent solutions modulo $13$.
I was able to find on my calculator (using brute force) that these solutions are $4,6,7,$ and $9$ (i.e. $\pm4,\pm6$), but how would I go about finding them without using a calculator?

We can just list all the values $x^8$ takes for $x\in\Bbb{Z}/13\Bbb{Z}$:
$$\begin{array}{c|cccccccccccccc} 
x   & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12\\
\hline
x^8 & 0 & 1 & 9 & 9 & 3 & 1 & 3 & 3 & 1 & 3 & 9 & 9 & 1 \\
\end{array}$$
If you use the fact that $(-x)^8=x^8$ and $(xy)^8=x^8y^8$, the only 'big' computations you need are
$$2^8\equiv256\equiv9\pmod{13}\qquad\text{ and }\qquad3^8\equiv6561\equiv9\pmod{13},$$
and even these can be broken down. Anyway, the solutions are clearly $4$, $6$, $7$ and $9$.
