Difference between revisions of "Bezout's Lemma"
(Generalization for PIDs)
m (Added categories)
|Line 34:||Line 34:|
Revision as of 01:03, 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 .
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.
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.
This article is a stub. Help us out by.