11
$\begingroup$

Bezout's identity says that there are integers $x$ and $y$ such that $ax + by = gcd(a, b)$ and the Extended Euclidean Algorithm finds a particular solution. For instance,

$333\cdot-83 + 1728\cdot16 = \gcd(333, 1728) = 9$.

Will the Extended Euclidean Algorithm always return the smallest $x$ and $y$ that satisfy the identity? By small, I mean that $|x|, |y|$ are minimized.

Because $333\cdot(-83 + 1728t) + 1728\cdot(16 - 333t) = \gcd(333, 1728)$ is also a solution for all $t \in \mathbf{Z}$.

$\endgroup$
4
  • 2
    $\begingroup$ You should write $333\cdot(-83 + 192t) + 1728\cdot(16 - 37t) = \gcd(333, 1728)$ $\endgroup$
    – Will Jagy
    Feb 10, 2014 at 2:55
  • 1
    $\begingroup$ There are many variations on "the" extended Euclidean algorithm. Which version do you refer to? $\endgroup$ Feb 10, 2014 at 3:01
  • $\begingroup$ Will Jagy - I am not sure what you mean by "You put the smaller number first; try gcd(16,83) by your exact method. You should get the second best pair." ----- Bill Dubuque - I am referring to the one found here: ----- en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/… $\endgroup$ Feb 10, 2014 at 3:22
  • $\begingroup$ See also math.stackexchange.com/questions/1001199/… $\endgroup$
    – lhf
    Apr 23, 2020 at 1:05

2 Answers 2

16
$\begingroup$

We can assume that the GCD is $1$, because the Euclidean algorithm for $a/g,\,b/g$ is just the algorithm for $a,b$ "scaled down", that is, the quotients remain the same and the other numbers are divided by $g$. We'll also assume that $a>b>1$.

As has been pointed out in comments, there are various implementations of the Euclidean algorithm, but suppose you do it this way, taking $n$ steps: $$\eqalign{ a&=q_1b+r_1\cr b&=q_2r_1+r_2\cr &\ \vdots\cr r_{n-2}&=q_{n-2}r_{n-1}+1\ .\cr}$$ Then you find the Bezout identity by reversing the procedure: $$\eqalign{1 &=r_{n-2}-q_{n-2}r_{n-1}\cr &=r_{n-2}-q_{n-2}(r_{n-3}-q_{n-3}r_{n-2})\cr &=-q_{n-2}r_{n-3}+(q_{n-2}q_{n-3}+1)r_{n-2}\cr &=\cdots\cr &=xa+yb\ .\cr}$$ Then we have $|x|\le b/2$ and $|y|\le a/2$. This can be proved by induction on $n$.

If $n=1$ we have just one line $a=qb+1$, so the Bezout identity is $a-qb=1$: the coefficients are $x=1$, $y=-q$ and we have $$|x|\le b/2\ ,\quad |y|=q\le qb/2<a/2\ .$$

Now suppose that a procedure of $n-1$ steps gives $$bX+r_1Y=1$$ where by induction we may assume $$|X|\le r_1/2\ ,\quad |Y|\le b/2\ .$$ Then the final step is $$1=bX+(a-qb)Y=aY-(qY-X)b=ax+by$$ where $$x=Y\ ,\quad y=-(qY-X)\ .$$ Therefore $$|x|=|Y|\le b/2\quad\hbox{and}\quad |y|\le q|Y|+|X|\le qb/2+r_1/2=a/2\ ,$$ and this completes the proof by induction.

Since the general solution for $x$ is $x=x_0+bt$, any value of $x$ between $-b/2$ and $b/2$ must be numerically the smallest possible; and similarly for $y$.

$\endgroup$
4
  • $\begingroup$ Thank you David for your very detailed response. I guess what I am asking is that, are the x and y that are found by the Extended Euclidean Algorithm the smallest x and y (in the absolute value sense) that satisfy ax + by = 1? $\endgroup$ Feb 10, 2014 at 4:03
  • 1
    $\begingroup$ Have just added an extra sentence at the end of my answer which I hope clears this up. $\endgroup$
    – David
    Feb 10, 2014 at 4:31
  • $\begingroup$ @David When you reverse the procedure how do you jump from line 2 to line 3. Why've you shortened $-q_{n-2}r_{n-3}$ to just $-q_{n-2}$? $\endgroup$ Apr 2, 2016 at 13:00
  • $\begingroup$ @Dhruv typo, fixed. $\endgroup$
    – David
    Apr 3, 2016 at 23:30
1
$\begingroup$

This question, as well as an extension to the GCD of more than two numbers, is analyzed in Section 3 of this paper by Majewski and Havas: http://staff.itee.uq.edu.au/havas/1994mh.pdf

They show that the same bound holds for the case of more than two numbers: one can always find coefficients that are at most half the largest number in absolute value. They also show how to find those coefficients very efficiently.

$\endgroup$
1
  • $\begingroup$ The extension to greatest common divisors of more than two numbers is doubtless an interesting Question, but it's not clear if you are actually answering the Question posed here, whether Extended Euclidean algorithm can promise the optimal size coefficients. The Question is a bit vague (about how size should be measured, and what specific variants of Extended Euclidean algorithm may be specified), but the older Answer offers some details to address that. $\endgroup$
    – hardmath
    May 24, 2014 at 4:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.