Difference between revisions of "Bézout's Lemma"
Etmetalakret (talk | contribs) (WIP) |
Etmetalakret (talk | contribs) |
||
| 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 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 === | ||
| + | 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</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 === | ||
| + | |||
| + | |||
| + | |||
(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). | ||
Revision as of 20:35, 19 February 2023
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: ![\[S = \{ ax + by \textrm{ } | \textrm{ } x, y \in \mathbb{Z}, ax + by > 0\} .\]](http://latex.artofproblemsolving.com/b/5/1/b517a90c3aad37c1753db2b9c68440c056edf2b6.png)
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).
