System of 3 Congruences

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?

-
I'm sorry I don't quite follow the Chinese Remainder Theorem, can you explain how it would apply for these numbers? – Dominick Gerard Mar 30 '12 at 14:43

2 Answers

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.

-