Question

Find all solutions of the system of congruences $\mathit{x}\mathbf{\equiv }\mathbf{4}\mathbf{\left(}\mathit{m}\mathit{o}\mathit{d}\mathbf{6}\mathbf{\right)}$and$\mathit{x}\mathbf{\equiv }\mathbf{13}\mathbf{\left(}\mathit{m}\mathit{o}\mathit{d}\mathbf{15}\mathbf{\right)}$.

Short answer

The solutions of the system of congruences$x\equiv 4(mod6)andx\equiv 13(mod15)isx\equiv 28mod30$.

Step-by-step solution

Chinese remainder theorem

A system of linear congruences modulo pairwise relatively prime integers have a unique solution modulo is the product of these moduli.

Let ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{m}}_{\mathbf{n}}$be pairwise relatively prime positive integers greater than one and${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{a}}_{\mathbf{n}}$arbitrary integers. Then the system

$\begin{array}{r}\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{1}}\left(mod{m}_1\right)\\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{2}}\left(mod{m}_2\right)\\ \\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{n}}\left(mod{m}_n\right)\end{array}$

has a unique solution modulo $\mathit{m}\mathbf{=}{\mathit{m}}_{\mathbf{1}}{\mathit{m}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{m}}_{\mathbf{n}}$. (That is, there is a solution xwith $\mathbf{0}\mathbf{\le }\mathit{x}\mathbf{<}\mathit{m}$, and all other solutions are congruent modulo mto this solution.)

Finding the solutions

It is given that

$\begin{array}{r}x\equiv 4(mod6)\\ x\equiv 13(mod15)\end{array}$

As we can see both 6 and 15 are multiples of 3

$x\equiv 4(mod6):x\equiv 4\equiv 1(mod3)\text{and}x\equiv 4\equiv 0(mod2)$

and

$x\equiv 13(mod15):x\equiv 13\equiv 1(mod3)\text{and}x\equiv 13\equiv 3(mod5)$

Therefore, equivalent equations are

$\begin{array}{r}x\equiv 0(mod2)\\ x\equiv 1(mod3)\\ x\equiv 3(mod5)\end{array}$

Therefore, from the Chinese remainder theorem we have

$\begin{array}{r}{a}_1=0,a_2=1,a_3=3\\ m_1=2,m_2=3,m_3=5\end{array}$

So,

$\begin{array}{r}m=m_1{m}_2{m}_3\\ =2\times 3\times 5\\ =30\end{array}$

Therefore,

$\begin{array}{r}{M}_1=\frac{m}{m_1}\\ =\frac{30}{2}\\ =15\\ M_2=\frac{m}{m_2}\\ =\frac{30}{3}\\ =10\\ M_3=\frac{m}{m_3}\\ =\frac{30}{5}\\ =6\end{array}$

$y_i$is inverse of $M_i$modulo $m_i$

$\begin{array}{r}{y}_1={15}^{-1}mod2=1\text{as}1.15mod2=15mod2=1\\ y_2={10}^{-1}mod3=1\text{as}1.10mod3=10mod3=1\\ y_3=6^{-1}mod5=1\text{as}1.6mod5=6mod5=1\end{array}$

The solution of the system is

$\begin{array}{r}x\equiv \left(a_1{M}_1{y}_1+a_2{M}_2{y}_2+a_3{M}_3{y}_3\right)modm\\ \equiv (\mathrm{0.15.1}+\mathrm{1.10.1}+\mathrm{3.6.1})mod30\\ \equiv 28mod30\end{array}$

Hence the solutions of the system of congruences $x\equiv 4(mod6)\text{and}x\equiv 13(mod15)isx\equiv 28mod30$