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