Difference between revisions of "Bezout's Lemma"
(New page: '''Bezout's Lemma''' states that if two integers <math>x</math> and <math>y</math> satisfy <math>gcd(x,y)=1</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> suc...) |
|||
| Line 1: | Line 1: | ||
| − | '''Bezout's Lemma''' states that if two integers <math>x</math> and <math>y</math> satisfy <math>gcd(x,y)=1</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=1</math>. | + | '''Bezout's Lemma''' states that if two integers <math>x</math> and <math>y</math> satisfy <math>gcd(x,y)=1</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=1</math>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>1</math>. |
==Proof== | ==Proof== | ||
| − | {{ | + | Since <math>gcd(x,y)=1</math>, <math>lcm(x,y)=xy</math>. So <math>\alpha=y</math> is the first time that <math>x\alpha\equiv 0\bmod{y}</math>, and it is there that the modular residues begin repeating. Now if for all integers <math>0<a,b<n</math>, we have that <math>xa\neq xb\bmod{y}</math>, then one of those <math>n-1</math> integers must be 1 from the [[Pigeonhole Principle]]. Assume for contradiction that <math>xa\equiv xb\bmod{y}</math>. Thus it repeats, and one of <math>a</math> or <math>b</math> must be <math>\geq n</math>, which is opposite of what we had. Thus there exists an <math>\alpha</math> such that <math>x\alpha\equiv 1\bmod{y}</math>, and the same proof holds for <math>\beta</math>. |
| + | |||
| + | Since <math>x\alpha +y\beta</math> is equivalent to 1 mod x and mod y, and <math>gcd(x,y)=1</math>, <math>x\alpha +y\beta \equiv 1\bmod{xy}</math>. Lets say that <math>x\alpha+y\beta=xy\gamma +1</math> for some integer <math>\gamma</math>. We can subtract <math>y\gamma</math> from <math>\alpha</math> and plug that in to get | ||
| + | |||
| + | <math>x(\alpha-y\gamma)+y\beta=xy\gamma+1-xy\gamma=1</math>. | ||
| + | |||
| + | Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=1</math>. | ||
==See also== | ==See also== | ||
[[Category:Number Theory]] | [[Category:Number Theory]] | ||
{{stub}} | {{stub}} | ||
Revision as of 10:03, 16 August 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.
