Bézout's Identity/Proof 6

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

We have that Integers are Euclidean Domain, where the Euclidean valuation $\nu$ is defined as:

$\map \nu x = \size x$

The result follows from Bézout's Identity on Euclidean Domain.

$\blacksquare$

Source of Name

This entry was named for Étienne Bézout.