Bézout's Lemma

In number theory, Bézout's Lemma, also called Bézout's Identity, states that for any integers $a$ and $b$ with greatest common denominator $d$ , there exist integers $x$ and $y$ such that $ax + by = d$ . Furthermore, the integers of the form $ax + by$ are exactly the multiples of $d$ . Bézout's Lemma is a foundational result in number theory that implies many other theorems, such as Euclid's Lemma and the Chinese Remainder Theorem.

To see an example of Bézout's Lemma, let $a$ and $b$ be $15$ and $6$ respectively. Note that $\gcd (a, b) = 3$ , The Lemma thus states that there exist integers $x$ and $y$ such that $15x + 6y = 3$ . A solution $(x, y)$ of this equation is $(1, -2)$ .

Proofs of Bézout's Lemma

Proof 1

Note that because the integers of the form $ax + by$ are the multiples of $d$ —and because there exist integers $x$ and $y$ such that $ax + by$ reaches $d$ — $d$ is the smallest positive value of $ax + by$ . This observation might lead us to write the following proof:

Let $a$ and $b$ be integers. We define the set $S$ as follows: $S = \{ ax + by \textrm{ } | \textrm{ } x, y \in \mathbb{Z}, ax + by > 0\} .$ Because $S$ only contains positive integers, the well-ordering principle guarantees it has a minimum value: $ax_0 + by_0 = d_0$ for some $x_0$ , $y_0$ , and $d_0$ . We wish to prove that $d_0 = d$ ; hence, we must show that $d_0$ divides both $a$ and $b$ , and that for all $c$ such that $c|a$ and $c|b$ , $c|d_0$ .

Proof 2

(Note: This article is a work in progress! I don't believe AoPS has sandboxes, sadly. This should eventually replace Bezout's Lemma as the main article).

Page

Toolbox

Search

Bézout's Lemma

Proofs of Bézout's Lemma

Proof 1

Proof 2