Question

Use the construction in the proof of the Chinese Remainder Theorem to find the solution of the system of congruences$\mathit{x}\mathbf{\equiv }\mathbf{2}\mathbf{(}\mathbf{mod}\mathbf{3}\mathbf{)}\mathbf{,}\mathbf{x}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{4}\mathbf{)}\mathbf{,}\mathbf{}\mathbf{and}\mathbf{}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{5}\mathbf{)}$

Short answer

The solution is $x\equiv 53(mod60)$.

Step-by-step solution

Chinese Remainder theorem

According to Chinese remainder theorem, let $\mathbf{}{\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{m}}_{\mathit{r}}$be relatively prime numbers such that $\mathbf{(}{\mathbf{m}}_{\mathbf{i}}\mathbf{,}{\mathbf{m}}_{\mathbf{j}}\mathbf{)}\mathbf{=}\mathbf{1}$where $\mathit{i}\mathbf{\ne }\mathit{j}$then the linear congruences$\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{1}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{1}}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{2}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{2}}\mathbf{)}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathit{r}}\mathbf{(}\mathbf{mod}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$ has a simultaneous solution which is unique modulo$\mathbf{(}{\mathbf{m}}_{\mathbf{1}}\mathbf{,}{\mathbf{m}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$

Find the solution of the system of the given congruence

Here we have,

$m_1=3,m_2=4,m_3=5\mathrm{and}{a}_1=2,a_2=1,a_3=3$

So,

role="math" localid="1668682626748" $$\begin{gathered} M=m_1\cdot m_2\cdot m_3 \\ =3\cdot 4\cdot 5 \\ =60 \end{gathered}$$

Now,

$$\begin{gathered} M_1=\frac{M}{m_1} \\ =\frac{60}{3} \\ =20 \\ {M}_2=\frac{M}{m_2} \\ =\frac{60}{4} \\ =15 \\ {M}_3=\frac{M}{m_3} \\ =\frac{60}{5} \\ =12 \end{gathered}$$

Now, to find inverse of$M_1\text{'}s$

For$M_1=20(mod3)=2(mod3)$

Inverse of$M_1^{-1}$ is 2 because$2\cdot 2(mod3)=4(mod3)=1$

For$M_2=15(mod4)=3(mod4)$

Inverse of$M_2^{-1}$ is 3 because$3\cdot 3(mod4)=9(mod4)=1$

For$M_3=12(mod5)=2(mod5)$

Inverse of$M_3^{-1}$ is 3 because$3\cdot 2(mod5)=6\left(mod{5}^2\right)=1$

Now, solution is given by,

$$\begin{gathered} x\equiv \left(a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}+a_3{M}_3{M}_3^{-1}\right)(modM) \\ x\equiv (2\cdot 20\cdot 2+1\cdot 15\cdot 3+3\cdot 12\cdot 3)(mod60) \\ x\equiv 233\left({mod}_{6}60\right) \\ x\equiv 53(mod60) \end{gathered}$$

Hence, solution is $x\equiv 53(mod60)$.