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.
x2 mod 3


x3 mod 5

x4 mod 11

x5 mod 16




Problem I am having is, when I apply the extended Euclidean Algorithm to find M2 such that N2.M21 mod n2 (where n2=5 and N2=3×11×16=528 and M3 being the modular inverse of 528 under  mod 5), I reach the following.



528=105×5+3105=35×3+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÷5 as the dividend, whereas it should actually be 5, which is the divider of the previous iteration. So it actually should be




528=105×5+35=1×3+23=1×2+1


and that's it. Thanks to @N.F.Taussig and @LordSharktheUnknown.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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