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 x2+x0 (mod10). Solutions are 1,0,4,5.



So 1 and 0 are obviously solutions of x2+x0 (mod105).
Now let's solve this for 4 and 5:



Let x=10k+4, then put this x into x2+x0 (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

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