<s>[INST] How to solve $x^2 + x = 0 (\mod 10^5)$? 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?
 [/INST] $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$.
</s>