Bézout's Lemma

From ProofWiki
(Redirected from Bezout's Lemma)
Jump to navigation Jump to 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 1

Work the Euclidean Division Algorithm backwards.

$\blacksquare$


Proof 2

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.

Let $S$ be the set of all positive integer combinations of $a$ and $b$:

$S = \set {x \in \Z, x > 0: x = m a + n b: m, n \in \Z}$


First we establish that $S \ne \O$.

We have:

\(\displaystyle a > 0\) \(\implies\) \(\displaystyle \size a = 1 \times a + 0 \times b\)
\(\displaystyle a < 0\) \(\implies\) \(\displaystyle \size a = \paren {-1} \times a + 0 \times b\)
\(\displaystyle b > 0\) \(\implies\) \(\displaystyle \size b = 0 \times a + 1 \times b\)
\(\displaystyle b < 0\) \(\implies\) \(\displaystyle \size b = 0 \times a + \paren {-1} \times b\)


As it is not the case that both $a = 0$ and $b = 0$, it must be that at least one of $\size a \in S$ or $\size b \in S$.

Therefore $S \ne \O$.


As $S$ contains only positive integers, $S$ is bounded below by $0$ and therefore $S$ has a smallest element.

Call this smallest element $d$: we have $d = u a + v b$ for some $u, v \in \Z$.


Let $x \in S$.

By the Division Theorem:

$x = q d + r, 0 \le r < d$

Suppose $d \nmid x$.

Then $x \ne q d$ and so $0 < r$.

But:

\(\, \displaystyle \exists m, n \in \Z: \, \) \(\displaystyle x\) \(=\) \(\displaystyle m a + n b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle r\) \(=\) \(\displaystyle x - q d\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {m a + n b} - q \paren {u a + v b}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {m - q u} a + \paren {n - q v} b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\displaystyle \paren {r \in S} \land \paren {r < d}\)

which contradicts the choice of $d$ as the smallest element of $S$.


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

In particular:

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

Thus:

$d \divides a \land d \divides b \implies 1 \le d \le \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 a + v b} = d\) Common Divisor Divides Integer Combination
\(\displaystyle \leadsto \ \ \) \(\displaystyle \gcd \set {a, b}\) \(\divides\) \(\displaystyle d\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \gcd \set {a, b}\) \(\le\) \(\displaystyle d\)


Since $d$ is the smallest number in $S$:

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

$\blacksquare$


Proof 3

Consider the Euclidean algorithm in action:

\(\displaystyle a\) \(=\) \(\displaystyle q_1 b + r_1\)
\(\displaystyle b\) \(=\) \(\displaystyle q_2 r_1 + r_2\)
\(\displaystyle r_1\) \(=\) \(\displaystyle q_3 r_2 + r_3\)
\(\displaystyle \cdots\) \(\) \(\displaystyle \)
\(\displaystyle r_{n - 2}\) \(=\) \(\displaystyle q_n r_{n - 1} + r_n\)
\(\displaystyle r_{n - 1}\) \(=\) \(\displaystyle q_{n + 1} r_n + 0\)

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$.

When $i = 2$, let $x_2 = -q_2, y_2 = 1 + q_1 q_2$.

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$


Proof 4

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.

Let $J$ be the set of all integer combinations of $a$ and $b$:

$J = \set {x: x = m a + n b: m, n \in \Z}$


First we show that $J$ is an ideal of $\Z$

Let $\alpha = m_1 a + n_1 b$ and $\beta = m_2 a + n_2 b$, and let $c \in \Z$

Then $\alpha,\beta \in J$ and :


\(\displaystyle \alpha + \beta\) \(=\) \(\displaystyle m_1 a + n_1 b + m_2 a + n_2 b\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {m_1 + m_2} a + \paren {n_1 + n_2} b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \alpha + \beta\) \(\in\) \(\displaystyle J\)


\(\displaystyle c \alpha\) \(=\) \(\displaystyle c \paren {m_1 a + n_1 b}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {c m_1} a + \paren {c n_1} b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle c \alpha\) \(\in\) \(\displaystyle J\)


Thus $J$ is an integral ideal.

We have that:

\(\displaystyle a\) \(=\) \(\displaystyle 1 a + 0 b\)
\(\, \displaystyle \land \, \) \(\displaystyle b\) \(=\) \(\displaystyle 0 a + 1 b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a, b\) \(\in\) \(\displaystyle J\)


$a$ and $b$ are not both zero, thus:

$J \ne \set 0$

By the something {theorem about ideals}:

$\exists x_0 > 0 : J = x_0 \Z$


$a \in J \land \set {J = x_0 \Z} \implies x_0 \divides a$
$b \in J \land \set {J = x_0 \Z} \implies x_0 \divides b$


$x_0 \divides a \land x_0 \divides b \implies x_0 \in \map D {a, b}$



Furthermore:

$x_0 \in J \implies \exists r, s \in \Z : x_0 = r a + s b$


Let $x_1 \in \map D {a, b}$.

Then:

\(\displaystyle x_1 \in \map D {a, b}\) \(\leadsto\) \(\displaystyle x_1 \divides a \land x_1 \divides b\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle x_1 \divides \paren {r a + s b}\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle x_1 \vert x_0\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle \size {x_1} \le \size {x_0} = x_0\)

Thus:

$x_0 = \max \set {\map D {a, b} } = \gcd \set {a, b} = r a + s b$

$\blacksquare$


Proof 5

Let $\gcd \set {a, b} = d$.

Let $\dfrac a d = p$ and $\dfrac b d = q$.

From Integers Divided by GCD are Coprime:

$\gcd \left\{{p, q}\right\} = 1$

From Integer Combination of Coprime Integers:

$\exists x, y \in \Z: p x + q y = 1$

The result follows by multiplying both sides by $d$.

$\blacksquare$


Proof 6

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 Lemma on Euclidean Domain.

$\blacksquare$


Also known as

This result is also known as Bézout's Identity.


Also see


Applications

Bézout's Lemma is primarily used when finding solutions to linear Diophantine equations, but is also used to find solutions via Euclidean Division Algorithm.

This result can also be applied to the Extended Euclidean Division Algorithm.


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.