Solve linear congruences

Solve linear congruences system

• $$11x \equiv 10 \mod 12$$
• $$14x \equiv 10 \mod 15$$
• $$20x \equiv 10 \mod 21$$

We need to find x that is closest to 1200. The correct solution is 1250.

This is the way I have done it: First I converted all equations to their correct shape:

• $$x \equiv 2 \mod 12$$
• $$x \equiv 5 \mod 15$$
• $$x \equiv 11 \mod 21$$

Then I do $$x = 2 + 12*k$$, which I put into the second equation and I get $$k = 4 mod 15$$. I put that back into first one and I get $$x = 5 + 18*h$$. I put that into the third one and I get $$h = 6 + 7*m$$. But how am I supposed to solve this. I also know the solution needs to be in modulo $$420$$, because $$lcm(12,15,21)=420$$.

• To be sure that the system has solution (12,15,21) should be coprimes. To apply CRT we need to write at first the equivalent system for the factors $12=3\cdot 4$, $15=3\cdot 5$ and $21=3\cdot 7$ and check that it is consistent.
– user
Dec 16, 2018 at 11:34

You can plug $$x=12a+2$$ into the second and third equations: $$\begin{cases}12a+2\equiv 5 \pmod{15} \\ 12a+2\equiv 11 \pmod{21}\end{cases} \Rightarrow \begin{cases}a\equiv 4 \pmod{5} \\ a\equiv 6 \pmod{7}\end{cases}$$ Now plug $$a=5b+4$$ into the last equation: $$5b+4\equiv 6 \pmod{7} \Rightarrow b\equiv 6 \pmod{7} \Rightarrow b=7c+6$$ Now go back: $$a=5b+4=5(7c+6)+4=35c+34;\\ x=12a+2=12(35c+34)+34=420c+410 \Rightarrow \\ x\equiv 410 \pmod{420}.$$ Verifying $$x=410$$: $$11\cdot 410\equiv 4510 \equiv 375\cdot 12+10\equiv 10 \pmod{12};\\ 14\cdot 410\equiv 5740 \equiv 382\cdot 15+10\equiv 10 \pmod{15};\\ 20\cdot 410\equiv 8200 \equiv 390\cdot 21+10\equiv 10 \pmod{21}.$$ You can check $$x=420\cdot 2+410=1250$$ youserlf.
Hint $$\ {-}x\equiv 10\pmod {\!a,b,c}\iff a,b,c\mid x\!+\!10\iff{\rm lcm}(a,b,c)\mid x\!+\!10$$
$${\rm lcm}(12,15,21) = 3\, {\rm lcm}(4,5,7) = 3\cdot 4\cdot 5\cdot 7 = 20\cdot 21 = 420,\,$$ hence $$\,x\equiv -10\pmod{\!420}$$