# Difference between revisions of "Bezout's Lemma"

m (correct category) |
(Generalized statement/proof to hold for any nonzero integers) |
||

Line 1: | Line 1: | ||

− | '''Bezout's Lemma''' states that if | + | '''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>. |

+ | |||

+ | 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== | ==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> | + | 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>. |

− | <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= | + | Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>. |

==See also== | ==See also== | ||

[[Category:Number theory]] | [[Category:Number theory]] | ||

{{stub}} | {{stub}} |

## Revision as of 00:33, 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 .

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 .

## See also

*This article is a stub. Help us out by expanding it.*