Wednesday, 28 December 2016

Equivalence of congruences - why are these congruences equivalent?




I'm reading a solution of the following congruence: x59604mod2013. It says that it is equivalent to the following system of congruences:
{x59604mod3x59604mod11x59604mod61
Why?



EDIT:



I know that 2013=31161|x59604. But why is this information sufficient to say that 3,11,61 all divide x59604 when considered separately?


Answer



Hint   If m,n are coprime then lcm(m,n)=mn,  therefore




ab(modm,n)m,nabmnabab(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,nklcm(m,n)k


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