Wednesday 28 December 2016

Equivalence of congruences - why are these congruences equivalent?




I'm reading a solution of the following congruence: $x^{59} \equiv 604 \mod 2013$. It says that it is equivalent to the following system of congruences:
$$\begin{cases} x^{59} \equiv 604 \mod 3 \\ x^{59} \equiv 604 \mod 11\\ x^{59} \equiv 604 \mod 61\end{cases}$$
Why?



EDIT:



I know that $2013=3*11*61|x^{59}-604$. But why is this information sufficient to say that $3,11,61$ all divide $x^{59}-604$ when considered separately?


Answer



Hint $\ $ If $\,m,n\,$ are coprime then $\,{\rm lcm}(m,n) = \color{#c00}{mn},\ $ therefore




$$ a\equiv b\!\!\!\pmod{\!m,n} \iff m,n\mid a-b\color{#0a0}\iff \color{#c00}{mn}\mid a-b\iff a\equiv b\!\!\!\pmod{mn}$$



Applied twice yields the claim. This is a special case of CRT = Chinese Remainder Theorem.



Remark $\ $ The $\,\rm\color{#0a0}{middle}\,$ equivalence employs the universal property of lcm, $ $ i.e.



$$ m,n\mid k\color{#0a0}\iff {\rm lcm}(m,n)\mid k$$


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