|
|
| (11 intermediate revisions by 6 users not shown) |
| Line 1: |
Line 1: |
| − | '''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>.
| + | #REDIRECT[[Bézout's Identity]] |
| − | | |
| − | 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>.
| |
| − | | |
| − | In particular, if <math>x</math> and <math>y</math> are [[relatively prime]] then there are integers <math>\alpha</math> and <math>\beta</math> for which <math>x\alpha+y\beta=1</math>.
| |
| − | | |
| − | ==Proof==
| |
| − | Let <math>x = gx_1</math>, <math>y = gy_1</math>, and notice that <math>\gcd(x_1,y_1) = 1</math>.
| |
| − | | |
| − | Since <math>\gcd(x_1,y_1)=1</math>, <math>\text{lcm}(x_1,y_1)=x_1y_1</math>. So <math>\alpha=y_1</math> is smallest positive <math>\alpha</math> for which <math>x\alpha\equiv 0\pmod{y}</math>. Now if for all integers <math>0\le a,b<y_1</math>, we have that <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then one of those <math>y_1</math> integers must be 1 from the [[Pigeonhole Principle]]. Assume for contradiction that <math>x_1a\equiv x_1b\pmod{y_1}</math>, and WLOG let <math>b>a</math>. Then, <math>x_1(b-a)\equiv 0\pmod y_1</math>, and so as we saw above this means <math>b-a\ge y_1</math> but this is impossible since <math>0\le a,b<y_1</math>. Thus there exists an <math>\alpha</math> such that <math>x_1\alpha\equiv 1\pmod{y_1}</math>.
| |
| − | | |
| − | Therefore <math>y_1|(x_1\alpha-1)</math>, and so there exists an integer <math>\beta</math> such that <math>x_1\alpha - 1 = y_1\beta</math>, and so <math>x_1\alpha + y_1\beta = 1</math>. Now multiplying through by <math>g</math> gives, <math>gx_1\alpha + gy_1\alpha = g</math>, or <math>x\alpha+y\beta = g</math>.
| |
| − | | |
| − | Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>.
| |
| − | | |
| − | 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==
| |
| − | [[Category:Number theory]]
| |
| − | [[Category:Abstract algebra]]
| |
| − | [[Category:Ring theory]]
| |
| − | {{stub}}
| |
