0
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 19 '19 at 13:42
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So you basically just guess the new mods? Is there any formula or recipe to guess them faster? $\endgroup$ – luchka13 Jun 19 '19 at 9:52
  • $\begingroup$ I figured it out. Thank you for the help! $\endgroup$ – luchka13 Jun 19 '19 at 10:13
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's easier to use two congruences, e.g. see my answer. $\endgroup$ – Bill Dubuque Jun 19 '19 at 13:15
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.