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?
Best Answer
$$x^8-3\equiv x^8-16\equiv \left(x^2-2\right)\left(x^2+2\right)\left(x^4+4\right)\pmod{13}$$
$x^2\equiv 2\pmod{13}$ and $x^2\equiv -2\pmod{13}$ are both unsolvable (by Quadratic Reciprocity), because $13\equiv 5\pmod{8}$.
$$x^4+4\equiv x^4-9\equiv \left(x^2+3\right)\left(x^2-3\right)\pmod{13}$$
$$x^2+3\equiv x^2-36\equiv (x+6)(x-6)\pmod{13}$$
$$x^2-3\equiv x^2-16\equiv (x+4)(x-4)\pmod{13}$$