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 \left\{{a, b}\right\}$ be the greatest common divisor of $a$ and $b$.

Then:

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


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


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


Proof

First we establish that:

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

include George E. Andrews: Number Theory coll.2-1


Now to show that $\gcd \left\{ {a, b}\right\}$ is the smallest positive number to satisfy the equation.

We first show that:

$\forall x \in \Z: \exists m, n \in \Z: x = m x + n y \ne 0 \implies d \mathrel \backslash x$

include George E. Andrews: Number Theory coll.2-2