# Extended Euclidean Algorithm: a remainder becomes zero

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.

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

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.