Solve linear congruences

congruence-relationsdiscrete mathematicsmodular arithmetic

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

Best Answer

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.