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

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.

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$

• @mixedmath: The smallest positive integer given your response would be 88, but trying: $3\cdot88 \equiv 6 \pmod{8}$ doesn't seem to work out. Am I doing something wrong?
– Bob
Mar 28 '15 at 1:25
• I do not currently see what I did wrong. But it will become clear, I would assume, momentarily Mar 28 '15 at 1:39
• @Bob Did you know that $8\cdot 5 = 40 \neq 42$? I know, it's news to me too. I've corrected my arithmetic mistake, and it is now correct. Mar 28 '15 at 1:42
• You should probably fix that $88+120l$, or someone could get confused :P
– Bob
Mar 28 '15 at 2:14
• Clever solution! I like how it only uses the definition of modulus. Mar 28 '15 at 2:40

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}.$$