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 $4$th step subtraction becomes $99 - ((133 - 99) \cdot 2)$




So first evaluate $(133\cdot 0 + 99\cdot 1)$, then evaluate $(133\cdot 1 - 99 \cdot (-1))$, then evaluate $99 - (34 \cdot 2)$ and finally $99 - 68 = 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 \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...