I'm reading a solution of the following congruence: x59≡604mod2013. It says that it is equivalent to the following system of congruences:
{x59≡604mod3x59≡604mod11x59≡604mod61
Why?
EDIT:
I know that 2013=3∗11∗61|x59−604. But why is this information sufficient to say that 3,11,61 all divide x59−604 when considered separately?
Answer
Hint If m,n are coprime then lcm(m,n)=mn, therefore
a≡b(modm,n)⟺m,n∣a−b⟺mn∣a−b⟺a≡b(modmn)
Applied twice yields the claim. This is a special case of CRT = Chinese Remainder Theorem.
Remark The middle equivalence employs the universal property of lcm, i.e.
m,n∣k⟺lcm(m,n)∣k
No comments:
Post a Comment