Saturday 15 December 2012

modular arithmetic - 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. But I am unable to find any such. That is why I have chosen to post this. Thanks n advance.


Answer



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...