$$
\begin{cases}
x\equiv 2 \pmod{3}\\
x\equiv 1 \pmod{4}\\
x\equiv 3 \pmod{5}
\end{cases}
$$
$
n_1=3\\
n_2=4\\
n_3=5\\
N=n_1 * n_2 * n_3 =60\\
m_1 = 60/3 = 20\\
m_2 = 60/4 = 15\\
m_3 = 60/5 = 12\\
gcd(20,3)=1=-20*1+3*7\\
gcd(15,4)=1=-15*1+4*4\\
gcd(12,5)=1=12*3-5*7\\
x=-20*2-15*1+12*3\equiv -19 \equiv 41 \pmod{60}\\
$
The above is what I've tried so far. Can someone tell me where I'm going wrong? It's my first time doing this and looking at the explanation and examples for the Chinese Remainder Theorem makes my head want to explode.
Best Answer
It's usually easier to solve the congruences successively, i.e. a pair at a time, replacing a pair of congruences by their solution's congruence. So we take the general solution of the first congruence, substitute it into the second, solve that, then substitute that solution into the third, etc, continually replacing the top $\,2\,$ congruences by an equivalent congruence, as summarized below
$\qquad\quad\begin{align} x\equiv 3\!\!\!\pmod{\! 5}\\ x\equiv 1\!\!\!\pmod{\! 4}\\ x\equiv 2\!\!\!\pmod{\! 3}\end{align}\! $ $\iff \begin{align} \\ x\equiv \color{#0a0}{13}\!\!\!\pmod{\!\color{#0a0}{20}}\\ x\equiv \ \ 2 \!\!\!\pmod{\!3} \ \ \end{align}\!\!$ $\begin{align} \\ \\ \iff x\equiv \color{#c00}{53}\!\!\!\pmod{\!60}\end{align}$
Below is the congruence arithmetic justifying the above reductions.
${\rm mod}\ 5\!:\,\ 3\equiv x\iff x = \color{#90f}{3\! +\! 5\:\!j}.\,$ Substituting this value of $\,x\,$ in the 2nd congruence we get
${\rm mod}\ 4\!:\,\ 1\equiv x = \color{#90f}{3\!+\!5\:\!j}\equiv -1\!+\!j\iff j\equiv 2\iff \color{#0a0}{j=2\!+\!4k}$
Thus the first $2$ congruence are equivalent to $\,x = \color{#90f}{3\!+\!5}\:\!\color{#0a0}j \equiv \color{#0a0}{13\!+\!20k}.\,$ Again, substituting this value of $\,x\,$ into the 3rd congruence yields
${\rm mod}\ 3\!:\,\ 2\equiv x = \color{#0a0}{13+20k}\equiv 1\!-\!k\iff k\equiv 2\iff \color{#c00}{k=2\!+\!3n} $
Therefore the $3$ congruences are equivalent to $\,x = \color{#0a0}{13\!+\!20}\:\!\color{#c00}k = \color{#c00}{53+60n}$
Remark $ $ Below is a summary of the reduction of the top two congruences:
$\qquad \begin{align} x\equiv 3\!\!\!\pmod{\! 5}\\ x\equiv 1\!\!\!\pmod {\!4}\end{align}$ $\iff \begin{align} x = \color{#90f}{3\! +\! 5\color{#0a0}j}\\ \color{#0a0}{j=2\!+\!4k}\end{align}$ $\iff x =\color{#90f}{3\!+\!5}(\color{#0a0}{2\!+\!4k})\overbrace{= \color{#0a0}{13+20k}}^{\large\,\ \equiv\ \ \color{#0a0}{13}\!\pmod{\!\color{#0a0}{\!\!20}}\!}$
Note that all reductions are $\iff$ i.e. "if and only if", i.e. equivalences, because we desire to replace two congruences by an equivalent congruence. This means each reduction step must be reversible. In particular, this means that if we encounter a congruence of the form $\,ac\, x\equiv bc\pmod{\!mc}\,$ then any cancelling of $\,c\neq 0\,$ must also be done to the modulus, i.e.
$$ a\color{#c00}c\,x\equiv b\color{#c00}c\!\!\!\pmod{m\color{#c00}c}\iff mc\mid (ax\!-\!b)c \iff m\mid ax\!-\!b\iff ax\equiv b\!\!\!\pmod m$$
i.e. we must cancel $\,\color{#c00}{c\,\ \rm everywhere}\,$ (compare here for a fractional view of this). Such cancellations occur frequently in the general case when the moduli are not pair-coprime.
Notice we ordered the congruences by largest-moduli-first, so that when the numbers are bigger near the end, the moduli are smaller, so modular arithmetic is easier. This optimization pays off much more when larger moduli are present.
See here for a general formula (Easy CRT) for solving a pair of congruences, including the case of noncoprime moduli.