Difference between revisions of "Bezout's Lemma"

(Generalized statement/proof to hold for any nonzero integers)
(Added proof that g minimal)
Line 1: Line 1:
 
'''Bezout's Lemma''' states that if <math>x</math> and <math>y</math> are nonzero integers and <math>g = \gcd(x,y)</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>g</math>.
 
'''Bezout's Lemma''' states that if <math>x</math> and <math>y</math> are nonzero integers and <math>g = \gcd(x,y)</math>, then there exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>g</math>.
 +
 +
Furthermore, <math>g</math> is the smallest positive integer that can be expressed in this form, i.e. <math>g = \min\{x\alpha+y\beta|\alpha,\beta\in\mathbb Z, x\alpha+y\beta > 0\}</math>.
  
 
In particular, if <math>x</math> and <math>y</math> are [[relatively prime]] then there are integers <math>\alpha</math> and <math>\beta</math> for which <math>x\alpha+y\beta=1</math>.
 
In particular, if <math>x</math> and <math>y</math> are [[relatively prime]] then there are integers <math>\alpha</math> and <math>\beta</math> for which <math>x\alpha+y\beta=1</math>.
Line 11: Line 13:
  
 
Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>.
 
Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>.
 +
 +
Now to prove <math>g</math> is minimum, consider any positive integer <math>g' = x\alpha'+y\beta'</math>. As <math>g|x,y</math> we get <math>g|x\alpha'+y\beta' = g'</math>, and as <math>g</math> and <math>g'</math> are both positive integers this gives <math>g\le g'</math>. So <math>g</math> is indeed the minimum.
  
 
==See also==
 
==See also==
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 
{{stub}}
 
{{stub}}

Revision as of 00:39, 21 March 2009

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

Furthermore, $g$ is the smallest positive integer that can be expressed in this form, i.e. $g = \min\{x\alpha+y\beta|\alpha,\beta\in\mathbb Z, x\alpha+y\beta > 0\}$.

In particular, if $x$ and $y$ are relatively prime then there are integers $\alpha$ and $\beta$ for which $x\alpha+y\beta=1$.

Proof

Let $x = gx_1$, $y = gy_1$, and notice that $\gcd(x_1,y_1) = 1$.

Since $\gcd(x_1,y_1)=1$, $\text{lcm}(x_1,y_1)=x_1y_1$. So $\alpha=y_1$ is smallest positive $\alpha$ for which $x\alpha\equiv 0\pmod{y}$. Now if for all integers $0\le a,b<y_1$, we have that $x_1a\not\equiv x_1b\pmod{y_1}$, then one of those $y_1$ integers must be 1 from the Pigeonhole Principle. Assume for contradiction that $x_1a\equiv x_1b\pmod{y_1}$, and WLOG let $b>a$. Then, $x_1(b-a)\equiv 0\pmod y_1$, and so as we saw above this means $b-a\ge y_1$ but this is impossible since $0\le a,b<y_1$. Thus there exists an $\alpha$ such that $x_1\alpha\equiv 1\pmod{y_1}$.

Therefore $y_1|(x_1\alpha-1)$, and so there exists an integer $\beta$ such that $x_1\alpha - 1 = y_1\beta$, and so $x_1\alpha + y_1\beta = 1$. Now multiplying through by $g$ gives, $gx_1\alpha + gy_1\alpha = g$, or $x\alpha+y\beta = g$.

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

Now to prove $g$ is minimum, consider any positive integer $g' = x\alpha'+y\beta'$. As $g|x,y$ we get $g|x\alpha'+y\beta' = g'$, and as $g$ and $g'$ are both positive integers this gives $g\le g'$. So $g$ is indeed the minimum.

See also

This article is a stub. Help us out by expanding it.

Invalid username
Login to AoPS