Does the Extended Euclidean Algorithm always return the smallest coefficients of Bézout's identity?

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}$.

Solution 1:

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$.

Solution 2:

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.