Solving a linear system of congruences

Question

Solve the following linear system of congruences \begin{cases} 18x \equiv 15 &\pmod{21}\\ 6x \equiv 7 &\pmod{11}\\ 3x \equiv 6 &\pmod{8} \end{cases}

My work: first step i simplify first equation dividing by 3.

\begin{cases} 6x \equiv 5 \pmod 7 \\ 6x \equiv 7 \pmod{11} \\ 3x \equiv 6 \pmod 8 \end{cases}

now, for convenience, the teacher advised us to get coefficient 1 to the first member then I multiply first equation by 6, second equation by 2 and third equation by $3$ :

\begin{cases} 36x \equiv 30 \pmod 7 \\ 12x \equiv 14 \pmod{11} \\ 9x \equiv 18 \pmod 8 \end{cases}

now doing mod :

\begin{cases} x \equiv 2 \pmod 7 \\ x \equiv 3 \pmod{11} \\ x \equiv 2 \pmod 8 \end{cases}

the solution of first equation is:

$$ 2+7*k $$

use this for resolve second equation :

$$ 2+7*k \equiv 3 \pmod{11} $$

$$7*k \equiv 1 \pmod{11}) $$

Now , I don't know if it's correct,but for resolve this equation I multiply by $8 so that $ 7*8=56; $ $56 \bmod 11 = 1$

so I get :

$ 56k \equiv 8 \pmod{11} $ after mod : $ k \equiv 8 \pmod{11} $

$ k = 8 $

Now we found the "x" of first solution :

$ 2+7 * k$ now $k = 8 $

$ 2+7*8 = 58 ; $

I multiply the first and second mod equations : $ 7*11 = 77 $

we have that $ 58+77*t $

or in other words : class of $58 \mod 77 $

Now repeat the same procedure for third equation :

$ 58+77*t \equiv 2 \pmod 8 $

$ 77*t \equiv -56 \pmod 8$

$ 5t \equiv 0 \pmod 8 $

$ t \equiv 0 \pmod 8$

Now, this zero has put bit of confusion in my head :

what is the result ?

in theory we have $$ 58 +77 * 0$$ Is correct ??

then

the product of the modules is $ 7*11*8 = 616 $

the result is $ 58 + 616 * h $ or class 58 mod 616

everything is correct ? I have a little doubt, sorry

Answer 1

Your result is right, but your method is far too complex.

The solutions of systems of congruences relies on Bézout's identity and the explicit formula for the inverse isomorphism in the Chinese remainder theorem, namely

Suppose the moduli $m$ and $n$ are coprime, and let $um+vn=1$ a Bézout's relation. Then the system $$\begin{cases}x\equiv\alpha\pmod m\\x\equiv\beta\mod n\end{cases}\enspace \text{ has for solution(s) }\enspace x\equiv\beta\, um+\alpha\, vn\pmod {mn}.$$

Now, you can begin solving congruences $(1)$ and $(3)$: since $8-7=1$, $$\begin{cases}x\equiv 2\pmod 7\\x\equiv 2\mod 8\end{cases}\iff x\equiv 2\pmod{56}.$$ So we now have to solve a system of two congruences modulo $56$ and modulo $11$. As $56-5\times 11=1$, we have $$\begin{cases}x\equiv 3\pmod{11}\\x\equiv 2\pmod{56}\end{cases}\iff x\equiv 3\times56-2\times 5\times 11= 58 \pmod{616}.$$