Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Bezout's Lemma"

m (correct category)
(Generalized statement/proof to hold for any nonzero integers)
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>. In other words, there exists a linear combination of <math>x</math> and <math>y</math> equal to <math>1</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>.
 +
 
 +
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>.
  
 
==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>.
+
Let <math>x = gx_1</math>, <math>y = gy_1</math>, and notice that <math>\gcd(x_1,y_1) = 1</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
+
Since <math>\gcd(x_1,y_1)=1</math>, <math>\text{lcm}(x_1,y_1)=x_1y_1</math>. So <math>\alpha=y_1</math> is smallest positive <math>\alpha</math> for which <math>x\alpha\equiv 0\pmod{y}</math>. Now if for all integers <math>0\le a,b<y_1</math>, we have that <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then one of those <math>y_1</math> integers must be 1 from the [[Pigeonhole Principle]]. Assume for contradiction that <math>x_1a\equiv x_1b\pmod{y_1}</math>, and WLOG let <math>b>a</math>. Then, <math>x_1(b-a)\equiv 0\pmod y_1</math>, and so as we saw above this means <math>b-a\ge y_1</math> but this is impossible since <math>0\le a,b<y_1</math>. Thus there exists an <math>\alpha</math> such that <math>x_1\alpha\equiv 1\pmod{y_1}</math>.
  
−
<math>x(\alpha-y\gamma)+y\beta=xy\gamma+1-xy\gamma=1</math>.
+
Therefore <math>y_1|(x_1\alpha-1)</math>, and so there exists an integer <math>\beta</math> such that <math>x_1\alpha - 1 = y_1\beta</math>, and so <math>x_1\alpha + y_1\beta = 1</math>. Now multiplying through by <math>g</math> gives, <math>gx_1\alpha + gy_1\alpha = g</math>, or <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=1</math>.
+
Thus there does exist integers <math>\alpha</math> and <math>\beta</math> such that <math>x\alpha+y\beta=g</math>.
  
 
==See also==
 
==See also==
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 
{{stub}}
 
{{stub}}

Revision as of 01:33, 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$.

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$.

See also

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Bezout%27s_Lemma&oldid=30908"