Simultaneusly solving $2x \equiv 11 \pmod{15}$ and $3x \equiv 6 \pmod 8$

Question

Find the smallest positive integer $x$ that solves the following simultaneously.

Note: I haven't been taught the Chinese Remainder Theorem, and have had trouble trying to apply it.

$$ \begin{cases} 2x \equiv 11 \pmod{15}\\ 3x \equiv 6 \pmod{8} \end{cases} $$

I tried solving each congruence individually.

The inverse for the first is 8: $x \equiv 8\cdot11 \equiv 88 \equiv 13 \pmod{15}$.

The inverse for the second is 3: $x \equiv 3\cdot6 \equiv 18 \equiv 2 \pmod{8}$.

But I can't figure out how where to go from here.

Answer 1

Let's proceed completely naively and see where it takes us.

The first congruence is equivalent to $x \equiv 13 \pmod{15}$. This is the same as $x = 13 + 15n$ for any integer $n$. Let's use this in the second congruence. $$\begin{align} 3x &\equiv 6 \pmod 8 \\ 3(13 + 15n) &\equiv 6 \pmod 8 \\ 39 + 45n &\equiv 6 \pmod 8 \\ 7 + 5n &\equiv 6 \pmod 8 \\ 5n &\equiv 7 \pmod 8. \end{align}$$ This lets you determine a solution for $n$. In particular, you'll find that $n \equiv 3 \pmod 8$, or rather $n = 3 + 8l$ for any integer $l$.

Going back, we see that $x = 13 + 15n = 13 + 15(3 + 8l) = 13 + 45 + 120l = 58 + 120l$, or rather that $x \equiv 58 \pmod{120}$. $\diamondsuit$

Answer 2

You must start from Bézout's identity between the moduli $15$ and $8$: $\,2\cdot 8-1\cdot 15=1$. From the solutions to the individual congruences $\color{red} {13} \pmod{15}$ and $\color{red}2 \pmod{8}$, you deduce the solutions to the system: $$2\cdot 8\cdot\color{red} {13}-1\cdot 15\cdot\color{red}2=178\equiv 58\pmod{120}.$$