Question

Solve the system of congruence$\mathbf{x}\mathbf{\equiv }\mathbf{3}\left(\mathrm{mod}6\right)$and $\mathbf{x}\mathbf{\equiv }\mathbf{4}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{7}\mathbf{)}$using the method of back substitution.

Short answer

The solution is$\mathrm{x}\equiv 39(\mathrm{mod}42)$

Step-by-step solution

Theorem 4(section 4.1)

According to theorem 4,letp be a positive integer. The integers s are t congruent modulo p if and only if there is an integer k such that $\mathit{s}\mathbf{=}\mathit{t}\mathbf{+}\mathit{k}\mathit{p}$.

Finding the solution of the given system using back substitution

Here we have given that, $\mathrm{x}\equiv 3(\mathrm{mod}6)$

From theorem 4 we can say that there is integer k such that $x=3+6k$

Also we have, $\mathrm{x}\equiv 4(\mathrm{mod}7)$,

Now, substitute the value of $x=3+6k$ in $\mathrm{x}\equiv 4(\mathrm{mod}7)$. We get,

$$\begin{gathered} 3+6k\equiv 4(mod7) \\ 6k\equiv 1(mod7) \\ k\equiv \left(6{)}^{-1}1\right(mod7) \end{gathered}$$

Now, we know that $k\equiv 6\cdot 6=36=1(mod7)$

So,

$$\begin{gathered} k\equiv \left(6{)}^{-1}1\right(mod7) \\ k\equiv 6(mod7) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer m such that $k=6+7m$

Also, we have $x=3+6k$.

Now, substitute the value of $k=6+7m$ in $x=3+6k$. We get,

$$\begin{gathered} \mathrm{x}=3+6(6+7m) \\ x=39+42m \end{gathered}$$

For some integer m.

Now, again by theorem 4 we can write $\mathrm{x}\equiv 39(\mathrm{mod}42)$.

Hence, the solution is $\mathrm{x}\equiv 39(\mathrm{mod}42)$.