<s>[INST] 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!
 [/INST] 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}$.
</s>