# 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:

\(\, \displaystyle \exists m, n \in D: \, \) | \(\displaystyle x\) | \(=\) | \(\displaystyle m \times a + n \times b\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle r\) | \(=\) | \(\displaystyle x - q \times d\) | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {m \times a + n \times b} - q \paren {u \times a + v \times b}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {m - q \times u} a + \paren {n - q \times v} b\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(\) | \(\displaystyle \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:

\(\displaystyle \gcd \set {a, b}\) | \(\divides\) | \(\displaystyle \paren {u \times a + v \times b} = d\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \gcd \set {a, b}\) | \(\divides\) | \(\displaystyle d\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \map \nu {\gcd \set {a, b} }\) | \(\le\) | \(\displaystyle \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.