Here's a congruence I'm trying to solve:
$$x^2\equiv24 \mod 125$$
What are the techniques I could use to solve it? I know about Euler's phi function, Fermat's little theorem and Chinese remainder theorem but they all seem inapplicable here. Is there something else I could use?
Best Answer
You can try this by "chunks". Since $\;24=4\cdot6\;$ and clearly $\;4\;$ is the square of $\;2\;$ , we can concentrate on $\;6\;$...and we're in luck since
$$6=256\pmod{125}=6+2\cdot125$$
So that $\;16^2=6\pmod{125}\;$ , and finally
$$(32)^2=2^216^2=4\cdot6=24\pmod{125}$$