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{1}\mathbf{(}\mathbf{mod}\mathbf{2}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{\equiv }\mathbf{2}\mathbf{(}\mathbf{mod}\mathbf{3}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{5}\mathbf{)}\mathbf{,}\mathbf{}\mathbf{and}\mathbf{}\mathit{x}\mathbf{\equiv }\mathbf{4}\mathbf{(}\mathbf{mod}\mathbf{11}\mathbf{)}$

Short answer

The solution is $x\equiv 323\left(\mathrm{mod}330\right)$.

Step-by-step solution

Chinese Remainder theorem

According to Chinese reminder 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=2,m_2=3,m_3=5,m_4=11$and $a_1=1,a_2=2,a_3=3,a_4=11$

So,

$$\begin{gathered} M=m_1\cdot m_2\cdot m_3\cdot m_4 \\ =2\cdot 3\cdot 5\cdot 11 \\ =330 \end{gathered}$$

Now,

$$\begin{gathered} M_1=\frac{M}{m_1} \\ =\frac{330}{2} \\ =165 \\ {M}_2=\frac{M}{m_2} \\ =\frac{330}{3} \\ =110 \\ {M}_3=\frac{M}{m_3} \\ =\frac{330}{5} \\ =66 \\ {M}_4=\frac{M}{m_4} \\ =\frac{330}{11} \\ =30 \end{gathered}$$

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

For$M_1=165\left(\mathrm{mod}2\right)=1\left(\mathrm{mod}2\right)$

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

For$M_2=110(mod3)=2(mod3)$

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

For$M_3=66(mod5)=1(mod5)$

Inverse of$M_3^{-1}$ is 1 because$1\cdot 1(mod5)=1(mod5)=1$

For$M_4=30(mod11)=8(mod11)$

Inverse of$M_4^{-1}$ is 7 because$7\cdot 8(mod11)=56(mod11)=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}+a_4{M}_4{M}_4^{-1}\right)(modM) \\ x\equiv (1\cdot 165\cdot 1+2\cdot 110\cdot 2+3\cdot 66\cdot 1+4\cdot 30\cdot 7)(mod330) \\ x\equiv 1643(mod330) \\ x\equiv 323(mod330) \end{gathered}$$

Hence, solution is $x\equiv 323(mod330)$.