# Bézout's Lemma/Euclidean Domain

## Theorem

Let $\struct {D, +, \times}$ be a Euclidean domain whose zero is $0$ and whose unity is $1$.

Let $\nu: D \setminus \set 0 \to \N$ be the Euclidean valuation on $D$.

Let $a, b \in D$ such that $a$ and $b$ are not both equal to $0$.

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

Then:

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

such that $\gcd \set {a, b}$ is the element of $D$ such that:

$\forall c = a \times x + b \times y \in D: \map \nu {\gcd \set {a, b} } \le \map \nu c$

## Proof

We are given that $a, b \in D$ such that $a$ and $b$ are not both equal to $0$.

Without loss of generality, suppose specifically that $b \ne 0$.

Let $S \subseteq D$ be the set defined as:

$S = \set {x \in D_{\ne 0}: x = m \times a + n \times b: m, n \in D}$

where $D_{\ne 0}$ denotes $D \setminus 0$.

Setting $m = 0$ and $n = 1$, for example, it is noted that $b \in S$.

Therefore $S \ne \O$.

By definition, $\nu$ has the properties:

$(1): \quad \forall a, b \in D, b \ne 0: \exists q, r \in D$ such that $\map \nu r < \map \nu b$, or $r = 0$, such that:
$a = q \times b + r$
$(2): \quad \forall a, b \in D, b \ne 0$:
$\map \nu a \le \map \nu {a \times b}$

Let $\nu \sqbrk S$ denote the image of $S$ under $\nu$.

We have that:

$\nu \sqbrk S \subseteq \N$

Hence by the Well-Ordering Principle $\nu \sqbrk S$ has a smallest element.

Let $d \in S$ be such that $\map \nu d$ is that smallest element of $\nu \sqbrk S$.

By definition of $S$, we have that:

$d = u \times a + v \times b$

for some $u, v \in D$.

Let $x \in S$.

By $(2)$ above:

$x = q \times d + r$

such that either:

$\map \nu r < \map \nu d$

or:

$r = 0$

Aiming for a contradiction, suppose $r \ne 0$.

Then:

 $\ds \exists m, n \in D: \,$ $\ds x$ $=$ $\ds m \times a + n \times b$ $\ds \leadsto \ \$ $\ds r$ $=$ $\ds x - q \times d$ $\ds$ $=$ $\ds \paren {m \times a + n \times b} - q \paren {u \times a + v \times b}$ $\ds$ $=$ $\ds \paren {m - q \times u} a + \paren {n - q \times v} b$ $\ds \leadsto \ \$ $\ds$  $\ds \paren {r \in S} \land \paren {\map \nu r < \map \nu d}$

which contradicts the choice of $d$ as the element of $S$ such that $\map \nu d$ is the smallest element of $\nu \sqbrk S$.

Therefore:

$\forall x \in S: x = q \times d$

for some $q \in D$.

That is:

$\forall x \in S: d \divides x$

where $\divides$ denotes divisibility.

In particular:

$d \divides a = 1 \times a + 0 \times b$
$d \divides b = 0 \times a + 1 \times b$

Thus:

$d \divides a \land d \divides b \implies \map \nu 1 \le \map \nu d \le \map \nu {\gcd \set {a, b} }$

However, note that as $\gcd \set {a, b}$ also divides $a$ and $b$ (by definition), we have:

 $\ds \gcd \set {a, b}$ $\divides$ $\ds \paren {u \times a + v \times b} = d$ $\ds \leadsto \ \$ $\ds \gcd \set {a, b}$ $\divides$ $\ds d$ $\ds \leadsto \ \$ $\ds \map \nu {\gcd \set {a, b} }$ $\le$ $\ds \map \nu d$

Since $d$ is the element of $S$ such that $\map \nu d$ is the smallest element of $\nu \sqbrk S$:

$\gcd \set {a, b} = d = u \times a + v \times b$

$\blacksquare$

## Source of Name

This entry was named for Étienne Bézout.

## Historical Note

There are sources which suggest that Bézout's Lemma was first noticed by Claude Gaspard Bachet de Méziriac.

Étienne Bézout's contribution was to prove a more general result, for polynomials.