0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user
    Dec 16, 2018 at 11:34

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .