Wednesday, August 16, 2017

calculus - Extended euclidean algorithm using table



I have to solve gcd(133,99)=d, d=ax+by using the extended euclidean algorithm. I understand a part of it but this table we have to use/fill out confuses me a bit.



I get bit confused at step 4. I sort of get the subtraction column I'm guessing () set the precedence so 4th step subtraction becomes 99((13399)2)




So first evaluate (1330+991), then evaluate (133199(1)), then evaluate 99(342) and finally 9968=31.



This is bit confusing but I guess understandable what confuses me the most is where I go wrong in the combined expression column on step 3 seems I made the correct assumption however on step 4 the result does not equal 31.



enter image description here


Answer



Hopefully this layout for the algorithm will help:



enter image description here



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...