How to solve $x^2 + x = 0 (\mod 10^5)$?

Question

I've tried to solve it in the following way:

First let's solve $x^2+x\equiv 0\ (\mod10)$. Solutions are $-1, 0, 4, 5$.

So $-1$ and $0$ are obviously solutions of $x^2 + x \equiv 0\ (\mod 10^5)$. Now let's solve this for $4$ and $5$:

Let $x = 10k + 4$, then put this $x$ into $x^2 + x \equiv 0\ (\mod 100)$. So after a few operation we get $k=-2\ (\mod 10)$. Now let $l = 10k + 2$ and $x = 10\cdot (10k + 2) + 4$. Now we can solve our equation by modulo $1000$. Then we keep doing similar steps until modulo $10^5$ solution is found.

The problem is we need to operate really big numbers. And we need to do it twice (for both roots $4$ and $5$). Is there any less complicated solution?

Answer 1

$10 = 2 \times 5$, so you should really do this mod $2^5$ and mod $5^5$ and use CRT. Since $x^2 + x = x (x + 1)$ and $\gcd(x,x+1) = 1$, $x^2+x \equiv 0 \mod p^n$ (where $p$ is prime) iff either $x \equiv 0 \mod p^n$ or $x \equiv -1 \mod p^n$.

Answer 2

To expand just a bit on Robert’s answer, in addition to $0$ and $99999$, which are already congruent to $0$ and $-1$ modulo $10^5$, you should be able to find $n$ that’s $\equiv0\pmod{32}$ and $\equiv-1\pmod{3125}$ and $m$ that’s $\equiv-1\pmod{32}$ and $\equiv0\pmod{3125}$.

Answer 3

$x^2 + x = x (x+1)$ At most one of $x$ or $x+1$ is divisible by 2, and likewise by 5. So either one of them is divisible by $10^5$ or one is divisible by $5^5$ and the other by $2^5$.

To find solutions, consider odd multiples of $5^5 = 3125$, add or subtract 1, and see how what the largest power of 2 is that divides the result.

A bit of checking shows that $3\times 5^5 = 9375$, and $9376 = 32\times293$, so $x = 9375$ is a third solution.