When working on the Chinese Remainder Theorem, I have stumbled upon this system of linear congruences.
x≡2 mod 3
x≡3 mod 5
x≡4 mod 11
x≡5 mod 16
Problem I am having is, when I apply the extended Euclidean Algorithm to find M2 such that N2.M2≡1 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