# Solving a congruence with Chinese Remainder Theorem

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!

• If you insist on using CRT then it's much easier to use $2$ (vs. $3)$ congruences - see my answer. But generally it is easier to use the extended Euclidean algorithm or Gauss's algorithm to compute such fractions, e.g. here. – Bill Dubuque Jun 19 '19 at 13:42

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

• So you basically just guess the new mods? Is there any formula or recipe to guess them faster? – luchka13 Jun 19 '19 at 9:52
• I figured it out. Thank you for the help! – luchka13 Jun 19 '19 at 10:13

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

• It's easier to use two congruences, e.g. see my answer. – Bill Dubuque Jun 19 '19 at 13:15

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