Question

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

Short answer

The solution is $x\equiv 323(mod330)$.

Step-by-step solution

Theorem 4(section 4.1)

According to theorem 4,let mbe a positive integer. The integers a and b such that$\mathbf{a}\mathbf{\equiv }\mathbf{b}\left(\mathrm{mod}m\right)$ if and only if there is an integer p such that $\mathbf{a}\mathbf{=}\mathbf{b}\mathbf{+}\mathbf{mp}$.

Finding the solution of the given system using back substitution

In exercise 20 we have given that,

$x\equiv 1(mod2);x\equiv 2(mod3),x\equiv 3(mod5),andx\equiv 4(mod11)$

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

Also we have, $x\equiv 2(mod3)$

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

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

Now, we know that $k\equiv 2\cdot 2=4=1(mod3)$

So,

$k\equiv 2(mod3)$

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

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

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

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

For some integer l .

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

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

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

Now, we know that $I\equiv 6\cdot 1=6=1(mod5)$

So,

role="math" localid="1668678995977" $$\begin{gathered} I\equiv \left(6{)}^{-1}3\right(mod5) \\ I\equiv 3(mod5) \end{gathered}$$

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

Also, we have $x=5+6l$.

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

$$\begin{gathered} x=5+6(3+5m) \\ x=23+30\mathrm{m} \end{gathered}$$

For some integer $m$.

Now, also we have, $x\equiv 4(mod11)$

Now, substitute the value of $x=23+30m\mathrm{in}x\equiv 4(mod11)$. We get,

$$\begin{gathered} 23+30m\equiv 4(mod11) \\ 30m\equiv -19(mod11) \\ 30m\equiv 3(mod11) \\ m\equiv \left(30{)}^{-1}3\right(mod11) \end{gathered}$$

Now, we know that $m\equiv 30\cdot \left(\frac{10}{3}\right)=100=1(mod11)$

So,

$$\begin{gathered} m\equiv \left(30{)}^{-1}3\right(mod11) \\ m\equiv \left(\frac{10}{3}\right)3(mod11) \\ m\equiv 10(mod11) \end{gathered}$$

Now, again from theorem 4 we can say that there is integer such that $m=10+11n$

Also, we have $x=23+30m$.

Now, substitute the value of $m=10+11n\mathrm{in}x=23+30m$. We get,

$$\begin{gathered} x=23+30(10+11n) \\ x=323+330n \end{gathered}$$

For some integer n .

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

Hence, the solution is $x\equiv 323(mod330)$.