Extended Euclidean Algorithm

From GCDs to Linear Combinations

The Euclidean algorithm computes the greatest common divisor of two integers. The extended Euclidean algorithm does more. It also expresses the gcd as an integer linear combination of the original two integers.

For integers $a$ and $b$, not both zero, it finds integers $x$ and $y$ such that

This identity is called Bézout’s identity.

For example,

and

Thus

The extended Euclidean algorithm gives such coefficients systematically.

The Basic Idea

The ordinary Euclidean algorithm repeatedly divides with remainder:

The key observation is that each remainder can be written as a linear combination of $a$ and $b$.

Since

the first remainder is already a linear combination.

The next remainder is obtained by dividing $b$ by $r$, and it can also be rewritten in terms of $a$ and $b$. Continuing this process, the last nonzero remainder, which is the gcd, becomes a linear combination of the original numbers.

Example

Compute $\gcd(1071,462)$ and express it as a linear combination of $1071$ and $462$.

The Euclidean algorithm gives

Thus

Now work backward.

From the second equation,

From the first equation,

Substitute this into the expression for $21$:

Expanding,

Thus

So one Bézout representation is

Tabular Form

The backward substitution method is clear but can become cumbersome. A tabular version tracks coefficients during the Euclidean algorithm.

Start with

Write each remainder as

Initially,

so

Also,

so

If

then

Hence the coefficients satisfy

When the final nonzero remainder is reached, its coefficients give the desired Bézout identity.

Existence of Bézout Coefficients

The extended Euclidean algorithm proves that for any integers $a$ and $b$, not both zero, there exist integers $x$ and $y$ such that

This is a stronger statement than merely saying that the gcd exists.

It says that the greatest common divisor belongs to the set of all integer linear combinations

This fact will become essential in solving Diophantine equations and congruences.

Modular Inverses

One of the most important applications is the computation of modular inverses.

Suppose

Then the extended Euclidean algorithm gives integers $x$ and $y$ such that

Reducing this equation modulo $n$, we obtain

Thus $x$ is a multiplicative inverse of $a$ modulo $n$.

For example, find the inverse of $7$ modulo $26$. The Euclidean algorithm gives

Working backward,

Since

we get

Since

we obtain

Hence

Therefore an inverse of $7$ modulo $26$ is

Indeed,

Linear Diophantine Equations

The extended Euclidean algorithm also solves equations of the form

Such an equation has an integer solution exactly when

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

then multiplying by $c/d$ gives

Thus a solution is obtained directly from Bézout coefficients.

Role in Number Theory

The extended Euclidean algorithm is one of the central computational tools of elementary number theory.

It computes gcds, proves Bézout identities, finds modular inverses, solves linear Diophantine equations, and prepares the ground for the Chinese remainder theorem.

Its importance comes from the fact that it turns divisibility into explicit arithmetic. It does not merely prove that a gcd exists. It shows how the gcd is built from the two original integers.