Bézout's Lemma
In number theory, Bézout's Lemma, also called Bézout's Identity, states that for any integers and
with greatest common denominator
, there exist integers
and
such that
. Furthermore, the integers of the form
are exactly the multiples of
. 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 and
be
and
respectively. Note that
, The Lemma thus states that there exist integers
and
such that
. A solution
of this equation is
.
Proofs of Bézout's Lemma
Proof 1
Note that because the integers of the form are the multiples of
—and because there exist integers
and
such that
reaches
—
is the smallest positive value of
. This observation might lead us to write the following proof:
Let and
be integers. We define the set
as follows:
Because
only contains positive integers, the well-ordering principle guarantees it has a minimum value:
for some
,
, and
. We wish to prove that
; hence, we must show that
divides both
and
, and that for all
such that
and
,
.
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).