2

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.

TheRandomGuy
  • 4,014
  • 2
  • 20
  • 56
  • You're right. The Extended Euclidean Algorithm finds the solution closest to the origin. I don't have a reference handy but it is not hard to prove. See also http://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm. – lhf Apr 02 '16 at 11:31
  • @lhf Then could you suggest a method of proving this. – TheRandomGuy Apr 02 '16 at 11:35
  • See http://math.stackexchange.com/questions/670405/does-the-extended-euclidean-algorithm-always-return-the-smallest-coefficients-of. – lhf Apr 02 '16 at 11:45
  • 1
    @lhf Am I right to claim that there exist exactly two $x$'s and $y$'s such that: $$-|\frac{a}{\gcd(a,b)}| < x < |\frac{a}{\gcd(a,b)}| $$ and $$ -|\frac{b}{\gcd(a,b)}| < y< |\frac{b}{\gcd(a,b)}| $$ (Those are absolute values.) – TheRandomGuy Apr 02 '16 at 12:53

0 Answers0