I was trying the Extended Euclidean Algorithm on various pairs of numbers to find a logic on the Bezout Coefficients produced. But, I am confused about the nature of the coefficients.
I found the GCD of 21 and 14 and then found the Bezout Coefficients, it was the diophantine equation 7=21⋅1+14⋅−1 What I don't understand is why the coefficients produced were those. One can easily represent them as 7=14⋅2+21⋅−1 Similarly, 3=21⋅2+39⋅−1 can also be written as 7=39⋅6+21⋅−11 I want to know why the Bezout Coefficients produced by the Extended Euclidean Algorithm are those. It seems that the Bezout Coefficients produce for gcd(a,b)=ax+by are those where |x|+|y| is the lowest. Is there a proof for that statement and are there some papers about it?
Furthermore, consider that a and b are both positive and the equation gcd(a,b)=ax+by We know that as x increases, y decreases. I want to know of the importance of the two solutions (x1,y1) and (x2,y2) where x1<y1 but x2>y2 and they are the solutions immediately next to each other.
It is the point of inversion of the larger of the solutions.
Thanks.
No comments:
Post a Comment