Bezout Identities

Linear Combinations

Let $a$ and $b$ be integers. An integer of the form

where

is called an integer linear combination of $a$ and $b$.

For example, if $a=18$ and $b=30$, then

is a linear combination of $18$ and $30$.

Linear combinations are important because divisibility behaves well under addition and subtraction. If an integer $d$ divides both $a$ and $b$, then $d$ divides every linear combination

Indeed, if

then

Thus every common divisor of $a$ and $b$ divides every integer linear combination of $a$ and $b$.

Statement of Bezout’s Identity

Bezout’s identity states that if $a$ and $b$ are integers, not both zero, then there exist integers $x$ and $y$ such that

The integers $x$ and $y$ are called Bezout coefficients.

For example,

One representation is

Thus $x=2$ and $y=-1$ are Bezout coefficients for $18$ and $30$.

Why the Identity Matters

Bezout’s identity gives a constructive meaning to the greatest common divisor.

The gcd is not merely the largest positive integer dividing both $a$ and $b$. It is also the smallest positive integer that can be written as a linear combination of $a$ and $b$.

This second description is often more useful. It connects common divisors, linear equations, congruences, and modular inverses.

For example, if

then Bezout’s identity gives

Reducing modulo $n$, this becomes

Hence $x$ is an inverse of $a$ modulo $n$.

Proof Using the Euclidean Algorithm

The extended Euclidean algorithm proves Bezout’s identity directly.

Consider

The Euclidean algorithm gives

The gcd is the last nonzero remainder:

Now rewrite the remainders backward.

From

we get

From

we get

Substituting,

Therefore

This is a Bezout identity.

The Smallest Positive Linear Combination

There is another useful proof of Bezout’s identity using the well-ordering principle.

Let

This set is nonempty because at least one of $a$ or $b$ is nonzero. By the well-ordering principle, $S$ has a least element. Call it $d$. Then

for some integers $x_0,y_0$.

One can show that

and

Indeed, divide $a$ by $d$:

Since

we have

Thus $r$ is also a linear combination of $a$ and $b$. If $r>0$, this contradicts the minimality of $d$. Hence

Therefore

The same argument shows that

Thus $d$ is a common divisor of $a$ and $b$.

Since every common divisor of $a$ and $b$ divides every linear combination, every common divisor divides $d$. Therefore $d$ is the greatest common divisor:

Hence

Non-Uniqueness of Bezout Coefficients

Bezout coefficients are generally not unique.

For example,

But also

Both identities are valid.

In general, if

and

then all solutions to

are given by

where

Thus Bezout representations form an infinite family.

Coprimality Criterion

Bezout’s identity gives a powerful criterion for coprimality.

Two integers $a$ and $b$ are coprime if and only if there exist integers $x$ and $y$ such that

Indeed, if

Bezout’s identity gives such $x$ and $y$.

Conversely, if

then any common divisor of $a$ and $b$ must divide $1$. Hence the greatest common divisor is $1$.

Role in Number Theory

Bezout identities are among the most useful tools in elementary number theory. They convert a divisibility statement into an explicit equation.

They are used to prove Euclid’s lemma, solve linear Diophantine equations, find modular inverses, prove the Chinese remainder theorem, and analyze coprime factorizations.

The central idea is that the greatest common divisor is the arithmetic content common to $a$ and $b$, and Bezout’s identity shows that this content can be recovered from $a$ and $b$ by integer linear combination.