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"

(→‎Proof)
Line 15: Line 15:
  
 
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.
 
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.
 +
 +
==Generalization/Extension of Bezout's Lemma==
 +
Let <math>a_1, a_2,..., a_m</math> be non-zero integers. Then there exists integers <math>x_1, x_2, ..., x_m</math> such that
 +
<cmath>\sum_{i=1}^{m} a_ix_i = \gcd(a_1, a_2, ..., a_m)</cmath> Also, <math>\gcd(a_1, a_2, ..., a_m)</math> is the least positive integer satisfying this property.
 +
 +
===Proof===
 +
Consider the set <math>P = \{n \in \mathbb{Z}^{+}|n= \sum_{i=1}^{m} a_iu_i: u_1, \dots, u_m \in \mathbb{Z}\}</math>. Obviously, <math>P \neq \emptyset</math>. Thus, because all the elements of <math>P</math> are positive, there exists a minimal element <math>d \in P</math>. So
 +
 +
<cmath>d=a_1x_1 +a_2x_2 + \dots +a_mx_m</cmath>
 +
if <math>n >d \in S</math> then <cmath>n=a_1u_1 +a_2u_2 + \dots +a_mu_m</cmath> But by the [[Division Algorithm|Division Algorithm]]:
 +
<cmath>n=qd +r \Longrightarrow r=n-qd</cmath>
 +
<cmath>= \sum_{i=1}^m a_i(u_i-qx_i)</cmath>
 +
<cmath> \Longrightarrow r\in P</cmath>
 +
But <math>0 \le r<d</math> so this would imply that <math>r \in P</math> which contradicts the assumption that <math>d</math> is the minimal element in <math>P</math>. Thus, <math>r=0</math> hence, <math>d|n</math>. But this would imply that <math>d|a_i</math> for <math>i \in \{1, 2,\dots,m\}</math> because <math>a_i = a_i \cdot1 + \sum_{k=1; k \neq i}^{m}(a_k\cdot0) \Longrightarrow \{a_1, a_2, \dots, a_m \} \subset P</math>.
 +
Now, because <math>d|a_i</math> for <math>i \in \{1, 2,\dots,m\}</math> we have that <math>d|\gcd(a_1, a_2,\dots, a_m)|a_i</math>. But then we also have that <math>\gcd(a_1, a_2,\dots, a_m)|\sum_{i=1}^m a_iu_i =d</math>. Thus, we have that <math>\boxed{d=\gcd(a_1, a_2,\dots, a_m)}</math> <math>\Box</math>
 +
 +
~qwertysri987
 +
  
 
==Generalization to Principal Ideal Domains==
 
==Generalization to Principal Ideal Domains==
Line 23: Line 41:
 
Note that this statement is indeed a generalization of the previous statement, as the [[ring]] of integers, <math>\mathbb Z</math> is a principal ideal domain.
 
Note that this statement is indeed a generalization of the previous statement, as the [[ring]] of integers, <math>\mathbb Z</math> is a principal ideal domain.
  
−
==Proof==
+
===Proof===
 
Consider the [[ideal]] <math>I = (x,y) = \{xr_1+yr_2|r_1,r_2\in R\}</math>. As <math>R</math> is a principal ideal domain, <math>I</math> must be principle, that is it must be generated by a single element, say <math>I = (g)</math>. Now from the definition of <math>I</math>, there must exist <math>r_1,r_2\in R</math> such that <math>g = xr_1+yr_2</math>. We now claim that <math>g = \gcd(x,y)</math>.
 
Consider the [[ideal]] <math>I = (x,y) = \{xr_1+yr_2|r_1,r_2\in R\}</math>. As <math>R</math> is a principal ideal domain, <math>I</math> must be principle, that is it must be generated by a single element, say <math>I = (g)</math>. Now from the definition of <math>I</math>, there must exist <math>r_1,r_2\in R</math> such that <math>g = xr_1+yr_2</math>. We now claim that <math>g = \gcd(x,y)</math>.
  

Revision as of 14:08, 21 April 2020

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_1\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\beta = 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.

Generalization/Extension of Bezout's Lemma

Let $a_1, a_2,..., a_m$ be non-zero integers. Then there exists integers $x_1, x_2, ..., x_m$ such that \[\sum_{i=1}^{m} a_ix_i = \gcd(a_1, a_2, ..., a_m)\] Also, $\gcd(a_1, a_2, ..., a_m)$ is the least positive integer satisfying this property.

Proof

Consider the set $P = \{n \in \mathbb{Z}^{+}|n= \sum_{i=1}^{m} a_iu_i: u_1, \dots, u_m \in \mathbb{Z}\}$. Obviously, $P \neq \emptyset$. Thus, because all the elements of $P$ are positive, there exists a minimal element $d \in P$. So

\[d=a_1x_1 +a_2x_2 + \dots +a_mx_m\] if $n >d \in S$ then \[n=a_1u_1 +a_2u_2 + \dots +a_mu_m\] But by the Division Algorithm: \[n=qd +r \Longrightarrow r=n-qd\] \[= \sum_{i=1}^m a_i(u_i-qx_i)\] \[\Longrightarrow r\in P\] But $0 \le r<d$ so this would imply that $r \in P$ which contradicts the assumption that $d$ is the minimal element in $P$. Thus, $r=0$ hence, $d|n$. But this would imply that $d|a_i$ for $i \in \{1, 2,\dots,m\}$ because $a_i = a_i \cdot1 + \sum_{k=1; k \neq i}^{m}(a_k\cdot0) \Longrightarrow \{a_1, a_2, \dots, a_m \} \subset P$. Now, because $d|a_i$ for $i \in \{1, 2,\dots,m\}$ we have that $d|\gcd(a_1, a_2,\dots, a_m)|a_i$. But then we also have that $\gcd(a_1, a_2,\dots, a_m)|\sum_{i=1}^m a_iu_i =d$. Thus, we have that $\boxed{d=\gcd(a_1, a_2,\dots, a_m)}$ $\Box$

~qwertysri987


Generalization to Principal Ideal Domains

Bezout's Lemma can be generalized to principal ideal domains.

Let $R$ be a principal ideal domain, and consider any $x,y\in R$. Let $g = \gcd(x,y)$. Then there exist elements $r_1,r_2\in R$ for which $xr_1+yr_2 = g$. Furthermore, $g$ is the minimal such element (under divisibility), i.e. if $g' = xr_1'+yr_2'$ then $g|g'$.

Note that this statement is indeed a generalization of the previous statement, as the ring of integers, $\mathbb Z$ is a principal ideal domain.

Proof

Consider the ideal $I = (x,y) = \{xr_1+yr_2|r_1,r_2\in R\}$. As $R$ is a principal ideal domain, $I$ must be principle, that is it must be generated by a single element, say $I = (g)$. Now from the definition of $I$, there must exist $r_1,r_2\in R$ such that $g = xr_1+yr_2$. We now claim that $g = \gcd(x,y)$.

First we prove the following simple fact: if $z\in I$, then $g|z$. To see this, note that if $z\in I = (g)$, then there must be some $r\in R$ such that $z = rg$. But now by definition we have $g|z$.

Now from this, as $x,y\in I$, we get that $g|x,y$. Furthermore, consider any $s\in R$ with $s|x,y$. We clearly have that $s|xr_1+yr_2 = g$. So indeed $g = \gcd(x,y)$.

Now we shall prove minimality. Let $g' = xr_1'+yr_2'$. Then as $g|x,y$, we have $g|xr_1'+yr_2' = g'$, as desired.

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=121418"