Bézout's Lemma/Proof 3

Theorem

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.

Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.

Then:

$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$

That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.

Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof

Consider the Euclidean algorithm in action:

 $\displaystyle a$ $=$ $\displaystyle q_1 b + r_1$ $\quad$ $\quad$ $\displaystyle b$ $=$ $\displaystyle q_2 r_1 + r_2$ $\quad$ $\quad$ $\displaystyle r_1$ $=$ $\displaystyle q_3 r_2 + r_3$ $\quad$ $\quad$ $\displaystyle \cdots$  $\displaystyle$ $\quad$ $\quad$ $\displaystyle r_{n - 2}$ $=$ $\displaystyle q_n r_{n - 1} + r_n$ $\quad$ $\quad$ $\displaystyle r_{n - 1}$ $=$ $\displaystyle q_{n + 1} r_n + 0$ $\quad$ $\quad$

First it will be established that there exist $x_i, y_i \in \Z$ such that:

$(1): \quad a x_i + b y_i = r_i$

for $i \in \set{1, 2, \ldots, n - 1}$.

The proof proceeds by induction.

Basis for the Induction

When $i = 1$, let $x_1 = 1, y_1 = -q_1$.

This is the basis for the induction.

Induction Hypothesis

Our induction hypothesis is that the integer solutions to $(1)$ have been found for all $i$ such that $i \le k$ where $k < n - 1$.

Induction Step

We know that:

$r_{k - 1} = r_k q_{k + 1} + r_{k + 1}$

Thus, by the induction hypothesis:

$\paren {a x_{k - 1} + b y_{k - 1} } - \paren {a x_k + b y_k} q_{k + 1} = r_{k + 1}$

which can be rewritten as:

$\paren {x_{k - 1} - x_k q_{k + 1} } a + \paren {y_{k - 1} - y_k q_{k + 1} } b = r_{k + 1}$

Hence we have the following solutions to $(1)$ when $i = k + 1$:

$x_{k + 1} = x_{k - 1} - x_k q_{k + 1}$
$y_{k + 1} = y_{k - 1} - y_k q_{k + 1}$

The result follows by the Principle of Mathematical Induction.

$\blacksquare$