Difference between revisions of "Bézout's Identity"
(→Proof) |
(→Proof) |
||
Line 7: | Line 7: | ||
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>x_1\alpha\equiv 0\pmod{y_1}</math>. Now if for all distinct <math>a,b \in\mathbb{Z}</math> satisfying <math>0\le a,b<y_1</math> we have <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then, by the [[Pigeonhole Principle]], we can express every residue of <math>y_1</math> as a multiple of <math>x_1</math>. In particular, there is some <math>\alpha</math> for which <math>x_1\alpha\equiv 1\pmod{y_1}</math>. 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>. | + | 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_1}</math>. Now if for all distinct <math>a,b \in\mathbb{Z}</math> satisfying <math>0\le a,b<y_1</math> we have <math>x_1a\not\equiv x_1b\pmod{y_1}</math>, then, by the [[Pigeonhole Principle]], we can express every residue of <math>y_1</math> as a multiple of <math>x_1</math>. In particular, there is some positive <math>\alpha<y_1</math> for which <math>x_1\alpha\equiv 1\pmod{y_1}</math>. 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\beta = g</math>, or <math>x\alpha+y\beta = g</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\beta = g</math>, or <math>x\alpha+y\beta = g</math>. |
Latest revision as of 02:41, 1 September 2024
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 distinct
satisfying
we have
, then, by the Pigeonhole Principle, we can express every residue of
as a multiple of
. In particular, there is some positive
for which
. 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