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?

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