6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ @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? $\endgroup$
    – Bob
    Mar 28 '15 at 1:25
  • $\begingroup$ I do not currently see what I did wrong. But it will become clear, I would assume, momentarily $\endgroup$
    – davidlowryduda
    Mar 28 '15 at 1:39
  • $\begingroup$ @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. $\endgroup$
    – davidlowryduda
    Mar 28 '15 at 1:42
  • $\begingroup$ You should probably fix that $88+120l$, or someone could get confused :P $\endgroup$
    – Bob
    Mar 28 '15 at 2:14
  • $\begingroup$ Clever solution! I like how it only uses the definition of modulus. $\endgroup$ Mar 28 '15 at 2:40
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.