Solve $x^{2}\equiv 24 \mod 125$ 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?
 A: Here is an elementary approach:
Reduce $x^2 \equiv 24 \bmod 125$ to $x^2 \equiv 24 \equiv -1 \bmod 5$, whose solutions is $x \equiv \pm 2 \bmod 5$.
Write $x=\pm 2 +5y$ and solve $x^2 \equiv 24 \bmod 25$ for $y$. You'll get $y \equiv \pm 1 \bmod 5$. This implies $x \equiv \pm 7 \bmod 25$.
Write $x=\pm 7 + 25z$ and solve  $x^2 \equiv 24 \bmod 125$ for $z$. You'll get  $z \equiv \pm 1 \bmod 5$. This implies $x \equiv \pm 32 \bmod 125$.
A: 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}$$
A: Hint $\,\ {\rm mod}\ 125\!:\,\ \overbrace{1000}^{\large 8\,\cdot\, 125}\equiv 0\,\overset{\large + 24\ }\Longrightarrow\, 24\equiv 1024\equiv 2^{10} = (2^5)^2$
Remark $\ $ Generally one can use Hensel's Lemma, as in lhf's answer, but that is a bit overkill in cases like this where the number is obviously congruent to a well-known power (which happens frequently for small moduli due to the law of small numbers).
A: $$
x^2-24 \equiv_5 0 \tag{1}
$$
has roots 2 and 3.
from $x=2$  seek $t$ such that
$$
(2+5t)^2 +1\equiv_{25} 0
$$
giving 
$$
5 +20t \equiv_{25} 0
$$
so $t=1$
now find $s$ s.t.
$$
(2+5t+25s)^2-24=(7+25s)^2-24\equiv_{125} 0
$$
so
$$
25+350s \equiv_{125} 0
$$
or
$$
1+14s \equiv_5 0
$$
giving $s=1$
so the solution corresponding to the root $2$ of (1) is 32
since the sum of the roots is zero, the other root (corresponding to the root 3 of (1) ) is $-32$ i.e. 93
A: $x^2\equiv 24\pmod{125}$ implies $x^2\equiv 4\pmod{5}$, from which $x=\pm 2\pmod{5}$ or $x=5k\pm 2$.
Since:
$$ (5k\pm 2)^2 = 25 k^2 \pm 20k + 4 $$
it follows that we must have:
$$  5k^2\pm 4k -4 \equiv 0\pmod{25}$$
from which $k\equiv \pm 1\pmod{5}$ or $k=5j\pm 1$. By plugging it back, we may notice that $j\equiv \pm 1\pmod{5}$ is a sufficient condition for solving the previous equation, then it follows that:
$$ x = 5(5(5i\pm 1)\pm 1)\pm 2 $$
so the solutions of the original equation are given by $x\equiv\pm 32\pmod{125}$.
