Bézout’s Identity and the Euclidean Algorithm

Imagine students is trying to divide snacks into equal groups with no leftovers 🍎🍪. Sometimes the numbers do not divide nicely, but there is always a biggest group size that works for both numbers. That idea is the heart of the Euclidean Algorithm, and Bézout’s identity shows something even deeper: the greatest common divisor can be written as a combination of the two numbers.

In this lesson, students will learn to:

explain what Bézout’s identity says,
use the Euclidean Algorithm to find the greatest common divisor $\gcd(a,b)$,
connect the answer to a statement of the form $ax+by=d$,
understand why this works for every pair of integers not both zero,
see how Bézout’s identity helps with solving equations in Number Theory.

What Bézout’s identity says

For any integers $a$ and $b$, not both $0$, there exist integers $x$ and $y$ such that

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

This statement is called Bézout’s identity. The numbers $x$ and $y$ are called Bézout coefficients.

The key idea is simple but powerful: the greatest common divisor is not only a number that divides both $a$ and $b$, but also a number that can be built from them using addition, subtraction, and multiplication by integers.

For example, for $a=12$ and $b=18$, we have $\gcd(12,18)=6$. One way to write $6$ is

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

So $x=-1$ and $y=1$ are Bézout coefficients. This is a concrete example of the identity in action.

Why is this important? Because it links divisibility with linear combinations. In Number Theory, this link is used to test whether equations have integer solutions and to understand more advanced topics like modular arithmetic 🔍.

How the Euclidean Algorithm finds the gcd

The Euclidean Algorithm is a fast method for finding $\gcd(a,b)$. It works by repeatedly dividing and using remainders.

Suppose $a>b>0$. Divide $a$ by $b$:

$a=bq+r, \quad 0\le r<b.$

Then

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

This is because any number that divides both $a$ and $b$ must also divide the remainder $r=a-bq$, and any number that divides both $b$ and $r$ also divides $a=bq+r$. So the common divisors stay the same.

Repeat this process until the remainder is $0$. The last nonzero remainder is the gcd.

Example: find $\gcd(84,30)$.

$84=30\cdot 2+24$
$30=24\cdot 1+6$
$24=6\cdot 4+0$

So $\gcd(84,30)=6$.

The Euclidean Algorithm gives the gcd efficiently, even for large numbers. But Bézout’s identity says more: once the gcd is known, it can be written as a combination of the original numbers.

From the algorithm to Bézout coefficients

The Euclidean Algorithm does not just compute the gcd. By working backward, students can express the gcd as a linear combination of the original numbers. This is called the extended Euclidean Algorithm.

Let’s use the previous example with $84$ and $30$.

From the steps above:

$30=24+6$

$6=30-24.$

Also,

$84=30\cdot 2+24,$

$24=84-30\cdot 2.$

Substitute this into the first expression:

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

Simplify:

$6=30-84+30\cdot 2=30\cdot 3-84.$

So we get

$6=84(-1)+30(3).$

That means one pair of Bézout coefficients is $x=-1$ and $y=3$.

This backward substitution is the practical way to find the coefficients. Each remainder is rewritten in terms of earlier remainders until only the original numbers remain.

Why Bézout’s identity is always true

Bézout’s identity is not just a lucky pattern. It is a theorem. The reason it works comes from the set of all integer linear combinations of $a$ and $b$:

ax+by \quad \text{for integers } x \text{ and } y.

Among all positive values of this form, choose the smallest one and call it $d$. A careful argument shows that $d$ divides both $a$ and $b$.

Here is the main idea:

If $d$ is the smallest positive linear combination of $a$ and $b$,
divide $a$ by $d$ to get $a=dq+r$ with $0\le r<d$,
because $d$ is built from $a$ and $b$, the remainder $r$ is also a linear combination of $a$ and $b$,
if $r>0$, that would contradict the choice of $d$ as the smallest positive one,
so $r=0$, which means $d$ divides $a$.

The same argument shows that $d$ divides $b$. Therefore, $d$ is a common divisor of $a$ and $b$.

Also, every common divisor of $a$ and $b$ divides every linear combination $ax+by$. So every common divisor divides $d$ as well. That means $d$ is actually the greatest common divisor.

So the smallest positive linear combination of $a$ and $b$ is exactly $\gcd(a,b)$. That is Bézout’s identity in action ✨.

