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

Question

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

Answer 1

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

As here, 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}$

Answer 2

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.