Bézout's Identity
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