Bezout's coefficients proof

Question

I have a little problem with proof one property of Bezout's coefficients.

Given $a,b$, there are exactly two pairs of integers $x,y$ such that:

$xa+yb = gcd(a,b)$ and $|x| \leq \frac{b}{gcd(a,b)}, |y| \leq \frac{a}{gcd(a,b)}$ .

Anyone can help me with that? I'm not really sure were to start.

Answer 1

For simplicity, let's write $d = \gcd(a,b)$.

Note that if $(x_0,y_0)$ is a solution of $ax+by = d$, then so is $(x_1,y_1) = (x_0+k \frac bd, y_0-k \frac ad)$ for any integer $k$.

By choosing $k$ appropriately, one may assure that $x_1 = x_0 + k \frac bd$ is at most $\frac bd$ in absolute value. But then $$|by_1| = |d + ax_1| \leq d + a |x_1| \leq d + \frac{ab}{d} .$$ Dividing by $b$ yields $|y_1| \leq a/d$.