Bézout's Lemma/Proof 3

From ProofWiki
Jump to: navigation, search

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$


Sources