Bézout's Lemma
Contents |
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$.
This result is also known as Bézout's Identity.
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 a > 0\) | \(\implies\) | \(\displaystyle \left \vert {a} \right \vert = 1 \times a + 0 \times b\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle a < 0\) | \(\implies\) | \(\displaystyle \left \vert {a} \right \vert = \left({-1}\right) \times a + 0 \times b\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle b > 0\) | \(\implies\) | \(\displaystyle \left \vert {b} \right \vert = 0 \times a + 1 \times b\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle b < 0\) | \(\implies\) | \(\displaystyle \left \vert {b} \right \vert = 0 \times a + \left({-1}\right) \times b\) | \(\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 \exists m, n, \in \Z:\) | \(\displaystyle x\) | \(=\) | \(\displaystyle m a + n b\) | \(\displaystyle \) | |||
| \(\displaystyle \implies\) | \(\displaystyle r\) | \(=\) | \(\displaystyle x - q d\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({m a + n b}\right) - q \left({u a + v b}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({m - q u}\right) a + \left({n - q v}\right) b\) | \(\displaystyle \) | |||
| \(\displaystyle \implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \left({r \in S}\right) \land \left({r < d}\right)\) | \(\displaystyle \) |
which contradicts the choice of $d$ as the smallest element of $S$.
Therefore $\forall x \in S: d \backslash x$.
Thus $d \backslash a \land d \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 \gcd \left\{ {a, b}\right\}\) | \(\backslash\) | \(\displaystyle \left({u a + v b}\right) = d\) | \(\displaystyle \) | Common Divisor Divides Integer Combination | ||
| \(\displaystyle \implies\) | \(\displaystyle \gcd \left\{ {a, b}\right\}\) | \(\backslash\) | \(\displaystyle d\) | \(\displaystyle \) | |||
| \(\displaystyle \implies\) | \(\displaystyle \gcd \left\{ {a, b}\right\}\) | \(\le\) | \(\displaystyle d\) | \(\displaystyle \) |
So $\gcd \left\{{a, b}\right\} = d = u a + v b$.
$\blacksquare$
Applications
It is primarily used when finding solutions to linear Diophantine equations, but is also used to find solutions via Euclidean Division Algorithm.
This Identity/Lemma 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.
This result can also be expanded to include more general objects, probably even as far up as integral domains. Further research needed.
You can help Proof Wiki by completing it.
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{WIP}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Source
- C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.11$: Theorem $19$
- George E. Andrews: Number Theory (1971): $\S 2.2$: Corollary $2.1$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 12.3$
- John F. Humphreys: A Course in Group Theory (1996): $\text{A}.1$: Theorem $\text{A}.2$
