# 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

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

This identity is called Bézout's identity.

For example,

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

and

$$
6=30-18.
$$

Thus

$$
6=1\cdot30+(-1)\cdot18.
$$

The extended Euclidean algorithm gives such coefficients systematically.

## The Basic Idea

The ordinary Euclidean algorithm repeatedly divides with remainder:

$$
a=bq+r.
$$

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

Since

$$
r=a-bq,
$$

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

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

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

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

Thus

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

Now work backward.

From the second equation,

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

From the first equation,

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

Substitute this into the expression for $21$:

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

Expanding,

$$
21=462-3\cdot1071+6\cdot462.
$$

Thus

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

So one Bézout representation is

$$
\gcd(1071,462)=(-3)1071+7\cdot462.
$$

## Tabular Form

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

Start with

$$
r_0=a,
\qquad
r_1=b.
$$

Write each remainder as

$$
r_i=s_i a+t_i b.
$$

Initially,

$$
r_0=1\cdot a+0\cdot b,
$$

so

$$
s_0=1,
\qquad
t_0=0.
$$

Also,

$$
r_1=0\cdot a+1\cdot b,
$$

so

$$
s_1=0,
\qquad
t_1=1.
$$

If

$$
r_{i-1}=q_i r_i+r_{i+1},
$$

then

$$
r_{i+1}=r_{i-1}-q_i r_i.
$$

Hence the coefficients satisfy

$$
s_{i+1}=s_{i-1}-q_i s_i,
$$

$$
t_{i+1}=t_{i-1}-q_i t_i.
$$

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

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

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

$$
ax+by,
\qquad x,y\in\mathbb{Z}.
$$

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

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

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

$$
ax+ny=1.
$$

Reducing this equation modulo $n$, we obtain

$$
ax\equiv1\pmod n.
$$

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

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

$$
26=7\cdot3+5,
$$

$$
7=5\cdot1+2,
$$

$$
5=2\cdot2+1.
$$

Working backward,

$$
1=5-2\cdot2.
$$

Since

$$
2=7-5,
$$

we get

$$
1=5-2(7-5)=3\cdot5-2\cdot7.
$$

Since

$$
5=26-3\cdot7,
$$

we obtain

$$
1=3(26-3\cdot7)-2\cdot7
=3\cdot26-11\cdot7.
$$

Hence

$$
-11\cdot7\equiv1\pmod{26}.
$$

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

$$
-11\equiv15\pmod{26}.
$$

Indeed,

$$
7\cdot15=105\equiv1\pmod{26}.
$$

## Linear Diophantine Equations

The extended Euclidean algorithm also solves equations of the form

$$
ax+by=c.
$$

Such an equation has an integer solution exactly when

$$
\gcd(a,b)\mid c.
$$

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

$$
d=ax_0+by_0,
$$

then multiplying by $c/d$ gives

$$
c=a\left(x_0\frac cd\right)+b\left(y_0\frac cd\right).
$$

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.