# Extended Euclidean Algorithm — Number Theory

*Written for publication on samxsmith.com*

The Extended Euclidean Algorithm is, as you might imagine, an extension of the standard Euclidean Algorithm. The standard version was developed in order to find the **greatest common divisor (GCD)** of two numbers. It also allows us to prove Lagrange’s four-square theorem.

The Extended algorithm adds the capability to find the Bézout coefficients for the two input numbers. We’ll cover the Extended algorithm & the Bézout identity but first we need to understand the core algorithm, for finding the GCD of 2 numbers.

# The Euclidean Algorithm

Define `a`

& `b`

as the two numbers for which we want to find the GCD. Here’s how the algorithm works:

Step 1) If

`is 0 then`

a`is the GCD.`

bStep 2) Else, set

`. and set`

a = b % a`. Repeat these steps until`

b = previous a`is 0.`

a`is your GCD.`

b

Here’s an example for finding the GCD of 273 & 399:

`> a = 273, b = 399`

> a is not 0

a₁ = 126 (399 % 273)

b₁ = a = 273

> a₁ is not 0

a₂ = 21 (273 % 126)

b₂ = a₁ = 126

> a₂ is not 0

a₃ = 0 (126 % 21)

b₃ = a₂ = 21

> a₃ is 0

> b₃ is 21

> So GCD is 21

And we can verify that 21 is a divisor of both 462 & 1071:

`273 % 21 = 0`

399 % 21 = 0

Why does that work? We can visualise the reasoning using a rectangle, where its lengths take the size of the two numbers in question.

To find a number which divides both 399 and 273, we need to find a square of some size which can tile the entire rectangle. To find the GCD, we are looking for the largest square that can do this.

Euclid’s algorithm works as follows. Take the length of the smaller side of the rectangle. `273`

in this case. Fill the rectangle with as many `273 x 273`

squares as will fit. Find the sides of the remaining rectangle, if any. One side will have length `273`

, the shorter length of the original rectangle.

We filled the rectangle with squares of length `273`

, physically dividing it. The remainder of the length is therefore found with `long_side % short_side`

e.g. `399 % 273 = 126`

. If the remainder is `0`

, the whole rectangle is filled. The size of the square is our GCD. Otherwise, we treat the leftover area as a new rectangle, and repeat the process. This continues until no space is left. At that point, the size of the last square used is the GCD.

This is a visual indication of how Euclid’s Algorithm works. The process of redefining `a`

& `b`

is equivalent to repeating the process of filling a rectangle as much as possible, then choosing a new size of square, and filling again.

21 is our smallest square length size. With those squares we are able to completely cover the rectangle. Because these `21 x 21`

squares could cover the whole rectangle we know that 21 literally fits into both `399`

& `273`

.

That’s how the Euclidean algorithm operates. We can use it to determine what the greatest common divisor of two numbers is, or determine whether two numbers are coprime (have a GCD of 1).

# Bézout’s Identity

Bézout’s Identity states that for the GCD of `a`

& `b`

, which we’ll call `d`

, there are integers `x`

& `y`

such that `ax + by = d`

.

It’s used in modular arithmetic to help find modular multiplicative inverses, because it rearranges like so:

`ax + by = d`

> subtract d, subtract -by

ax - d = -by

> this tells us that (ax - d) is a multiple of b

ax - d = (-y)b

> So we know that

ax % b = d

More generally, the Bézout Identity gives us a way of reasoning about coprimes in relation to one another. How could we calculate these values? Up steps the Extended Euclidean Algorithm.

# The Extended Euclidean Algorithm

Euclid didn’t stop with GCDs. We can extend the algorithm we looked at earlier to calculate not just the GCD of two numbers, but their Bézout coefficients too. For finding modular multiplicative inverses this algorithm is a one-stop shop.

You’ll remember that Euclid’s algorithm recursively redefined `a`

& `b`

until we found a divisor which left no remainder. That part of the process does not change. Now though, alongside finding the GCD of `a`

& `b`

we will also find their Bézout coefficients as we go along.

At each step of the Euclidian Algorithm `b`

is the proposed GCD. At the end of the algorithm the final value of `b`

is the correct GCD. The Extended Algorithm works with this assumption, by calculating the Bézout coeffecients for each attempt at a GCD, the value `bᵢ`

