Euclidean algorithm

The Euclidean algorithm is an efficient algorithm that finds the greatest common divisor of two integers, without knowledge of their prime factorizations. It is one of the oldest algorithms still in use today, based on the following theorem:

This theorem turns out to be a consequence of the remainder \(a \bmod b\) being a linear combination of \(a\) and \(b\), as any factor that divides \(a\) and \(b\) must also divide their linear combination \(a \bmod b.\) So, \(a\) and \(b\) end up sharing the same set of common factors as \(a \bmod b\) and \(b\), including the same greatest common divisor.

Remember, the order of the inputs does not matter for the \(\gcd\) function: \(\gcd(a, b) = \gcd(b, a).\) So do not focus on the order here. Basically, what this theorem is saying is that the greatest common divisor of two positive integers stays the same even if one of the integers has the other integer subtracted from it a certain number of times (which is essentially the effect of the \(\bmod\) operation).

The result of \(a \bmod b\) will always be \(a\) if \(a < b\), which is not very useful if our goal is to make the greatest common divisor easier to compute. The part of this theorem that is actually useful to the Euclidean algorithm is when \(a \geq b\), which means \(a \bmod b\) will decrease in size, becoming smaller than \(b\), since, as you know, \(a \bmod b\) can only return an integer in the set \(\set{0, ... b-1}.\) This process brings \(a\) progressively closer to the greatest common divisor, as you'll see below:

algorithm euclid is
    input: two integers, a and b, where a ≥ b
    output: their greatest common divisor (gcd)

    while b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    return a

The larger integer a gets continually replaced until the smaller integer b is able to divide it and a mod b = 0, at which point a holds the greatest common divisor. Let's watch this algorithm step-by-step:

Here is exactly how the algorithm uses the theorem mentioned earlier:

Quite effective! And especially useful for large integers, whose prime factorizations would take way too long to compute.

Extended version

The extended Euclidean algorithm not only returns the greatest common divisor of two integers \(a\) and \(b\), but also the integer coefficients \(x\) and \(y\) such that \(ax + by = \gcd(a, b).\)

To briefly explain how it does this, it recognizes that the equation that defines integer division, \(a = (a \text{ div } b) \times b + (a \bmod b)\), can always be rearranged as \((a \bmod b) = a - (a \text{ div } b) \times b\) to express \(a \bmod b\) as a linear combination of \(a\) and \(b.\) This equation is then updated as a and b update each iteration until a mod b = 0, at which point the loop finishes. During the second-to-last iteration of the loop, a mod b stores the value of the greatest common divisor for the originally input a and b, which is why we maintain "previous" variables, so that in the end, we can access those second-to-last values. Here's the extended algorithm:

algorithm extended_euclid is
    input: two integers, a and b, where a ≥ b
    output: their greatest common divisor (gcd) and x and y such that ax + by = gcd(a, b)

    previous_x ← 1
    x ← 0
    previous_y ← 0
    y ← 1

    while b ≠ 0
        temp_x ← x
        x ← previous_x - a div b * x
        previous_x ← temp_x

        temp_y ← y
        y ← previous_y - a div b * y
        previous_y ← temp_y

        t ← b
        b ← a mod b
        a ← t
    return a, previous_x, previous_y

Let's walk through this algorithm for the inputs a = 1071 and b = 462:

All we had to do was keep records of these \(a \bmod b\) equations from each iteration. That is the entirety of the Euclidean algorithm's extension. The integer coefficients \(x\) and \(y\) such that \(ax + by = \gcd(a, b)\) are a byproduct of computing \(\gcd(a, b)\) with the Euclidean algorithm. In other words, \(x\) and \(y\) were always present, we just had to write a bit more code to pay attention to how they update with \(a\) and \(b.\) Overall, this extension allows us to get more out of the algorithm than we normally would for very little additional computing cost, which is really nice!