[Introduction to Number Theory Series Part 6] How Does Bézout's Identity Express the GCD as a Formula?

The gcd is more than “the biggest common divisor.” It can also be written as a combination of the two integers themselves. That statement is Bézout's identity.

What this post covers

• The statement of Bézout's identity
• Why the gcd can be written in the form ax+by
• Concrete coefficient examples
• How this leads into linear Diophantine equations

Key terms

• Bézout's identity: the theorem that expresses gcd(a,b) in the form ax+by
• linear Diophantine equation: an equation of the form ax+by=c with integer solutions
• greatest common divisor: the largest positive common divisor of two integers
• coprime: having gcd 1

The statement

If a and b are not both 0, then there exist integers x and y such that

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

This is Bézout's identity.

Why is this important?

It connects three questions at once:

1. What is the gcd?
2. Can the gcd be built from the two integers themselves?
3. When does an equation like ax+by=c have integer solutions?

So gcd computations and integer-solution problems are not separate topics. The gcd is the bridge between them.

Example 1: 12 and 18

We know

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

And

$$18-12=6,$$

so

$$12(-1)+18(1)=6.$$

This already gives one valid pair of coefficients.

Example 2: 30 and 18

First compute the gcd:

$$30=18\times 1+12$$ $$18=12\times 1+6$$ $$12=6\times 2+0$$

So gcd(30,18)=6. Now go backward:

$$6=18-12$$

and

$$12=30-18.$$

Substituting gives

$$6=18-(30-18)=2\cdot 18-30.$$

So

$$30(-1)+18(2)=6.$$

What happens if the numbers are coprime?

If a and b are coprime, then gcd(a,b)=1, so Bézout's identity becomes

$$ax+by=1.$$

That fact later becomes central in modular inverses.

Common mistakes

1. Thinking the coefficients are unique

They are usually not unique. There are often many valid pairs of integers that produce the same gcd.

2. Thinking every integer can be written as ax+by

Not every integer appears. The reachable values are exactly the multiples of gcd(a,b).

3. Separating Bézout's identity from the Euclidean algorithm

The Euclidean algorithm finds the gcd, and tracing the steps backward finds coefficients.

Wrap-up

Bézout's identity says the gcd can be written as ax+by. That turns the gcd from a divisor-listing idea into a structural equation.

Next we use that directly to study when ax+by=c has integer solutions.