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

(WIP)
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
In [[number theory]], '''Bézout's Lemma''', also called '''Bézout's Identity''', states that for any integers <math>a</math> and <math>b</math> with greatest common denominator <math>d</math>, there exist integers <math>x</math> and <math>y</math> such that <math>ax + by  = d</math>. Furthermore, the integers of the form <math>ax + by</math> are exactly the multiples of <math>d</math>. 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]].
 
In [[number theory]], '''Bézout's Lemma''', also called '''Bézout's Identity''', states that for any integers <math>a</math> and <math>b</math> with greatest common denominator <math>d</math>, there exist integers <math>x</math> and <math>y</math> such that <math>ax + by  = d</math>. Furthermore, the integers of the form <math>ax + by</math> are exactly the multiples of <math>d</math>. 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 <math>a</math> and <math>b</math> be <math>15</math> and <math>6</math> respectively. Note that <math>\gcd (a, b) = 3</math>, The Lemma thus states that there exist integers <math>x</math> and <math>y</math> such that <math>15x + 6y = 3</math>. A solution <math>(x, y)</math> to this equation is <math>(1, -2)</math>.
+
To see an example of Bézout's Lemma, let <math>a</math> and <math>b</math> be <math>15</math> and <math>6</math> respectively. Note that <math>\gcd (a, b) = 3</math>, The Lemma thus states that there exist integers <math>x</math> and <math>y</math> such that <math>15x + 6y = 3</math>. A solution <math>(x, y)</math> of this equation is <math>(1, -2)</math>.
 +
 
 +
== Proofs of Bézout's Lemma ==
 +
=== Proof 1 ===
 +
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_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).
 
(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).

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