3
$\begingroup$

I've gone ahead and split up $4000$ into $2^{5} 5^{3}$ and solved each solution separately - as in applied Hensel's lemma for mod 2 and mod 5 solutions separately, I just don't understand how I would combine these solutions.

For mod $2^{5}$, after lifting the final solution I got was $x = 31$ (set of solutions would be $x = 31 + 32n$)

For mod $5^{3}$, after lifting the final solution I got was $x = 124$ (set of solutions would be $x = 124 + 125n$)

How can I combine what I got to get the final answer? Because these do not work for mod 4000

$\endgroup$
  • 2
    $\begingroup$ e.g. CRT. Note for $p$ prime: $\ p^n\mid x(x\!+\!1)\iff p^n\mid x\,$ or $\,p^n\mid x\!+\!1\,$ since $x$ and $\,x+1$ are coprime. $\endgroup$ – Bill Dubuque Nov 4 '18 at 17:30
  • $\begingroup$ Can you elaborate some more please $\endgroup$ – Wallace Nov 4 '18 at 17:36
  • 1
    $\begingroup$ We get solutions $\,x\equiv 0,-1\,$ mod $32$ and $125$ which combine to $4$ solutions mod $4000$ viz. $\,x\equiv (0,0),\, (0,-1),\,(-1,0),\,(-1,-1) $ mod $(32,125)$ The 1st and 4th solutions are $0$ and $-1\pmod{4000}$ and the third is computable from the 2nd since $\,(0,-1)+(-1,0) = (-1,-1).\,$ So you need only ompute the 2nd (or 3rd) by CRT. $\endgroup$ – Bill Dubuque Nov 4 '18 at 17:42
  • 1
    $\begingroup$ A modification of the methods outlined here will settle this w.r.t. any modulus. In other words, Bill Dubuque's suggestion. $\endgroup$ – Jyrki Lahtonen Nov 4 '18 at 18:40
2
$\begingroup$

You don't need Hensel's Lemma. This can be solved completely in a minute of mental arithmetic using only a single simple CRT calculation.

If $\,p\,$ is prime then $\,p^n\mid x(x\!+\!1)\iff p^n\mid x\,$ or $\,p^n\mid x\!+\!1\,$ by $\,x,\,x\!+\!1$ coprime.

So $\,2^5\mid x(x\!+\!1)\iff x\equiv 0,-1\pmod{\!32},\,$ and $\,5^3\mid x(x\!+\!1)\iff x\equiv 0,-1\pmod{\!125}$

By CRT these root pairs combine to exactly $4$ roots mod $32*125 = 4000,\,$ namely

$x \equiv \ \ (0,\,0)\ \ \ \ \pmod{32,125}\iff x\equiv\ \,0\ \pmod{\!n=4000}$

$x \equiv (-1,-1)\pmod{32,125}\iff x\equiv -1\pmod{\!n}$

$x \equiv (\color{#0a0}{-1},\,\color{#c00}{0})\ \ \pmod{32,125}\iff x\equiv 1375\pmod{4000}\ $ since by CRT, mod $32$ we have:

$\!\color{#0a0}{{-}1}\equiv x\equiv \color{#c00}{125k}\equiv -3k\!\iff\! 3k\equiv 1\equiv 33\!\iff\! k\equiv 11\!\iff\! x= 125(11)\equiv 1375\pmod{\!n} $

$x\equiv (0,-1)\ \ \pmod{32,125}\iff x\equiv (-1,-1)-(-1,0) = -1-1375 \equiv 2624\pmod{\!n}$

$\endgroup$
  • $\begingroup$ "$x \equiv (-1,0)\ \ \ \pmod{32,125}\iff x\equiv 1375\pmod{4000}\ $ since modul0 $32$ we have" I have a hard time understanding how you got this..? Could you please elaborate $\endgroup$ – Wallace Nov 4 '18 at 18:17
  • 1
    $\begingroup$ That CRT calculation is explained in the line just below that. viz. $\,x\equiv 0\pmod{125}\iff x = 125k.\,$ Next plug that into $\,x\equiv -1\pmod{32}$ and solve for $k$ as we did above. $\endgroup$ – Bill Dubuque Nov 4 '18 at 18:19
2
$\begingroup$

You have $x\equiv 31\equiv -1\pmod{32}$ and $x\equiv 124\equiv -1\pmod{125}$, hence $x\equiv -1\pmod{4000}$.

In general, given a system of linear congruences you have to apply the Chinese Remainder Theorem: see for example my answer here.

$\endgroup$

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.