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