7 min read

On the Extended Euclidean Algorithm

We’re going to look at another algorithm by our old pal Euclid. But before we do, no discussion of the extended Euclidean algorithm would be complete without first taking a step back to consider the Euclidean algorithm and Bézout’s identity.

The Euclidean algorithm is of one of the oldest known algorithms that is still in common use today and has real-world, practical applications beyond mathematical algorithms such as those found in RSA.

Described in his book the Elements circa 300BCE, the algorithm determines the greatest common divisor of two numbers. My interest is in how it is used in number theory and cryptography.

The Euclidean Algorithm

First, we need to be acquainted with a helpful algorithm known as the division algorithm, which computes the quotient and remainder for two integers n and d in the form:

n = dq + r, where 0 <= r < d

n = dividend (numerator)
d = divisor (denominator)
q = quotient
r = remainder

For example:

n = 57
d = 13

57 = 13(4) + 5

Note that for Euclid’s algorithm we don’t care about the quotient, but we do for the extended Euclidean algorithm!

The Algorithm

Let’s compute the following: gcd(a, b)

Before starting, assign the larger number to n and the smaller to d.

  1. Divide n by d and assign the remainder to r.
  2. If r > 0, assign d to n and r to d. Repeat step 1.
  3. Else if r == 0, the greatest common divisor is d.

This algorithm is fast, and every other iteration the value of r is reduced by a bit!

Examples

gcd(51, 39)

n = 51, d = 39

Step 1
    n = 51
    d = 39
    r = n % d = 12

Step 2
    Is r > 0? Yes.

Step 1
    n = 39
    d = 12
    r = n % d = 3

Step 2
    Is r > 0? Yes.

Step 1
    n = 12
    d = 3
    r = n % d = 0

Step 2
    Is r > 0? No!

Step 3
    The gcd(51, 39) is 3.

Easy peasy lemon squeezy!

Let’s do another! Weeeeeeeeeeeeeeeeeeeeee

gcd(17, 97)

n = 97, d = 17

Step 1
    n = 97
    d = 17
    r = n % d = 12

Step 2
    Is r > 0? Yes.

Step 1
    n = 17
    d = 12
    r = n % d = 5

Step 2
    Is r > 0? Yes.

Step 1
    n = 12
    d = 5
    r = n % d = 2

Step 2
    Is r > 0? Yes.

Step 1
    n = 5
    d = 2
    r = n % d = 1

Step 2
    Is r > 0? Yes.

Step 1
    n = 2
    d = 1
    r = n % d = 0

Step 2
    Is r > 0? No!

Step 3
    The gcd(17, 97) is 1.

And this is straightforward to code. Here is a recursive approach in C:

euclidean_algorithm.c

#include <stdlib.h>
#include <stdio.h>

// gcc -o gcd euclidean_algorithm.c

int gcd(int a, int b) {
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

void main(int argc, char **argv) {
    if (argc < 3) {
        printf("[ERROR] Not enough args: %s [a] [b]\n", argv[0]);
        exit(1);
    }

    printf("%d\n", gcd(atoi(argv[1]), atoi(argv[2])));
}

Having the base case be a % b == 0 rather than b == 0 saves us one recursive call on the stack.

Now, that we have the Euclidean algorithm under our belt, let’s take another step on the way to our main topic, the extended Euclidean algorithm.

Bézout’s Identity

Bézout’s identity, as its name suggests, was named after the 18th century French mathemetician Étienne Bézout. The theorem states the following (from Wikipedia):

Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

So, we can write:

gcd(a, b) = ax + by

The pair of coefficients x and y are referred to as Bézout’s coefficients for (a, b) and can be computed by the extended Euclidean algorithm. Let’s turn to this now.

So, why is this important? Well, for one, it can determine the modular multiplicative inverse, and this can be used as the private key in asymmetric encryption. I’ll cover this is my next article.

The Extended Euclidean Algorithm

As the Euclidean algorithm needs the division algorithm, so does the extended algorithm. In addition, we are interested in capturing the quotient for each expression (we weren’t before). Capturing the quotient will help us to compute Bézout’s identity.

In addition, we’ll want to rewrite each expression so the remainder is expressed as a linear combination:

n = dq + r
r = n - dq

Let’s now see how we can use this to compute both the greatest common divisor of a and b as well as Bézout’s coefficients.

The Algorithm

Before beginning, assign the numbers to a and b, with the former containing the larger value. These will be used throughout the algorithm in our substitutions.

The algorithm:

  1. Compute the division algorithm, rewriting it to so the remainder is represented as a linear combination, and substitute values with the previously-computed polynomial expressions.
  2. If r > 0, assign d to n and r to d. Repeat step 1.
  3. If r == 0, calculate the polynomial expression for the penultimate Step 1.

Example

gcd(527, 341)

a = 527, b = 341

Step 1:
    n = 527
    d = 341
    q = 1
    r = n % d = 186

    186 = 527 - 341(1)
    186 = a - b

Step 2:
    Is r > 0? Yes.

Step 1:
    n = 341
    d = 186
    q = 1
    r = n % d = 155

    155 = 341 - 186(1)
    155 = b - (a - b)
    155 = -a + 2b

Step 2:
    Is r > 0? Yes.

Step 1:
    n = 186
    d = 155
    q = 1
    r = n % d = 31

    31 = 186 - 155(1)
    31 = (a - b) - (-a + 2b)
    31 = 2a - 3b

Step 2:
    Is r > 0? Yes.

Step 1:
    n = 155
    d = 31
    q = 5
    r = n % d = 0

    0 = 155 - 31(5)
    0 = (-a + 2b) - 5(2a - 3b)
    0 = -11a + 17b

Step 2:
    Is r > 0? No!

Step 3:
    31 = 2a - 3b
    31 = 2(527) - 3(341)
    31 = 1054 - 1023
    31 = 31

So, we've learned the gcd is 31 and that the coefficients are 2 and -3, respectively
(one of the numbers will always be negative).
It's a twofer!  We can now determine our entire expression!

gcd(527, 341) = 527x + 341y
           31 = 527(2) + 341(-3)
           31 = 1054 - 1023
           31 = 31

Hmm, looks suspiciously like Step 3 above!  Bingo!

For completeness, we can also verify the polynomial expression from the last Step 1.

0 = -11a + 17b
0 = -11(527) + 17(341)
0 = -5797 + 5797

Note that by rewriting the expression for the remainder and substituting as we go that we’re essentially computing the Euclidean algorithm and the extended Euclidean algorithm at the same time, so that we’re done by the time we’ve determined the gcd.

There is a way to do this that some may consider a shortcut, whereby the gcd is first determined by the former before employing the latter to reverse the expressions, substituting as you go. I personally find this to be a bit confusing, so I’m not covering it here

Conclusion

So, what have we learned?

We now know that the Euclidean algorithm determines the greatest common divisor for two numbers. It is efficient and fast.

Once we’ve determined that, we can write Bézout’s identity:

ax + by = gcd(a, b)

Neat!

Lastly, we know that the extended Euclidean algorithm computes both the gcd and the coefficients for Bézout’s identity. It is extremely useful and can be seen in cryptographic systems like RSA.

My next article well delve into how we can use the extended Euclidean algorithm to calculate the modular multiplicative inverse for any number where the gcd(a, b) = 1.

Weeeeeeeeeeeeeeeeeeeeeeee

References