Friday, November 20, 2015

number theory - Bezout Coefficients produced by Extended Euclidean Algorithm for a and b

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=211+141 What I don't understand is why the coefficients produced were those. One can easily represent them as 7=142+211 Similarly, 3=212+391 can also be written as 7=396+2111 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

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...