Use the Chinese Remainder Theorem to solve the following congruences x ≡ 2 MOD 3 x ≡ 3 MOD 4 x ≡ 1 MOD 5

Solution Using the Chinese Remainder Theorem

We are given the following system of congruences: $$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}4)\\ x\equiv 1(\mathrm{mod}5)\end{array}$$

Step 1: Verify that the moduli are pairwise coprime

The moduli are $3$, $4$, and $5$. Since: $$\gcd (3,4)=1,\gcd (3,5)=1,\gcd (4,5)=1,$$ the Chinese Remainder Theorem (CRT) applies.

Step 2: Solve the first two congruences

We first solve: $$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}4)\end{array}$$

Let $x=3k+2$ for some integer $k$. Substitute into the second congruence: $$\begin{gathered} 3k+2\equiv 3(\mathrm{mod}4) \\ 3k\equiv 1(\mathrm{mod}4) \end{gathered}$$

Since $3\equiv -1(\mathrm{mod}4)$, we have: $$\begin{gathered} -k\equiv 1(\mathrm{mod}4) \\ k\equiv -1(\mathrm{mod}4) \\ k\equiv 3(\mathrm{mod}4) \end{gathered}$$

Thus, $k=4m+3$ for some integer $m$. Substituting back: $$x=3(4m+3)+2=12m+9+2=12m+11$$

So, the combined solution for the first two congruences is: $$x\equiv 11(\mathrm{mod}12)$$

Step 3: Incorporate the third congruence

Now, we solve: $$\{\begin{array}{l}x\equiv 11(\mathrm{mod}12)\\ x\equiv 1(\mathrm{mod}5)\end{array}$$

Let $x=12n+11$ for some integer $n$. Substitute into the third congruence: $$\begin{gathered} 12n+11\equiv 1(\mathrm{mod}5) \\ 12n\equiv -10(\mathrm{mod}5) \\ 12n\equiv 0(\mathrm{mod}5)(\text{since }-10\equiv 0(\mathrm{mod}5)) \end{gathered}$$

Since $12\equiv 2(\mathrm{mod}5)$, we have: $$\begin{gathered} 2n\equiv 0(\mathrm{mod}5) \\ n\equiv 0(\mathrm{mod}5)(\text{because }\gcd (2,5)=1) \end{gathered}$$

Thus, $n=5p$ for some integer $p$. Substituting back: $$x=12(5p)+11=60p+11$$

The general solution is: $$x\equiv 11(\mathrm{mod}60)$$

Final Answer

The smallest positive solution is: $x=11$ (mod 60). The complete solution set is all integers of the form $x=60k+11$, where $k$ is any integer.