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 \,2^5\mid x(x\!+\!1)\iff x\equiv 0,-1\pmod{\!32},\, and \,5^3\mid x(x\!+\!1)\iff x\equiv 0,-1\pmod{\!125}



By CRT these root pairs combine to exactly 4 roots mod 32*125 = 4000,\, namely



x \equiv \ \ (0,\,0)\ \ \ \ \pmod{32,125}\iff x\equiv\ \,0\ \pmod{\!n=4000}



x \equiv (-1,-1)\pmod{32,125}\iff x\equiv -1\pmod{\!n}



x \equiv (\color{#0a0}{-1},\,\color{#c00}{0})\ \ \pmod{32,125}\iff x\equiv 1375\pmod{4000}\ since by CRT, mod 32 we have:




\!\color{#0a0}{{-}1}\equiv x\equiv \color{#c00}{125k}\equiv -3k\!\iff\! 3k\equiv 1\equiv 33\!\iff\! k\equiv 11\!\iff\! x= 125(11)\equiv 1375\pmod{\!n}



x\equiv (0,-1)\ \ \pmod{32,125}\iff x\equiv (-1,-1)-(-1,0) = -1-1375 \equiv 2624\pmod{\!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}...