Monday, 18 April 2016

modular arithmetic - How to solve x2+x=0(mod105)?



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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...