Difference between revisions of "Bezout's Lemma"

Revision as of 09:03, 16 August 2008

Bezout's Lemma states that if two integers $x$ and $y$ satisfy $gcd(x,y)=1$ , then there exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=1$ . In other words, there exists a linear combination of $x$ and $y$ equal to $1$ .

Proof

Since $gcd(x,y)=1$ , $lcm(x,y)=xy$ . So $\alpha=y$ is the first time that $x\alpha\equiv 0\bmod{y}$ , and it is there that the modular residues begin repeating. Now if for all integers $0<a,b<n$ , we have that $xa\neq xb\bmod{y}$ , then one of those $n-1$ integers must be 1 from the Pigeonhole Principle. Assume for contradiction that $xa\equiv xb\bmod{y}$ . Thus it repeats, and one of $a$ or $b$ must be $\geq n$ , which is opposite of what we had. Thus there exists an $\alpha$ such that $x\alpha\equiv 1\bmod{y}$ , and the same proof holds for $\beta$ .

Since $x\alpha +y\beta$ is equivalent to 1 mod x and mod y, and $gcd(x,y)=1$ , $x\alpha +y\beta \equiv 1\bmod{xy}$ . Lets say that $x\alpha+y\beta=xy\gamma +1$ for some integer $\gamma$ . We can subtract $y\gamma$ from $\alpha$ and plug that in to get

$x(\alpha-y\gamma)+y\beta=xy\gamma+1-xy\gamma=1$ .

Thus there does exist integers $\alpha$ and $\beta$ such that $x\alpha+y\beta=1$ .

@@ 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==
-{{incomplete|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==
 [[Category:Number Theory]]
 {{stub}}

Page

Toolbox

Search

Difference between revisions of "Bezout's Lemma"

Revision as of 09:03, 16 August 2008

Proof

See also