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?

• Have you studied Quadratic Reciprocity (squares modulo something)? May 18 '15 at 11:32
• Do you know about discrete logarithm? It could help right here, if you could find a quadratic non-residue modulo 125. May 18 '15 at 11:33
• It wasn't covered in my discrete math class (actually all that was covered is everything I've listed above). But I'll read about it, thanks. May 18 '15 at 11:33
• Are you familiar with Hensel's Lemma? May 18 '15 at 11:38

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

• i.e. $\ \sqrt{4\cdot 6} \,=\, 2\sqrt{6}\,\equiv\, 2\sqrt{256}\,\equiv\, \pm 2\cdot 16\ \pmod{125}\ \$ May 18 '15 at 15:07
• For a "direct" proof it is quicker to notice that $\ 24\equiv 1024\equiv 2^{10},\$ see my answer. May 18 '15 at 17:30

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

• For a generalization of this technique, see Hensel's lemma.
– lhf
May 18 '15 at 12:03

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

• +1! that is even neater than Timbuc's nice answer - surely the optimal solution for this particular little puzzle! May 18 '15 at 17:11

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

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

• Since $125$ is not prime, in principle a quadratic equation could have more than two solutions... For instance, $x^2=1 \bmod 8$ has four solutions.
– lhf
May 18 '15 at 12:35
• +1 thank you for reminding me of that @lhf! one peril for the "autodidact" is the persistence of over-restrictive assumptions, which any teacher would probably spot and correct with a judiciously chosen example. MSE has helped me a lot in that way, and i hope it will continue to do so. May 18 '15 at 17:04