3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Have you studied Quadratic Reciprocity (squares modulo something)? $\endgroup$
    – Timbuc
    Commented May 18, 2015 at 11:32
  • $\begingroup$ Do you know about discrete logarithm? It could help right here, if you could find a quadratic non-residue modulo 125. $\endgroup$
    – Atvin
    Commented May 18, 2015 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – qiubit
    Commented May 18, 2015 at 11:33
  • 1
    $\begingroup$ Are you familiar with Hensel's Lemma? $\endgroup$
    – Hayden
    Commented May 18, 2015 at 11:38

5 Answers 5

Reset to default
5
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ For a generalization of this technique, see Hensel's lemma. $\endgroup$
    – lhf
    Commented May 18, 2015 at 12:03
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ +1! that is even neater than Timbuc's nice answer - surely the optimal solution for this particular little puzzle! $\endgroup$
    – David Holden
    Commented May 18, 2015 at 17:11
2
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – lhf
    Commented May 18, 2015 at 12:35
  • $\begingroup$ +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. $\endgroup$
    – David Holden
    Commented May 18, 2015 at 17:04
  • $\begingroup$ OK, for $0 \le \ x \lt 5^3$ there exist $a,b,c \in \{0,1,2,3,4\}$ s.t. $x = a + 5b + 25c$, $\endgroup$
    – CopyPasteIt
    Commented Jan 21, 2023 at 14:50
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .