Wednesday, 21 January 2015

elementary number theory - Find all solutions that satisfy x2+xequiv0pmod4000



I've gone ahead and split up 4000 into 2553 and solved each solution separately - as in applied Hensel's lemma for mod 2 and mod 5 solutions separately, I just don't understand how I would combine these solutions.




For mod 25, after lifting the final solution I got was x=31 (set of solutions would be x=31+32n)



For mod 53, after lifting the final solution I got was x=124 (set of solutions would be x=124+125n)



How can I combine what I got to get the final answer? Because these do not work for mod 4000


Answer



You don't need Hensel's Lemma. This can be solved completely in a minute of mental arithmetic using only a single simple CRT calculation.



If p is prime then pnx(x+1)pnx or pnx+1 by x,x+1 coprime.




So 25x(x+1)x0,1(mod32), and 53x(x+1)x0,1(mod125)



By CRT these root pairs combine to exactly 4 roots mod 32125=4000, namely



x  (0,0)    (mod32,125)x 0 (modn=4000)



x(1,1)(mod32,125)x1(modn)



x(1,0)  (mod32,125)x1375(mod4000)  since by CRT, mod 32 we have:




1x125k3k3k133k11x=125(11)1375(modn)



x(0,1)  (mod32,125)x(1,1)(1,0)=113752624(modn)


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...