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