0
$\begingroup$

When working on the Chinese Remainder Theorem, I have stumbled upon this system of linear congruences. $$ x\equiv2 \mbox{ mod 3} $$ $$ x\equiv3 \mbox{ mod 5} $$ $$ x\equiv4 \mbox{ mod 11} $$ $$ x\equiv5 \mbox{ mod 16} $$

Problem I am having is, when I apply the extended Euclidean Algorithm to find $M_2$ such that $N_2.M_2\equiv1\mbox{ mod }n_2$ (where $n_2=5$ and $N_2=3\times11\times16=528$ and $M_3$ being the modular inverse of 528 under $\mbox{ mod }5$), I reach the following.

$$ 528=105\times5+3\\ 105=35\times3+0 $$ What I don't understand is how to go from this point forth. This question might have been repeated somewhere in this stack exchange. But I am unable to find any such. That is why I have chosen to post this. Thanks n advance.

$\endgroup$
  • $\begingroup$ @GAVD Thanks for making it look better. :) $\endgroup$ – Romeo Sierra Sep 22 '17 at 5:48
  • $\begingroup$ $528$ is not $105\times 5+30$. $\endgroup$ – Angina Seng Sep 22 '17 at 5:49
  • $\begingroup$ Corrected. It was a typo.. $\endgroup$ – Romeo Sierra Sep 22 '17 at 5:52
  • $\begingroup$ Surely, the next stage in your EEE should be $5-1\times 3=2$? $\endgroup$ – Angina Seng Sep 22 '17 at 5:54
  • $\begingroup$ @LordSharktheUnknown Didn't get you. Can you please elaborate? $\endgroup$ – Romeo Sierra Sep 22 '17 at 7:11
0
$\begingroup$

So the problem here is I am choosing the wrong input to the second iteration. I am choosing 105, which is the quotient of $528\div5$ as the dividend, whereas it should actually be 5, which is the divider of the previous iteration. So it actually should be

$$ 528=105\times5+3\\ 5=1\times3+2\\ 3=1\times2+1 $$ and that's it. Thanks to @N.F.Taussig and @LordSharktheUnknown.

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