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

Let $a = a_0 d$ and $b = b_0 d$ for some $a_0$ and $b_0$ , where $\gcd(a, b) = 1$ . We may divide $ax + by = d$ by $d$ to get an equivalent equation we wish to prove—namely, that $a_0 x + b_0 y = 1$ . Using the observation that $1$ is the smallest positive integer, we write the following proof:

Let $a_0$ and $b_0$ be relatively prime positive integers. We define the set $S$ as follows: $S = \{ a_0 x + b_0 y \mid x, y \in \mathbb{Z}, a_0 x + b_0 y > 0\} .$ Because $S$ only contains positive integers, the well-ordering principle guarantees it has a minimum value: $a_0x + b_0y = d_0$ for some $x$ , $y$ , and $d_0$ . We wish to prove that $d_0 = 1$ ; hence, we must show that $d_0$ divides both $a_0$ and $b_0$ .

By Euclidean division, there exist integers $q$ and $r$ such that $a_0 = d_0 q + r$ and $0 \leq r < d_0$ . Solving for $r$ , we have that $r = a_0 - d_0q$ . Substituting $a_0x + b_0y = d_0$ yields $r = a_0 - (a_0x + b_0y)q$ $r = a_0(1-qx) + b_0(qy)$ . Hence, $r$ is of the form $a_0x + b_0y$ . Note that we defined $r$ to be less than $d_0$ —then because $d_0$ is the smallest positive number of the form $a_0x + b_0y$ , $r$ must be $0$ . Hence, $a_0 = d_0 q$ , and $d_0 \mid a_0$ .

Via similar logic, we may deduce that $d_0 | b_0$ . Hence, $d_0 | gcd(a_0, b_0$ , or $d_0 | 1$ . Then because $d_0$ is positive, it must be equal to $1$ . Therefore, there exist integers $x$ and $y$ such that $a_0x + b_0y = 1.$ Multiplying by $d$ gives us $ax + by = d$ , as desired. $\square$

(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