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?
 A: $$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}$$
A: 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}$.
A: 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$.
A: 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.
