Difference between revisions of "Bézout's Lemma"
Etmetalakret (talk | contribs) (WIP) |
Etmetalakret (talk | contribs) |
||
(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 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 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).