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 = 21 \cdot 1 + 14 \cdot -1$$ What I don't understand is why the coefficients produced were those. One can easily represent them as $$7 = 14 \cdot 2 + 21 \cdot -1$$ Similarly, $$3 = 21 \cdot 2 + 39 \cdot -1$$ can also be written as $$7 = 39 \cdot 6 + 21 \cdot -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 $(x_1, y_1)$ and $(x_2, y_2)$ where $x_1 < y_1$ but $x_2 > y_2$ 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 \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...