# Find all solutions that satisfy $x^2 + x \equiv 0 \pmod {4000}$

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

• 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. – Bill Dubuque Nov 4 '18 at 17:30
• Can you elaborate some more please – Wallace Nov 4 '18 at 17:36
• 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. – Bill Dubuque Nov 4 '18 at 17:42
• A modification of the methods outlined here will settle this w.r.t. any modulus. In other words, Bill Dubuque's suggestion. – Jyrki Lahtonen Nov 4 '18 at 18:40

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

• "$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 – Wallace Nov 4 '18 at 18:17
• 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. – Bill Dubuque Nov 4 '18 at 18:19

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.