Difference between revisions of "Bézout's Lemma"

Latest revision as of 10:19, 5 March 2023

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).

@@ Line 5: / Line 5: @@
 == Proofs of Bézout's Lemma ==
 === Proof 1 ===
-Note that because the integers of the form <math>ax + by</math> are the multiples of <math>d</math>—and because there exist integers <math>x</math> and <math>y</math> such that <math>ax + by</math> reaches <math>d</math>—<math>d</math> is the smallest positive value of <math>ax + by</math>. This observation might lead us to write the following proof:
+Let <math>a = a_0 d</math> and <math>b = b_0 d</math> for some <math>a_0</math> and <math>b_0</math>, where <math>\gcd(a, b) = 1</math>. We may divide <math>ax + by = d</math> by <math>d</math> to get an equivalent equation we wish to prove—namely, that <math>a_0 x + b_0 y = 1</math>. Using the observation that <math>1</math> is the smallest positive integer, we write the following proof:
-Let <math>a</math> and <math>b</math> be integers. We define the set <math>S</math> as follows: <cmath>S = \{ ax + by \textrm{ } | \textrm{ } x, y \in \mathbb{Z}, ax + by > 0\} .</cmath> Because <math>S</math> only contains positive integers, the well-ordering principle guarantees it has a minimum value: <math>ax_0 + by_0 = d_0</math> for some <math>x_0</math>, <math>y_0</math>, and <math>d_0</math>. We wish to prove that <math>d_0 = d</math>; hence, we must show that <math>d_0</math> divides both <math>a</math> and <math>b</math>, and that for all <math>c</math> such that <math>c|a</math> and <math>c|b</math>, <math>c|d_0</math>.
-=== Proof 2 ===
+Let <math>a_0</math> and <math>b_0</math> be relatively prime positive integers. We define the set <math>S</math> as follows: <cmath>S = \{ a_0 x + b_0 y \mid x, y \in \mathbb{Z}, a_0 x + b_0 y > 0\} .</cmath> Because <math>S</math> only contains positive integers, the well-ordering principle guarantees it has a minimum value: <math>a_0x + b_0y = d_0</math> for some <math>x</math>, <math>y</math>, and <math>d_0</math>. We wish to prove that <math>d_0 = 1</math>; hence, we must show that <math>d_0</math> divides both <math>a_0</math> and <math>b_0</math>.
+By Euclidean division, there exist integers <math>q</math> and <math>r</math> such that <math>a_0 = d_0 q + r</math> and <math>0 \leq r < d_0</math>. Solving for <math>r</math>, we have that <math>r = a_0 - d_0q</math>. Substituting <math>a_0x + b_0y = d_0</math> yields <cmath>r = a_0 - (a_0x + b_0y)q</cmath> <cmath>r = a_0(1-qx) + b_0(qy)</cmath>.
+Hence, <math>r</math> is of the form <math>a_0x + b_0y</math>. Note that we defined <math>r</math> to be less than <math>d_0</math>—then because <math>d_0</math> is the smallest positive number of the form <math>a_0x + b_0y</math>, <math>r</math> must be <math>0</math>. Hence, <math>a_0 = d_0 q</math>, and <math>d_0 \mid a_0</math>.
+Via similar logic, we may deduce that <math>d_0 | b_0</math>. Hence, <math>d_0 | gcd(a_0, b_0</math>, or <math>d_0 | 1</math>. Then because <math>d_0</math> is positive, it must be equal to <math>1</math>. Therefore, there exist integers <math>x</math> and <math>y</math> such that <cmath>a_0x + b_0y = 1.</cmath> Multiplying by <math>d</math> gives us <math>ax + by = d</math>, as desired. <math>\square</math>
 (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

Difference between revisions of "Bézout's Lemma"

Latest revision as of 10:19, 5 March 2023

Proofs of Bézout's Lemma

Proof 1