discrete mathematics - 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.

Answer

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?