# Difference between revisions of "Bezout's Lemma"

(Generalized statement/proof to hold for any nonzero integers) |
(Added proof that g minimal) |
||

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

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

Line 11: | Line 13: | ||

Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <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. | ||

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

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

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

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

## See also

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