Bézout's Lemma

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 1

Work the Euclidean Division Algorithm backwards.


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 = \left\{{x \in \Z, x > 0: x = m a + n b: m, n \in \Z}\right\}$


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

We have:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle a > 0\) \(\implies\) \(\displaystyle \) \(\displaystyle \left \vert {a} \right \vert = 1 \times a + 0 \times b\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle a < 0\) \(\implies\) \(\displaystyle \) \(\displaystyle \left \vert {a} \right \vert = \left({-1}\right) \times a + 0 \times b\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle b > 0\) \(\implies\) \(\displaystyle \) \(\displaystyle \left \vert {b} \right \vert = 0 \times a + 1 \times b\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle b < 0\) \(\implies\) \(\displaystyle \) \(\displaystyle \left \vert {b} \right \vert = 0 \times a + \left({-1}\right) \times b\) \(\displaystyle \) \(\displaystyle \)                    


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

Therefore $S \ne \varnothing$.


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 \) \(\displaystyle \exists m, n, \in \Z:\) \(\displaystyle \) \(\displaystyle x\) \(=\) \(\displaystyle \) \(\displaystyle m a + n b\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle r\) \(=\) \(\displaystyle \) \(\displaystyle x - q d\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({m a + n b}\right) - q \left({u a + v b}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({m - q u}\right) a + \left({n - q v}\right) b\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left({r \in S}\right) \land \left({r < d}\right)\) \(\displaystyle \) \(\displaystyle \)                    

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


Therefore $\forall x \in S: d \mathop \backslash x$.

In particular:

$d \mathop \backslash \left \vert {a} \right \vert = 1 \times a + 0 \times b$
$d \mathop \backslash \left \vert {b} \right \vert = 0 \times a + 1 \times b$

Thus:

$d \mathop \backslash a \land d \mathop \backslash b \implies 1 \le d \le \gcd \left\{{a, b}\right\}$


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

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \gcd \left\{ {a, b}\right\}\) \(\backslash\) \(\displaystyle \) \(\displaystyle \left({u a + v b}\right) = d\) \(\displaystyle \) \(\displaystyle \)          Common Divisor Divides Integer Combination          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \gcd \left\{ {a, b}\right\}\) \(\backslash\) \(\displaystyle \) \(\displaystyle d\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \gcd \left\{ {a, b}\right\}\) \(\le\) \(\displaystyle \) \(\displaystyle d\) \(\displaystyle \) \(\displaystyle \)                    


So $\gcd \left\{{a, b}\right\} = d = u a + v b$.

$\blacksquare$


Also known as

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


Also see


Applications

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

However, there are sources which suggest that this identity was first noticed by Claude Gaspard Bachet de Méziriac.

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




Sources