Difference between revisions of "Bezout's Lemma"
m (→Proof) |
Hashtagmath (talk | contribs) (→See also) |
||
Line 37: | Line 37: | ||
[[Category:Ring theory]] | [[Category:Ring theory]] | ||
{{stub}} | {{stub}} | ||
+ | [[Category:Theorems]] |
Revision as of 11:15, 30 May 2019
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.
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.
Proof
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.
See also
This article is a stub. Help us out by expanding it.