Congruence equation with polynomials So, I tried solving $x^{12} \equiv 37 \mod 41$. I tried to use indices technique (not sure if everyone is familiar with that) but ended up 3 solutions short (there are 4 solutions) and calculations were tedious, to say at least.
Could anyone provide a method for solving congruences like this one, possibly using same technique or something elementary?
Thank you very much!
 A: Fill in details: doing arithmetic modulo $\;41\;$ all along, we get:
$$x^{12}=37=-4\implies x^{12}+4=0\implies (x^6-2i)(x^6+2i)=0$$
with $\;i^2=-1\;$ , which we know it exists (why and what number is square root of $\;-1\;$ here?)
Now, for example:
$$0=x^6+18=(x^3-3\sqrt2\,i)(x+3\sqrt2\,i)$$
and we also should (or could) know that $\;2\;$ is a quadratic residue since $\;41=\pm1\pmod8\;$ ...
Try now to take it from here...and I've no idea what the indices technique is and  couldn't find it in google.
A: We would like to find a primitive gernerator for $\mathbb{Z}_{41}$ ... so lets try $2$ ...$2,4,8,16,32,23,5,10,20,40$. Now $40 \equiv -1 \mod 41$ so $2^{20}=1$ ... carrying on a bit ...
$39,\color{red}{37},33,25,9,18,36,31,21,1$. So it turns out that $x=2$ is a solution.
To find the other three solutions we shall use  $2^{20}=1$
\begin{eqnarray*}
37 \equiv 2^{12} \equiv 2^{12+3 \times 20} \equiv 2^{72} \equiv (2^{6})^{12} \equiv 23^{12} \mod 41 \\
37 \equiv 2^{12} \equiv 2^{12+6 \times 20} \equiv 2^{132} \equiv (2^{11})^{12} \equiv 39^{12} \mod 41 \\
37 \equiv 2^{12} \equiv 2^{12+9 \times 20} \equiv 2^{192} \equiv (2^{16})^{12} \equiv 18^{12} \mod 41 
\end{eqnarray*}
So the four solutions are $x=\color{red}{2,23,39,18}$.
