# Solving simultaneous congruences with the Chinese remainder theorem

Solve the following system of congruences using the Chinese remainder theorem: \begin{align*} 2x &\equiv 3 \pmod{7} \\ x &\equiv 4 \pmod{6} \\ 5x &\equiv 50 \pmod{55} \end{align*} I was a little confused how to reduce the congruences into a form where the Chinese remainder theorem is applicable.

1. The first congruence takes the form $$2x \equiv 3 \pmod 7$$ so we want to find the multiplicative inverse of $2$, modulo $7$. You can use Euclid's algorithm for computing GCDs, or just think about it, and see that $4$ is the multiplicative inverse of $2$, as $$2 \times 4 \equiv 1 \pmod{7}$$ So now we multiply the congruence through by $4$, and we get $$x \equiv 3 \times 4 \equiv 5 \pmod 7$$ which is the form we want for the CRT.

2. This congruence is already in the form we want.

3. The third congruence is $$5x \equiv 50 \pmod {55}$$ Since the coefficient of $x$, the remainder and the modulus all have common factor $5$, we can divide through by this to get the congruence $$x \equiv 10 \pmod {11}$$ So now this congruence is in a suitable form to apply CRT.

(For proof that this works, observe that $$55 \mid (5x - 50) \iff 5 \times 11 \mid 5\,(x - 10) \iff 11 \mid x - 10.)$$

Now you have the three congruences \begin{align*} x &\equiv 5 \pmod 7 \\ x &\equiv 4 \pmod 6 \\ x &\equiv 10 \pmod {11} \end{align*} the standard form, which I assume you already know how to solve.

• isn't the first congruence x≡5 (mod 7) since 12-7=5?
– Lil
May 2 '14 at 20:56
• @Lil: Yes, my mistake copy/pasting from top to bottom. Fixed. May 2 '14 at 20:57
• np, one more question. what is the solution to the congruence 4x≡1(mod6)?
– Lil
May 2 '14 at 21:01
• @Lil: No solution exists. Observe that $4x \equiv 1 \pmod 6$ is equivalent to $6 \mid (4x - 1)$, but $(4x - 1)$ is odd for any choice of $x$, so we cannot have $6 \mid (4x - 1)$ (as $6$ is even). May 2 '14 at 21:03
• so how do you go about solving this using the chinese remainder theorem? Should I just solve the other 2 congruences and then substitute the number back in for x?
– Lil
May 2 '14 at 21:03

The congruence $2x\equiv 3\pmod{7}$ holds if and only if $x\equiv 5\pmod{7}$. And $5x\equiv 50\pmod{55}$ if and only if $x\equiv 10\pmod{11}$. Now the problem is in "standard" form.

Remark: To get the first result, we can multiply both sides of $2x\equiv 3\pmod{7}$ by the inverse of $2$ modulo $7$. Note that $4$ is the inverse to $2$. Or more simply we replace the $3$ by $10$, and divide by $2$.

The second result comes from the general fact that if $k\ne 0$, then $ka\equiv kb\pmod{km}$ if and only if $a\equiv b\pmod{m}$.

• so for the congruence: 5x≡50(mod55) you just divided everything by 5 to simplify correct? How did you simplify 2x≡3(mod7)
– Lil
May 2 '14 at 20:48
• I added a bit in a remark. May 2 '14 at 20:50
• got it. Thank you so much!
– Lil
May 2 '14 at 20:51
• what is the solution to the congruence 4x≡1(mod6) I can't think of any number smaller than 6 for x that makes the statement true.
– Lil
May 2 '14 at 20:52
• You are welcome. The answer just posted by alexwichan has thorough explanations. May 2 '14 at 20:53

Solving x = 5(mod 7) and x = 4(mod 6) simultaneously, you get x = 40(mod 42).

Solving this result and x = 10(mod 11) simultaneously, you get x = 208(mod 462)

$$2x≡3(mod 7)=> 2x≡3+7(mod 7)$$

$$x≡4(mod 6)$$

$$5x≡50(mod 55) => x≡10(mod 11)$$

3 linear congruence formed now apply CRT

$$m=7*6*11=462$$

$$M_1=66,M_2=77,M_3=42$$

$$66x≡1(mod 7) ; b_1=5$$

$$77x≡1(mod 6) ; b_2=-1$$ $$42x≡1(mod 11) ; b_3=5$$

$$x≡5*5*66+77*(-1)*(4)+42*5*10(mod 462)$$

$$x≡3442 (mod 462)$$

$$x≡208(mod 462)$$

$$x=(462)t+208; t={0,1,2,3...}$$

• Please use MathJax. Aug 31 '17 at 15:54
• Thanks for the link, will study and implement it. Aug 31 '17 at 17:08