Solve $x^{2}\equiv 24 \mod 125$

Question

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?

Answer 1

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}$$

Answer 2

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$.

Answer 3

$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}$.

Answer 4

$$ 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

Answer 5

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).