Question

(a) State the Chinese Remainder Theorem

(b) Find the solutions to the system Find the solutions to the system $\mathbf{x}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{4}\mathbf{}\mathbf{)}\mathbf{x}\mathbf{\equiv }\mathbf{2}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{5}\mathbf{)}$and$\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{7}\mathbf{}\mathbf{)}$

Short answer

(a) let ${\mathrm{m}}_1,{\mathrm{m}}_2,...,{\mathrm{m}}_{\mathrm{r}}$be relatively prime numbers such that $(m_i,m_j)=1$ where $i\ne j$then the linear congruences $x\equiv a_1(mod{m}_1)$, $x\equiv a_2(mod{m}_2)$ , …, $x\equiv a_r(mod{m}_r)$has a simultaneous solution which is unique modulo $(m_1,m_2,...,m_r)$.

(b) The solution is $\mathrm{x}\equiv 17(\mathrm{mod}140)$.

Step-by-step solution

Chinese Remainder theorem

(a)

Which says that, let ${\mathrm{m}}_1,{\mathrm{m}}_2,...,{\mathrm{m}}_{\mathrm{r}}$be relatively prime numbers such that where then the linear congruences role="math" localid="1668503455119" $\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{1}}\mathbf{(}\mathbf{mod}\mathbf{}{\mathbf{m}}_{\mathbf{1}}\mathbf{)}$, $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{2}}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}{\mathit{m}}_{\mathbf{2}}\mathbf{)}$, …, $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{r}}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}{\mathit{m}}_{\mathbf{r}}\mathbf{)}$ has a simultaneous solution which is unique modulo$\mathbf{(}{\mathbf{m}}_{\mathbf{1}}\mathbf{,}{\mathbf{m}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$

Find the solution of the system of the given congruence

(b)

Here we have,

$m_1=4,m_2=5,m_3=7$ and$a_1=1,a_2=2,a_3=3$

So,

$$\begin{gathered} M=m_1\cdot m_2\cdot m_3 \\ =4\cdot 5\cdot 7 \\ =140 \end{gathered}$$

Now,

$$\begin{gathered} M_1=\frac{M}{m_1} \\ =\frac{140}{4} \\ =35 \end{gathered}$$

$$\begin{gathered} M_2=\frac{M}{m_2} \\ =\frac{140}{5} \\ =28 \\ {M}_3=\frac{M}{m_3} \\ =\frac{140}{7} \\ =20 \end{gathered}$$

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

For$M_1=35\left(mod4\right)=3\left(mod4\right)$

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

For $M_2=28\left(mod5\right)=3\left(mod5\right)$

Inverse of ${M_2}^{-1}$is 7 because$7\cdot 3(mod5)=21(mod5)=1$

For $M_3=20\left(mod7\right)=6\left(mod7\right)$

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

Now, solution is given by,

$$\begin{gathered} x\equiv (a_1{M}_1{M_1}^{-1}+a_2{M}_2{M_2}^{-1}+a_3{M}_3{M_3}^{-1})(modM) \\ x\equiv (1\cdot 35\cdot 3+2\cdot 28\cdot 7+3\cdot 20\cdot 6)(mod140) \\ x\equiv 857(mod140) \\ x\equiv 17(mod140) \end{gathered}$$

Hence, solution is $x\equiv 17(mod140)$.