Difference between revisions of "Bezout's Lemma"
Hashtagmath (talk | contribs) (→See also) |
Qwertysri987 (talk | contribs) m (→Generalization/Extension of Bezout's Lemma) |
||
(5 intermediate revisions by 2 users not shown) | |||
Line 8: | Line 8: | ||
Let <math>x = gx_1</math>, <math>y = gy_1</math>, and notice that <math>\gcd(x_1,y_1) = 1</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>\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> | + | 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_1\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>. |
− | 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\ | + | 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\beta = 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=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. | 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 positive 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, by the [[Well Ordering Principle|Well Ordering Principle]], 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</math> and <math>n \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 45: | ||
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 21:53, 8 May 2020
Bezout's Lemma states that if and are nonzero integers and , then there exist integers and such that . In other words, there exists a linear combination of and equal to .
Furthermore, is the smallest positive integer that can be expressed in this form, i.e. .
In particular, if and are relatively prime then there are integers and for which .
Contents
Proof
Let , , and notice that .
Since , . So is smallest positive for which . Now if for all integers , we have that , then one of those integers must be 1 from the Pigeonhole Principle. Assume for contradiction that , and WLOG let . Then, , and so as we saw above this means but this is impossible since . Thus there exists an such that .
Therefore , and so there exists an integer such that , and so . Now multiplying through by gives, , or .
Thus there does exist integers and such that .
Now to prove is minimum, consider any positive integer . As we get , and as and are both positive integers this gives . So is indeed the minimum.
Generalization/Extension of Bezout's Lemma
Let be positive integers. Then there exists integers such that Also, is the least positive integer satisfying this property.
Proof
Consider the set . Obviously, . Thus, because all the elements of are positive, by the Well Ordering Principle, there exists a minimal element . So
if and then But by the Division Algorithm:
But so this would imply that which contradicts the assumption that is the minimal element in . Thus, hence, . But this would imply that for because . Now, because for we have that . But then we also have that . Thus, we have that
~qwertysri987
Generalization to Principal Ideal Domains
Bezout's Lemma can be generalized to principal ideal domains.
Let be a principal ideal domain, and consider any . Let . Then there exist elements for which . Furthermore, is the minimal such element (under divisibility), i.e. if then .
Note that this statement is indeed a generalization of the previous statement, as the ring of integers, is a principal ideal domain.
Proof
Consider the ideal . As is a principal ideal domain, must be principle, that is it must be generated by a single element, say . Now from the definition of , there must exist such that . We now claim that .
First we prove the following simple fact: if , then . To see this, note that if , then there must be some such that . But now by definition we have .
Now from this, as , we get that . Furthermore, consider any with . We clearly have that . So indeed .
Now we shall prove minimality. Let . Then as , we have , as desired.
See also
This article is a stub. Help us out by expanding it.