Trying to solve this system of congruences:
$n \equiv 4 \quad \text{(mod 19)}$ $n \equiv 3 \quad \text{(mod 10)}$ $n \equiv 6 \quad \text{(mod 11)}$
how do I solve this?
Trying to solve this system of congruences:
$n \equiv 4 \quad \text{(mod 19)}$ $n \equiv 3 \quad \text{(mod 10)}$ $n \equiv 6 \quad \text{(mod 11)}$
how do I solve this?
It's a simple application of Easy CRT (below). With practice, this can be calculated mentally.
$\!\!\!\!\!\!\!\!\!\rm \begin{eqnarray}\rm n&\equiv&\rm 6\ (mod\ 11) \\ \rm n&\equiv&\rm 4\ (mod\ 19)\end{eqnarray}\!\!\! \iff\!\! n \equiv 4 + 19\: \bigg[\!\!\frac{6\!-\!4}{19} mod\ 11\bigg]\! \equiv 61\ (mod\ 209)\ \ by\ \frac{2}{19}\equiv \frac{-9}{-3}\equiv 3 \ (mod\ 11)$
$\rm\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \begin{eqnarray}\rm n&\equiv&\rm\ 3\ \ (mod\ 10) \\ \rm n&\equiv&\rm 61\: (mod\ 209)\end{eqnarray}\!\!\! \iff\!\! n \equiv 61 + 209 \bigg[\!\!\frac{3\!-\!61}{209} mod\ 10\bigg]\! \equiv -357\ (mod\ 2090)\ \ by\ \frac{2}{-1}\equiv -2\: (mod\ 10)$
THEOREM (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ n^{-1}\ $ exists $\rm\ (mod\ m)\ \ $ and
$\rm\displaystyle\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray}\!\!\! \iff\! x\: \equiv\: b + n\ \bigg[\frac{a\!-\!b}{n}\ mod\ m\:\bigg]\ \ (mod\ m\:\!n)$
Proof $\rm\ (\Leftarrow)\quad mod\:\ n\!:\:\ x\:\equiv\: b + n\ (\cdots)\equiv b\:,\ $ and $\rm\ mod\ m\!:\ x\equiv b + (a-b)\ n/n\: \equiv\: a\:.$
$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ m\:\!n)\ $ since if \rm\ x',x\ are solutions then \rm\ x'\equiv x\ mod $\rm\:m,n\:$ therefore \rm\ m,n\ |\ x'-x\ \Rightarrow\ m\:\!n\ |\ x'-x\ \ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:\!n\ \ \ $ QED
$ \begin{eqnarray} 10\cdot11&\equiv&0&\mod10\;,\\ 10\cdot11&\equiv&0&\mod11\;,\\ 10\cdot11&\equiv&15&\mod19\;. \end{eqnarray} $
Now you just need to solve $15x\equiv4\mod19$, and then $10\cdot11\cdot x$ solves the first congruence without disturbing the other two. Then you can do the same thing for the other two.