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?

One can easily see that $2$ is a primitive root of $13$.
Hence, we can write any number less than $13$ as some power of $2$.
$x^8\equiv3\equiv2^4\pmod{13}$.
Any solution will also be of the form $x=2^m$ for some $1\leq m\leq12$.
So, we have
$(2^m)^8=2^{8m}\equiv2^4\pmod{13}$.
Now, these powers will be congruent modulo $\phi(13)$, giving
$8m\equiv4\pmod{12}$
$8m\equiv16\pmod{12}$
$m\equiv2\pmod3$
$m\equiv2,5,8,$ or $11\pmod{12}$.
So, we have $x\equiv2^2,2^5,2^8,$ or $2^{11}\pmod{13}\implies x\equiv4,6,9,$ or $7\pmod{13}$.
