Difference between revisions of "Bezout's Lemma"
Qwertysri987 (talk | contribs) |
Qwertysri987 (talk | contribs) (→Proof) |
||
Line 21: | Line 21: | ||
===Proof=== | ===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 | + | 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> | <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]]: | + | |
+ | 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>n=qd +r \Longrightarrow r=n-qd</cmath> | ||
<cmath>= \sum_{i=1}^m a_i(u_i-qx_i)</cmath> | <cmath>= \sum_{i=1}^m a_i(u_i-qx_i)</cmath> | ||
<cmath> \Longrightarrow r\in P</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>. | 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> | 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 | ~qwertysri987 | ||
− | |||
==Generalization to Principal Ideal Domains== | ==Generalization to Principal Ideal Domains== |
Revision as of 20:49, 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
[hide]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 non-zero 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.