Solving a congruence with Chinese Remainder Theorem

Question

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!

Answer 1

Since $374=2\times11\times17$, all you have to do is to apply the Chinese Remainder Theorem to the system$$\left\{\begin{array}{l}19x\equiv7\mod2(\iff x\equiv1\mod2)\\19x\equiv7\mod11(\iff8x\equiv7\mod11)\\19x\equiv7\mod17(\iff2x\equiv7\mod17).\end{array}\right.$$

Answer 2

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

Answer 3

It's much easier to use $2$ (vs. $3)$ congruences, i.e. $\ 374 = (2\cdot 11)\, 17 = 22\cdot 17\ $ so

$\!\!\bmod \color{#0a0}{22}\!:\,\ \overbrace{{-}3x \equiv -15^{\phantom{.}}}^{\Large\ 19x\ \ \equiv\ \ 7_{\phantom{I}}}\! \iff x\, \equiv\, \color{#0a0}5$

$\!\!\bmod \color{#c00}{17}\!:\ \ \ \ \ 2x \equiv -10\iff x \equiv -5 \equiv \color{#0a0}{5+22}\,\color{#c00}k \equiv 5\!+\!5k\!\iff\! 5k \equiv-10\!\iff\! \color{#c00}{k \equiv -2}$

so substituting for $\,\color{#c00}k\,$ we obtain that: $\,\ x = 5 + 22(\color{#c00}{-2\!+\!17}n)\equiv \bbox[5px,border:1px solid red]{-39\equiv 335 \pmod{\!374}}$

---

Alternatively applying $ $ Gauss's algorithm and Inverse Reciprocity we easily compute

$\bmod 374\!:\,\ \dfrac{7}{19} \equiv \dfrac{19\cdot 7\ \ }{19\cdot 19}\equiv \dfrac{ 133}{-13} \equiv \dfrac{\color{#90f}{133+374}}{-13}\equiv -39,\ $ by $\bmod 13\!:\,\ \color{#90f}{133}\equiv 3\equiv \color{#90f}{-374}$