I've tried to solve it in the following way:
First let's solve x2+x≡0 (mod10). Solutions are −1,0,4,5.
So −1 and 0 are obviously solutions of x2+x≡0 (mod105).
Now let's solve this for 4 and 5:
Let x=10k+4, then put this x into x2+x≡0 (mod100). So after a few operation we get k=−2 (mod10). Now let l=10k+2 and x=10⋅(10k+2)+4. Now we can solve our equation by modulo 1000. Then we keep doing similar steps until modulo 105 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×5, so you should really do this mod 25 and mod 55 and use CRT.
Since x2+x=x(x+1) and gcd, 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