Difference between revisions of "Bezout's Lemma"
m (correct category) |
|||
Line 11: | Line 11: | ||
==See also== | ==See also== | ||
− | [[Category:Number | + | [[Category:Number theory]] |
{{stub}} | {{stub}} |
Revision as of 18:31, 4 September 2008
Bezout's Lemma states that if two integers and
satisfy
, then there exist integers
and
such that
. In other words, there exists a linear combination of
and
equal to
.
Proof
Since ,
. So
is the first time that
, and it is there that the modular residues begin repeating. Now if for all integers
, we have that
, then one of those
integers must be 1 from the Pigeonhole Principle. Assume for contradiction that
. Thus it repeats, and one of
or
must be
, which is opposite of what we had. Thus there exists an
such that
, and the same proof holds for
.
Since is equivalent to 1 mod x and mod y, and
,
. Lets say that
for some integer
. We can subtract
from
and plug that in to get
.
Thus there does exist integers and
such that
.
See also
This article is a stub. Help us out by expanding it.