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 have that $Z/13Z$ it's a field. In $Z/13Z$ the inverse of $3$ is $9$ so if you multiply by $9$ will have $9x^8$ is congruent by 1 modulo 9. In Z/13Z,  $x^{12}$ is congruent by 1 modulo 13. So $9x^8-x^{12}$ is congruent by 0 modulo 13. So $x^8(x^4-9)$ is congruent with 0 modulo 13. Result that x is congruent by 0 mod 13(is not solution) or $x^4-9=(x^2-3)(x^2+3)$ is congruent by 0 modulo 13 and now it is more clear.
