Bezout's lemma states that if a and b are integers, and at least one of them is non-zero, then there exist integers $x, y$ such that $$ax + by = gcd(a, b)$$ One way of finding such a pair $(x, y)$ is the extended Euclidean algorithm where in each step we express the remainder (until it becomes zero) as an integral linear combination of $a, b$. There exist many such pairs $x, y$ which satisfy Bezout's lemma for $a, b$ but the one given by the extended Euclidean algorithm are minimal in absolute value. How do I prove this?

  • 1
    $\begingroup$ Yes, there exist many pairs $x$, $y$, but do you understand the formula that gives all of them in terms of any one of them? From that, can you see which solution minimizes absolute value? and why the extended Euclidean algorithm gives you that solution? $\endgroup$ – Gerry Myerson Sep 7 '13 at 11:56
  • 1
    $\begingroup$ You can observe that the Euclidean algorithm is equivalent to the continued fraction algorithm, hence $\frac{\lvert x\rvert}{\lvert y\rvert}$ is the penultimate convergent of $\frac{b}{a}$, and that is the first neighbour of $\frac{b}{a}$ in any Farey sequence. $\endgroup$ – Daniel Fischer Sep 7 '13 at 11:56
  • $\begingroup$ @GerryMyerson Yes I know that if I've found a solution (x, y) and d = gcd(a, b) then all other solutions are given by (x - kb/d, y + ka/d) where k is an integer other than 0 but I don't know how to relate it to the extended Euclidean algorithm. $\endgroup$ – ajay Sep 7 '13 at 12:02
  • $\begingroup$ Well, one thing at a time. Knowing the general form of the solution, which solution is going to minimize the absolute value? $\endgroup$ – Gerry Myerson Sep 7 '13 at 12:05
  • $\begingroup$ @Daniel, maybe something needs to be said about the case in which the gcd is not 1. $\endgroup$ – Gerry Myerson Sep 7 '13 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.