Bezout's Lemma
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.