Difference between revisions of "Bézout's Identity"
Etmetalakret (talk | contribs) (Created page with "'''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</...") |
Etmetalakret (talk | contribs) m |
||
Line 1: | Line 1: | ||
− | ''' | + | '''Bézout's Identity''' states that if <math>x</math> and <math>y</math> are nonzero [[Integer|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>. | 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>. | ||
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 | + | ==Generalization/Extension of Bézout's Identity== |
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 | 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. | <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. |
Revision as of 15:50, 6 September 2023
Bézout's Identity 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
.
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 Bézout's Identity
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