, at each step.

We know the formula for Bézout’s Identity is `ax + by = GCD`

. At each step `bᵢ`

is the proposed GCD. So `aᵢxᵢ + bᵢyᵢ = bᵢ`

. At the beginning this is simple. `b₀`

is the proposed GCD.

`> Where i = 0, we want to satisfy`

a₀x₀ + b₀y₀ = b₀

> Solved by x₀ = 0, y₀ = 1

a₀(0) + b₀(1)

= b₀(1)

= b₀

So we have our starting values `x₀, y₀ = 0, 1`

. In the following steps the value of `b`

will change. We need to adjust `x`

& `y`

accordingly, so that:

`> for every step, i:`

a₀xᵢ + b₀yᵢ = bᵢ

For each new value of the potential GCD, `bᵢ`

, we need to find `xᵢ`

and `yᵢ`

so that they conform to the Bezout Identity for the original `a`

and `b`

values, `a₀`

& `b₀`

. This would be intensive, if we did not have the `x`

& `y`

values from the previous step. With those values we are able to deduce the new ones.

`> Remember how we find b for the next step?`

bᵢ₊₁ = aᵢ

> And also how we find b for the next step

aᵢ = bᵢ₋₁ % aᵢ₋₁

> We can substitute "a" out altogether

bᵢ₊₁ = aᵢ

bᵢ₊₁ = bᵢ₋₁ % bᵢ

**Note**: A “Euclidean division” separates the “quotient”, which is the integer part of the result, and the remainder For example `62/7`

would give a quotient of `8`

and a remainder of `6`

. A modulus operation is simply the dividend, `62`

, minus the divisor multiplied by the quotient: `7 * 8`

. `62 - (7 * 8) = 6`

Another example:

`43 % 8 = 3`

> OR

QUOTIENT OF 43/8 = 5

43 - (8 * 5) = 3

With this in mind, let’s start to prep for the Extended algorithm.

`> We want an easy way to find the Bézout Coefficients at each step`

bᵢ₊₁ = a₀xᵢ₊₁ + b₀yᵢ₊₁

> We know how to find bᵢ₊₁:

bᵢ₊₁ = bᵢ₋₁ % bᵢ

> Or in terms of Euclidean division

bᵢ₊₁ = bᵢ₋₁ - bᵢ(QUOTIENT(bᵢ₋₁ / bᵢ))

> Let us define the quotient at each step:

qᵢ = QUOTIENT(bᵢ₋₁ / bᵢ)

> So to find the new b value:

bᵢ₊₁ = bᵢ₋₁ - bᵢqᵢ

> We will have Bézout's Identity for the previous step

bᵢ₋₁ = a₀xᵢ₋₁ + b₀yᵢ₋₁

> And we know the formula for the ith step

bᵢ = a₀xᵢ + b₀yᵢ

If that all makes sense, now we’re going to do some substitutions using what we’ve established, in order to find some way of actually calculating these Bézout coefficients going forward.

`> given the equations we have derived`

bᵢ = a₀xᵢ + b₀yᵢ

bᵢ₋₁ = a₀xᵢ₋₁ + b₀yᵢ₋₁

> and our formula for finding the next b value

bᵢ₊₁ = bᵢ₋₁ - bᵢqᵢ

> we can substitute them in

bᵢ₊₁ = (a₀xᵢ₋₁ + b₀yᵢ₋₁) - (a₀xᵢ + b₀yᵢ)qᵢ

bᵢ₊₁ = a₀xᵢ₋₁ + b₀yᵢ₋₁ - a₀xᵢqᵢ - b₀yᵢqᵢ

> group a & b terms

bᵢ₊₁ = (a₀xᵢ₋₁ - a₀xᵢqᵢ) + (b₀yᵢ₋₁ - b₀yᵢqᵢ)

> and factorise

bᵢ₊₁ = a₀(xᵢ₋₁ - xᵢqᵢ) + b₀(yᵢ₋₁ - yᵢqᵢ)

> compare this to the original Bézout formula

bᵢ₊₁ = a₀(xᵢ₊₁) + b₀(yᵢ₊₁)

> we can see that

xᵢ₊₁ = xᵢ₋₁ - xᵢqᵢ

yᵢ₊₁ = yᵢ₋₁ - yᵢqᵢ

