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
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.
No comments:
Post a Comment