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
Let and for some and , where . We may divide by to get an equivalent equation we wish to prove—namely, that . Using the observation that is the smallest positive integer, we write the following proof:
Let and be relatively prime positive 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 .
By Euclidean division, there exist integers and such that and . Solving for , we have that . Substituting yields . Hence, is of the form . Note that we defined to be less than —then because is the smallest positive number of the form , must be . Hence, , and .
Via similar logic, we may deduce that . Hence, , or . Then because is positive, it must be equal to . Therefore, there exist integers and such that Multiplying by gives us , as desired.
(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).