Difference between revisions of "Bezout's Lemma"
(Added proof that g minimal) |
(Generalization for PIDs) |
||
Line 1: | Line 1: | ||
− | '''Bezout's Lemma''' states that if <math>x</math> and <math>y</math> are nonzero integers and <math>g = \gcd(x,y)</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>g</math>. | + | '''Bezout's Lemma''' states that if <math>x</math> and <math>y</math> are nonzero [[Integer|integers]] and <math>g = \gcd(x,y)</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>g</math>. |
Furthermore, <math>g</math> is the smallest positive integer that can be expressed in this form, i.e. <math>g = \min\{x\alpha+y\beta|\alpha,\beta\in\mathbb Z, x\alpha+y\beta > 0\}</math>. | Furthermore, <math>g</math> is the smallest positive integer that can be expressed in this form, i.e. <math>g = \min\{x\alpha+y\beta|\alpha,\beta\in\mathbb Z, x\alpha+y\beta > 0\}</math>. | ||
Line 15: | Line 15: | ||
Now to prove <math>g</math> is minimum, consider any positive integer <math>g' = x\alpha'+y\beta'</math>. As <math>g|x,y</math> we get <math>g|x\alpha'+y\beta' = g'</math>, and as <math>g</math> and <math>g'</math> are both positive integers this gives <math>g\le g'</math>. So <math>g</math> is indeed the minimum. | Now to prove <math>g</math> is minimum, consider any positive integer <math>g' = x\alpha'+y\beta'</math>. As <math>g|x,y</math> we get <math>g|x\alpha'+y\beta' = g'</math>, and as <math>g</math> and <math>g'</math> are both positive integers this gives <math>g\le g'</math>. So <math>g</math> is indeed the minimum. | ||
+ | |||
+ | ==Generalization to Principal Ideal Domains== | ||
+ | Bezout's Lemma can be generalized to [[Principal ideal domain|principal ideal domains]]. | ||
+ | |||
+ | Let <math>R</math> be a principal ideal domain, and consider any <math>x,y\in R</math>. Let <math>g = \gcd(x,y)</math>. Then there exist elements <math>r_1,r_2\in R</math> for which <math>xr_1+yr_2 = g</math>. Furthermore, <math>g</math> is the minimal such element (under divisibility), i.e. if <math>g' = xr_1'+yr_2'</math> then <math>g|g'</math>. | ||
+ | |||
+ | Note that this statement is indeed a generalization of the previous statement, as the [[ring]] of integers, <math>\mathbb Z</math> is a principal ideal domain. | ||
+ | |||
+ | ==Proof== | ||
+ | Consider the [[ideal]] <math>I = (x,y) = \{xr_1+yr_2|r_1,r_2\in R\}</math>. As <math>R</math> is a principal ideal domain, <math>I</math> must be principle, that is it must be generated by a single element, say <math>I = (g)</math>. Now from the definition of <math>I</math>, there must exist <math>r_1,r_2\in R</math> such that <math>g = xr_1+yr_2</math>. We now claim that <math>g = \gcd(x,y)</math>. | ||
+ | |||
+ | First we prove the following simple fact: if <math>z\in I</math>, then <math>g|z</math>. To see this, note that if <math>z\in I = (g)</math>, then there must be some <math>r\in R</math> such that <math>z = rg</math>. But now by definition we have <math>g|z</math>. | ||
+ | |||
+ | Now from this, as <math>x,y\in I</math>, we get that <math>g|x,y</math>. Furthermore, consider any <math>s\in R</math> with <math>s|x,y</math>. We clearly have that <math>s|xr_1+yr_2 = g</math>. So indeed <math>g = \gcd(x,y)</math>. | ||
+ | |||
+ | Now we shall prove minimality. Let <math>g' = xr_1'+yr_2'</math>. Then as <math>g|x,y</math>, we have <math>g|xr_1'+yr_2' = g'</math>, as desired. | ||
==See also== | ==See also== | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
{{stub}} | {{stub}} |
Revision as of 02:01, 21 March 2009
Bezout's Lemma states that if and are nonzero integers and , then there exist integers and such that . In other words, there exists a linear combination of and equal to .
Furthermore, is the smallest positive integer that can be expressed in this form, i.e. .
In particular, if and are relatively prime then there are integers and for which .
Proof
Let , , and notice that .
Since , . So is smallest positive for which . Now if for all integers , we have that , then one of those integers must be 1 from the Pigeonhole Principle. Assume for contradiction that , and WLOG let . Then, , and so as we saw above this means but this is impossible since . Thus there exists an such that .
Therefore , and so there exists an integer such that , and so . Now multiplying through by gives, , or .
Thus there does exist integers and such that .
Now to prove is minimum, consider any positive integer . As we get , and as and are both positive integers this gives . So is indeed the minimum.
Generalization to Principal Ideal Domains
Bezout's Lemma can be generalized to principal ideal domains.
Let be a principal ideal domain, and consider any . Let . Then there exist elements for which . Furthermore, is the minimal such element (under divisibility), i.e. if then .
Note that this statement is indeed a generalization of the previous statement, as the ring of integers, is a principal ideal domain.
Proof
Consider the ideal . As is a principal ideal domain, must be principle, that is it must be generated by a single element, say . Now from the definition of , there must exist such that . We now claim that .
First we prove the following simple fact: if , then . To see this, note that if , then there must be some such that . But now by definition we have .
Now from this, as , we get that . Furthermore, consider any with . We clearly have that . So indeed .
Now we shall prove minimality. Let . Then as , we have , as desired.
See also
This article is a stub. Help us out by expanding it.