Question

Solve the system of congruenceExercise 20 using the method of back substitution.

Short answer

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

Step-by-step solution

Theorem 4(section 4.1)

According to theorem 4,et xbe a positive integer. The integers s and t such that $\mathit{s}\mathbf{\equiv }\mathit{t}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{x}\mathbf{)}$ if and only if there is an integer such that $\mathit{s}\mathbf{=}\mathit{t}\mathbf{+}\mathit{p}\mathit{x}$.

Finding the solution of the given system using back substitution

In exercise 20 we have given that,

$x\equiv 2(mod3),x\equiv 1(mod4),\mathrm{and}x\equiv 3(mod5)$

Now, for $x\equiv 2(mod3)$ from theorem 4 we can say that there is integer k such that $x=2+3k$

Also we have, $x\equiv 1(mod4)$,

Now, substitute the value of $x=2+3k\mathrm{in}x\equiv 1(mod4)$. We get,

$$\begin{gathered} 2+3k\equiv 1(mod4) \\ 3k\equiv -1(mod4) \\ k\equiv (3{)}^{-1}\cdot 3(mod4) \end{gathered}$$

Now, we know that $k\equiv 3\cdot 3=9=1(mod4)$

So,

$$\begin{gathered} k\equiv \left(3{)}^{-1}3\right(mod4) \\ k\equiv 9(mod4) \\ k\equiv 1(mod4) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer l such that $k=1+4l$

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

Now, substitute the value of $k=1+4l\mathrm{in}x=2+3k$. We get,

$$\begin{gathered} x=2+3(1+4l) \\ x=5+12l \end{gathered}$$

For some integer l.

Now, also we have, $x\equiv 3(mod5)$

Now, substitute the value of $x=5+12l\mathrm{in}x\equiv 3(mod5)$. We get,

$$\begin{gathered} 5+12I\equiv 3(mod5) \\ 12l\equiv -2(mod5) \\ 12l\equiv 3(mod5) \\ I\equiv \left(12{)}^{-1}3\right(mod5) \end{gathered}$$

Now, we know that $I\equiv 3\cdot 12=36=1(mod5)$

So,

$$\begin{gathered} I\equiv \left(12{)}^{-1}3\right(mod5) \\ I\equiv 9(mod5) \\ l\equiv 4(mod5) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer such that $I=4+5m$

Also, we have $x=5+12I$.

Now, substitute the value of$I=4+5m\mathrm{in}x=5+12l$ . We get,

$$\begin{gathered} x=5+12(4+5m) \\ x=53+60m \end{gathered}$$

For some integer m .

Now, again by theorem 4 we can write $x\equiv 53(mod60)$.

Hence, the solution is $x\equiv 53(mod60)$.