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$
  • $\begingroup$ Have you studied Quadratic Reciprocity (squares modulo something)? $\endgroup$ – Timbuc May 18 '15 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 May 18 '15 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 May 18 '15 at 11:33
  • 1
    $\begingroup$ Are you familiar with Hensel's Lemma? $\endgroup$ – Hayden May 18 '15 at 11:38
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$
  • 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 May 18 '15 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 May 18 '15 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$
  • $\begingroup$ For a generalization of this technique, see Hensel's lemma. $\endgroup$ – lhf May 18 '15 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
    $\begingroup$ +1! that is even neater than Timbuc's nice answer - surely the optimal solution for this particular little puzzle! $\endgroup$ – David Holden May 18 '15 at 17:11
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$
1
$\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$
  • 2
    $\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 May 18 '15 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 May 18 '15 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.