Find All Solutions to System of Congruence $$
\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.
 A: 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 (e.g. 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.
A: I think you're a bit confused about the recipe used to solve the system of congruences using the Chinese Remainder Theorem.  Using your notation, the actual solution is given by
\begin{align*}
x = 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) + 1 \cdot m_2 \cdot ({m_2}^{-1} \text{ mod } 4) + 3 \cdot m_3 \cdot ({m_3}^{-1} \text{ mod } 5) \, .
\end{align*}
Let's see why this answer works.  Since $m_1$ is divisible by both $4$ and $5$, the first term is "invisible" when we consider $x$ mod $4$ and mod $5$: it is congruent to $0$ mod $4$ and mod $5$, so it doesn't contribute to the answer of the last two congruences.  Thus, we can focus on making this first term satisfy the first congruence.  Okay, so far we know the first term should have as factors $2$ (the congruence we want) and $m_1$ (to get rid of the effect mod $4$ and $5$).  But now we don't satisfy the first congruence; the $m_1$ throws things off.  To fix this, we multiply by the ${m_1}^{-1}$ mod $3$.  Then mod $3$ we have
\begin{align*}
x &= 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) + 1 \cdot m_2 \cdot ({m_2}^{-1} \text{ mod } 4) + 3 \cdot m_3 \cdot ({m_3}^{-1} \text{ mod } 5)\\
&\equiv 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) \equiv 2 \pmod{3}
\end{align*}
as desired.  Similar reasoning shows that $x$ satisfies the given congruences mod $4$ and $5$.
You have the right idea with your solution, but you're missing some factors.  Since you've shown $1 = 20 \cdot (-1)  + 3 \cdot 7 \equiv 20 \cdot (-1) \pmod{3}$, then
$$
{m_1}^{-1} \text{ mod } 3 = 20^{-1} \text{ mod } 3 = -1 \equiv 2 \pmod{3} \, .
$$
So the first term should be $2 \cdot 20 \cdot 2$.  Can you figure out the other two terms now?