Solving equations using Bézout’s identity

Bézout’s identity is especially useful for equations of the form

$ax+by=c,$

where $a$, $b$, and $c$ are integers. A key fact is:

the equation has integer solutions if and only if $\gcd(a,b)$ divides $c$.

Why? If $ax+by=c$, then $c$ is a linear combination of $a$ and $b$. Since $\gcd(a,b)$ divides every such combination, it must divide $c$. So divisibility is necessary.

It is also sufficient. If $d=\gcd(a,b)$ and $d\mid c$, then Bézout’s identity gives integers $x_0$ and $y_0$ such that

$ax_0+by_0=d.$

If $c=kd$, then multiplying by $k$ gives

$a(kx_0)+b(ky_0)=c,$

which is an integer solution.

Example: solve

$12x+18y=30.$

First find $\gcd(12,18)=6$. Since $6\mid 30$, solutions exist.

From earlier, one Bézout form is

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

Multiply by $5$:

$12(-5)+18(5)=30.$

So one solution is $x=-5$ and $y=5$.

This is a very useful method in Number Theory and in real-world problems like balancing quantities, scheduling cycles, and checking compatibility of repeated patterns 📅.

Connection to the broader Euclidean Algorithm topic

Bézout’s identity fits naturally into the Euclidean Algorithm topic because the algorithm does two jobs:

it computes $\gcd(a,b)$,
it provides a path to express that gcd as $ax+by$.

The first job is the basic algorithm. The second job is the extended version, which is built from the same division steps.

This connection matters because many later results depend on it. For example:

if $\gcd(a,b)=1$, then Bézout’s identity gives integers $x$ and $y$ such that $ax+by=1$,
this fact is used to show that $a$ has a multiplicative inverse modulo $b$ when $\gcd(a,b)=1$,
it helps determine whether linear Diophantine equations have integer solutions.

So Bézout’s identity is not a separate idea floating alone. It is one of the main reasons the Euclidean Algorithm is so important.

Worked example with backward substitution

Let’s use a full example to see the process clearly.

Find integers $x$ and $y$ such that

$99x+78y=\gcd(99,78).$

First apply the Euclidean Algorithm:

$99=78\cdot 1+21$

$78=21\cdot 3+15$

$21=15\cdot 1+6$

$15=6\cdot 2+3$

$6=3\cdot 2+0.$

$\gcd(99,78)=3.$

Now work backward:

$3=15-6\cdot 2.$

Since

$6=21-15,$

substitute:

$3=15-2(21-15)=3\cdot 15-2\cdot 21.$

Since

$15=78-21\cdot 3,$

we get

$3=3(78-21\cdot 3)-2\cdot 21=3\cdot 78-11\cdot 21.$

Since

$21=99-78,$

then

$3=3\cdot 78-11(99-78)=14\cdot 78-11\cdot 99.$

Thus one solution is

$x=-11,\quad y=14.$

Check:

$99(-11)+78(14)=-1089+1092=3.$

That confirms the result ✅.

Conclusion

Bézout’s identity says that for integers $a$ and $b$, not both zero, there are integers $x$ and $y$ such that

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

This idea connects directly to the Euclidean Algorithm. The algorithm finds the gcd, and the extended version rewrites that gcd as a linear combination of the original numbers. That connection is useful for proving divisibility facts, solving equations like $ax+by=c$, and building later Number Theory ideas.

For students, the main takeaway is this: the Euclidean Algorithm tells you the size of the greatest common divisor, and Bézout’s identity tells you how to build it from the original numbers. Those two ideas belong together 🤝.

Study Notes

Bézout’s identity states that for integers $a$ and $b$, not both $0$, there exist integers $x$ and $y$ such that $ax+by=\gcd(a,b)$.
The integers $x$ and $y$ are called Bézout coefficients.
The Euclidean Algorithm finds $\gcd(a,b)$ by repeated division with remainder.
The extended Euclidean Algorithm works backward from the remainder steps to find Bézout coefficients.
If $\gcd(a,b)=d$, then the equation $ax+by=c$ has integer solutions exactly when $d\mid c$.
A common divisor of $a$ and $b$ divides every linear combination $ax+by$.
Bézout’s identity is a foundation for modular inverses and linear Diophantine equations.
The identity fits into the Euclidean Algorithm topic because it explains both the gcd and how to express it using the original numbers.