The Extended Euclidean Algorithm

Consider the numbers $a=1239$ and $b=168$. Their greatest common divisor (gcd) is $21$. Moreover, we can express $21$ as a linear combination of $a$ and $b$ (i.e., as a sum of integer multiples of $a$ and $b$): $$21 = 3 \cdot 1239 + (-22) \cdot 168$$ The Extended Euclidean Algorithm can be used to find the greatest common divisor (gcd) of two numbers, and to simultaneously express the gcd as a linear combination of these numbers. Amazingly, this algorithm finds the greatest common factor of two numbers without ever factoring the numbers! Further, it works incredibly fast, even on extremely large numbers (with hundreds of digits). The speed at which this algorithm works coupled with the necessary relative slowness of actually factoring very large numbers lies at the heart of how modern cryptographic methods work (the same methods that keep your credit card information safe when you are surfing the internet).

The algorithm is best explained by example. To find the gcd and an associated linear combination for $a=1239$ and $b=168$ (the same numbers mentioned previously), we do the following:

  1. First, we initialize some additional variables with the following values: $q=0$, $x = 0$, $y=1$, $x_{last} = 1$, and $y_{last} = 0$

  2. Then, while $b$ is not zero, we make the following replacements (in order):

    • $q \leftarrow a \textrm{ div } b$
    • $(a,b) \leftarrow (b, a \textrm{ mod } b)$
    • $(x,x_{last}) \leftarrow (x_{last} - q \cdot x, x)$
    • $(y,y_{last}) \leftarrow (y_{last} - q \cdot y, y)$

When we are done, it should be the case that
$$ \gcd(x,y) = x_{last} \cdot 1239 + y_{last} \cdot 168 $$

The below table shows the values of each variable above, both initially and after each set of replacements occurs:

$x$ $y$ $a$ $b$ $q$ $x_{last}$ $y_{last}$
0 1 1239 168 0 1 0
1 -7 168 63 7 0 1
-2 15 63 42 2 1 -7
3 -22 42 21 1 -2 15
-8 59 21 0 2 3 -22

Consequently, the above table tells us that $\gcd(1239,168) = 21$, and one linear combination of these two numbers that equals the gcd is given by: $$3 \cdot 1239 + (-22) \cdot 168$$