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 pn∣x(x+1)⟺pn∣x or pn∣x+1 by x,x+1 coprime.
So 25∣x(x+1)⟺x≡0,−1(mod32), and 53∣x(x+1)⟺x≡0,−1(mod125)
By CRT these root pairs combine to exactly 4 roots mod 32∗125=4000, namely
x≡ (0,0) (mod32,125)⟺x≡ 0 (modn=4000)
x≡(−1,−1)(mod32,125)⟺x≡−1(modn)
x≡(−1,0) (mod32,125)⟺x≡1375(mod4000) since by CRT, mod 32 we have:
−1≡x≡125k≡−3k⟺3k≡1≡33⟺k≡11⟺x=125(11)≡1375(modn)
x≡(0,−1) (mod32,125)⟺x≡(−1,−1)−(−1,0)=−1−1375≡2624(modn)
No comments:
Post a Comment