This gives us a way to understand the relationship between the Bézout coefficients at consecutive steps of the Euclidean Algorithm.

Remember these steps from the original algorithm:

Define

`&`

a`as the two numbers for which we want to find the GCD. Here’s how the algorithm works:`

bStep 1) If

`is 0 then`

a`is the GCD.`

bStep 2) Else, set

`. and set`

a = b % a`.`

b = previous aRepeat these steps until

`is 0.`

a`is your GCD.`

b

We need to append to and amend these slightly in order to find both the GCD and Bézout’s Identity.

# Performing the Extended Euclidean Algorithm

Prep Step 1) Define `r₀`

& `r₁`

. `r₀`

is the value `a`

, `r₁`

is the value `b`

. These work just like `a`

& `b`

but makes successive steps easier to follow.

Prep Step 2) Define `x₀`

& `x₁`

as `1`

& `0`

respectively. Also, define `y₀`

& `y₁`

as `0`

& `1`

respectively. These values are pre-selected so that Bézout’s Identity is correct from the start. Remember that `r₁`

is the initial candidate for GCD. Therefore `r₀x + r₁y = r₁`

should be satisfied. This is ensured by setting `y₁ = 1`

& `x₁ = 0`

because `b = r₁`

, therefore `r₀(0) + r₁(1) = r₁`

.

Now we have those initial values, we can begin the algorithm.

Step 1) If `rᵢ`

is `0`

, stop. The GCD value is `rᵢ₋₁`

. The Bézout coefficients are `xᵢ₋₁`

& `yᵢ₋₁`

. This is the base case, which we’ll hit eventually.

Step 2) Find the new quotient, `qᵢ = rᵢ₋₁ / rᵢ`

.

Step 3) Find the next value of r, `rᵢ₊₁ = rᵢ₋₁ — (qᵢ * rᵢ)`

. (Reminder: this is equivalent to `rᵢ₋₁ % rᵢ`

. We use the quotient method because we need the quotient for the following steps.)

Step 4) Find the next value of `x`

, `xᵢ₊₁ = xᵢ₋₁ — (qᵢ * xᵢ)`

.

Step 5) Find the next value of `y`

, `yᵢ₊₁ = yᵢ₋₁ — (qᵢ * yᵢ)`

.

Step 6) Return to Step 1 and repeat.

That’s how it works. Example time! I’ll include the index, `i`

, at the beginning of each cycle to keep track of where we are.

Take the numbers `a = 7`

& `b = 93`

.

`r₀ = a = 7`

r₁ = b = 93

x₀ = 1

x₁ = 0

y₀ = 0

y₁ = 1

> AND begin!

i = 1

r₁ is not 0

q₁ = 0 (quotient of 7/93)

r₂ = 7 (7 - 0 * 93)

x₂ = 1 (1 - 0 * 0)

y₂ = 0 (0 - 0 * 1)

i = 2

r₂ is not 0

q₂ = 13 (quotient of 93 / 7)

r₃ = 2 (93 - 13 * 7)

x₃ = -13 (0 - 13 * 1)

y₃ = 1 (1 - 13 * 0)

i = 3

r₃ is not 0

q₃ = 3 (quotient 7 / 2)

r₄ = 1 (7 - 3 * 2)

x₄ = 40 (1 - 3 * -13)

y₄ = -3 (0 - 3 * 1)

i = 4

r₄ is not 0

q₄ = 2 (quotient 2 / 1)

r₅ = 0 (2 - 2 * 1)

x₅ = -93 (-13 - 2 * 40)

y₅ = 7 (1 - 2 * -3)

i = 5

r₅ IS 0

x = 40 (x₄)

y = -3 (y₄)

GCD = 1 (r₄)

There we have it. A greatest common divisor and Bézout coefficients for the values `a = 7`

, `b = 93`

. A GCD of 1 means they are coprime. We can confirm the Bézout identity is correct by substituting into the equation.

`> ax + by = GCD`

(7 * 40) + (93 * -3)

= 280 - 279

= 1

# That’s It

The Extended Euclidean Algorithm is an important contribution to number theory, very commonly used in cryptography. By finding coefficients for the Bézout Identity and proving whether a number is coprime, it allows us to find modular multiplicative inverses, as used in RSA encryption.