Question

Find all solutions, if any, to the system of congruences $\mathbf{x}\mathbf{\equiv }\mathbf{7}\left(\mathrm{mod}9\right)\mathbf{,}\mathbf{}\mathbf{x}\mathbf{\equiv }\mathbf{4}\left(\mathrm{mod}12\right)$, and$\mathbf{x}\mathbf{\equiv }\mathbf{16}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{21}\mathbf{)}$

Short answer

The solution is given by, $x=16+252k$ where$k$ is an integer

Step-by-step solution

Chinese Remainder theorem

According to Chinese remainder theorem,let ${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{m}}_{\mathbf{r}}$be relatively prime numbers such that role="math" localid="1668598549667" $\mathbf{(}{\mathbf{m}}_{\mathbf{i}}\mathbf{}\mathbf{,}{\mathbf{m}}_{\mathbf{j}}\mathbf{)}\mathbf{=}\mathbf{1}$where $\mathit{i}\mathbf{\ne }\mathit{j}$then the linear congruences role="math" localid="1668598554573" $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{1}}\mathbf{(}\mathbf{mod}\mathbf{}{\mathbf{m}}_{\mathbf{1}}\mathbf{)}$, $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{2}}\mathbf{(}\mathbf{mod}\mathbf{}{\mathbf{m}}_{\mathbf{2}}\mathbf{)}$,....., $\mathit{x}\mathbf{\equiv }{\mathit{a}}_{\mathbf{r}}\mathbf{(}\mathbf{mod}\mathbf{}{\mathbf{m}}_{\mathbf{r}}\mathbf{)}$has a simultaneous solution which is unique modulo $\left(m_1,m_2,....,m_r\right)$

Check that Chinese Reminder theorem is applicable or not

Here we have given that,

$\mathrm{x}\equiv 7\left(\mathrm{mod}9\right),\mathrm{x}\equiv 4\left(\mathrm{mod}12\right),\mathrm{and}\mathrm{x}\equiv 16\left(\mathrm{mod}21\right)$

In above system we can see that, 9,12,21 are not relatively prime.

So, we cannot apply Chinese reminder theorem.

Step 3: Finding the solution of the given system

Here we have given that,

$\mathrm{x}\equiv 7\left(\mathrm{mod}9\right),\mathrm{x}\equiv 4\left(\mathrm{mod}12\right),\mathrm{and}\mathrm{x}\equiv 16\left(\mathrm{mod}21\right)$

By, the given system we can see that 16 is a solution to the system of given congruences and it is the smallest positive integer solution.

Now, we need to find the Least Common Multiple of 9,12,21.

So,

$$\begin{gathered} Icm\left(9,12,21\right)=3^2·2^2·7 \\ =252 \end{gathered}$$

So, the solution is given by, $x=16+252k$where$k$ is an integer.