# Bezout Identities

## Linear Combinations

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

$$
ax+by
$$

where

$$
x,y\in\mathbb{Z}
$$

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

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

$$
2a-b=2\cdot18-30=6
$$

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

$$
ax+by.
$$

Indeed, if

$$
a=dm,
\qquad
b=dn,
$$

then

$$
ax+by=dmx+dny=d(mx+ny).
$$

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

$$
\gcd(a,b)=ax+by.
$$

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

For example,

$$
\gcd(18,30)=6.
$$

One representation is

$$
6=2\cdot18-1\cdot30.
$$

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

$$
\gcd(a,n)=1,
$$

then Bezout's identity gives

$$
ax+ny=1.
$$

Reducing modulo $n$, this becomes

$$
ax\equiv1\pmod n.
$$

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

## Proof Using the Euclidean Algorithm

The extended Euclidean algorithm proves Bezout's identity directly.

Consider

$$
a=1071,
\qquad
b=462.
$$

The Euclidean algorithm gives

$$
1071=462\cdot2+147,
$$

$$
462=147\cdot3+21,
$$

$$
147=21\cdot7+0.
$$

The gcd is the last nonzero remainder:

$$
\gcd(1071,462)=21.
$$

Now rewrite the remainders backward.

From

$$
462=147\cdot3+21,
$$

we get

$$
21=462-147\cdot3.
$$

From

$$
1071=462\cdot2+147,
$$

we get

$$
147=1071-462\cdot2.
$$

Substituting,

$$
21=462-3(1071-462\cdot2).
$$

Therefore

$$
21=-3\cdot1071+7\cdot462.
$$

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

$$
S=\{ax+by:x,y\in\mathbb{Z},\ ax+by>0\}.
$$

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

$$
d=ax_0+by_0
$$

for some integers $x_0,y_0$.

One can show that

$$
d\mid a
$$

and

$$
d\mid b.
$$

Indeed, divide $a$ by $d$:

$$
a=dq+r,
\qquad
0\le r<d.
$$

Since

$$
d=ax_0+by_0,
$$

we have

$$
r=a-dq
=a-q(ax_0+by_0)
=a(1-qx_0)+b(-qy_0).
$$

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

$$
r=0.
$$

Therefore

$$
d\mid a.
$$

The same argument shows that

$$
d\mid b.
$$

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:

$$
d=\gcd(a,b).
$$

Hence

$$
\gcd(a,b)=ax_0+by_0.
$$

## Non-Uniqueness of Bezout Coefficients

Bezout coefficients are generally not unique.

For example,

$$
6=2\cdot18-1\cdot30.
$$

But also

$$
6=7\cdot18-4\cdot30.
$$

Both identities are valid.

In general, if

$$
d=\gcd(a,b)
$$

and

$$
d=ax_0+by_0,
$$

then all solutions to

$$
ax+by=d
$$

are given by

$$
x=x_0+\frac{b}{d}t,
$$

$$
y=y_0-\frac{a}{d}t,
$$

where

$$
t\in\mathbb{Z}.
$$

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

$$
ax+by=1.
$$

Indeed, if

$$
\gcd(a,b)=1,
$$

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

Conversely, if

$$
ax+by=1,
$$

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.