Solving a congruence with Chinese Remainder Theorem

chinese remainder theoremeuclidean-algorithmmodular arithmetic

I need help solving a congruence with the help of Chinese Remainder Theorem. I am not sure how I could get 3 congruences out of one. For solving congruences I use Euclid's algorithm. Here's an example:
\begin{align*}
19x &\equiv 7 \mod 374 \\
\end{align*}

Any tips would be massively appreciated. Thank you!

Best Answer

The Chinese Remainder Theorem approach actually leads you to do more work than directly applying Euclid's algorithm in this simple case, because you now need to solve 3 congruence and apply Euclid/Bezout twice (on the moduli $2,11,17$, although you can avoid doing the 2 by inspection instead of via Bezout) to match them up.

  • If you can just apply Euclid directly: \begin{align*} 374-19\times 19&=13\\ 19-13&=6\\ 13-2\times 6&=1 \end{align*} and so running it backwards gives $3\times 374-59\times 19 = 1$. Hence multiplying your given equation by $-59$ gives $x\equiv -59\times 7\pmod{374}$.

  • On the other hand, by Chinese Remainder Theorem, you need to solve $$ \left\{ \begin{aligned} 19 x&\equiv 7\pmod{2}\\ 19 x&\equiv 7\pmod{11}\\ 19 x&\equiv 7\pmod{17}\\ \end{aligned} \right. $$ giving (steps omitted here) $$ \begin{aligned} x&\equiv 1\pmod 2\\ x&\equiv 5\pmod{11}\\ x&\equiv 12\pmod{17} \end{aligned} $$ and now you need to apply Euclid to $11,17$ and run backwards, giving $$ 2\times 17-3\times 11=1 $$ so $x\equiv 5\times (2\times 17)+12\times(-3\times 11)\pmod{187}$ and $x\equiv 1\pmod 2$, so $$ x\equiv 5\times 2\times 17+12\times(-3)\times 11+187\pmod{374}. $$

Related Question