 # The greatest common divisor and the Euclidean algorithm

written in

In this blog post, we’re going to explore some properties of division of integers, and more specifically, a concept called the greatest common divisor. The greatest common divisor, or $$\gcd$$, is the largest positive integer that divides a pair of integers. For example, take the pair 16 and 24. One method of finding their common divisor is to find the divisors of each integer, and then see which is the largest one they have in common. So the divisors of 16 are:

$$\{-16, -8, -4, -2, -1, 1, 2, 4, 8, 16\}$$

Likewise for 24, we have:

$$\{-24, -12, -8, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 8, 12, 24\}$$

Just from eyeballing these two sets, it’s obvious that the $$\gcd(24, 16)$$ is 8.

However, what do we do when the numbers are large and the set of divisors is not so manageable? We can calculate it using something called the Euclidean algorithm. The way it works is like so. We first need to consider the formal definition of division, which states that $$a = bq + r$$, where $$0 \leq r < b$$. What this means is that we take some integer $$a$$, divide it by $$b$$ (the divisor) $$q$$ (quotient) times, and have some remainder $$r$$ which is always smaller than the divisor $$b$$. It turns out that these numbers are related by their greatest common divisors, where $$\gcd(a, b) = \gcd(b, r)$$. So if we want to find the $$\gcd(a, b)$$, we can use the fact that it is equivalent to $$\gcd(b, r)$$ to find it. This is still a bit abstract, so let’s see how it works using an example.

Let’s say we want to find $$\gcd(2406, 654)$$. Then we first divide 2406, working out the quotient and the remainder:

$$2406 = 654 \cdot 3 + 444$$

So we have $$a = 2406$$, $$b = 654$$, $$q = 3$$ and $$r = 444$$. We know that $$\gcd(2406, 654) = \gcd(654, 444)$$, so we can now try to solve for the latter:

$$654 = 444 \cdot 1 + 210$$

Now you can see that we’ve substituted in $$\gcd(b, r)$$ for $$\gcd(a, b)$$, and we now solve for this. We can continue doing this until we end up with a remainder of 0, which means we’ve found our $$\gcd(a, b)$$:

\begin{aligned} 2406 &= 654 \times 3 + 444 &\Rightarrow gcd(2406, 654) &= gcd(654, 444) \\ 654 &= 444 \times 1 + 210 &\Rightarrow gcd(2406, 654) &= gcd(444, 210) \\ 444 &= 210 \times 2 + 24 &\Rightarrow gcd(2406, 654) &= gcd(210, 24) \\ 210 &= 24 \times 8 + 18 &\Rightarrow gcd(2406, 654) &= gcd(24, 18) \\ 24 &= 18 \times 1 + 6 &\Rightarrow gcd(2406, 654) &= gcd(18, 6) \\ 18 &= 6 \times 3 &\Rightarrow gcd(2406, 654) &= gcd(6, 0) = 6 \end{aligned}

We can see that when we get to $$\gcd(18, 6)$$ we have a remainder of 0, therefore $$\gcd(2406, 654) = 6$$.

We can abstract the form of this equation as follows:

\begin{aligned} a &= bq_1 + r_1 \\ b &= r_1q_2 + r_2 \\ r_1 &= r_2q_3 + r_3 \\ r_2 &= r_3q_4 + r_4 \\ \ldots \\ r_{k-4} &= r_{k-3}q_{k-2} + r_{k-2} \\ r_{k-3} &= r_{k-2}q_{k-1} + r_{k-1} \\ r_{k-2} &= r_{k-1}q_k \end{aligned}

## Representing the gcd as a linear combination

As you’ve seen above, the Euclidean algorithm is a simple way of calculating the gcd of a pair of integers. It turns out to have other applications as well. It turns out the the gcd of any pair of integers can be represented as a linear combination, in the form $$d = ma + nb$$, where $$d$$ is our gcd, $$a$$ and $$b$$ are the integers we found the gcd of, and $$m$$ and $$n$$ are integers we must multiply them by in order to get the gcd. For our example above, we’d be looking for $$6 = 2406m + 654n$$. But how do we find $$m$$ and $$n$$? Well, we can use the results of the calculation above to get the values we need.

Above, we defined that each line can be defined according to the values of $$r$$ and $$q$$ in the previous lines in the sequence. We can use this pattern to work out the values of $$m$$ and $$n$$, by starting from the second last line and working our way to the top.

Looking at the second last line, $$24 = 18 \times 1 + 6$$ can be defined as $$r_{k - 3} = r_{k - 2}q_{k - 1} + r_{k - 1}$$, where $$r_{k - 3} = 24$$, $$r_{k - 2} = 18$$, $$q_{k - 1} = 1$$ and $$r_{k - 1} = 6$$. Well $$r_{k - 1} = 6$$ is our $$\gcd(2406, 654)$$, which is equal to $$d$$. So we can rearrange the equation to solve for $$r_{k - 1}$$:

\begin{aligned} r_{k - 3} &= r_{k - 2}q_{k - 1} + r_{k - 1} \\ r_{k - 3} - r_{k - 1} &= r_{k - 2}q_{k - 1} \\ -r_{k - 1} &= r_{k - 2}q_{k - 1} - r_{k - 3} \\ r_{k - 1} &= -r_{k - 2}q_{k - 1} + r_{k - 3} \end{aligned}

We can rewrite this is the form $$r_{k - 1} = m'r_{k - 2} + n'r_{k - 3}$$ by taking $$m' = -q_{k - 1}$$ and $$n' = 1$$ (we use $$m'$$ and $$n'$$ as we’re going to have to calculate a number of $$m$$s and $$n$$s, and we need to differentiate them). We’re now on our way to representing the equation in the form $$d = ma + nb$$.

Having solved for line $$k-1$$, we now move to the next line $$k-2$$. We can rearrange this line so that we go from $$r_{k-4} = r_{k-3}q_{k-2} + r_{k-2}$$ to $$r_{k-2} = r_{k-4} - r_{k-3}q_{k-2}$$. We can now substitute this into our current equation for $$r_{k - 1}$$:

\begin{aligned} r_{k - 1} &= m'r_{k - 2} + n'r_{k - 3} \\ &= m'(r_{k-4} - r_{k-3}q_{k-2}) + n'r_{k - 3} \\ &= m'_{k-4} - m'r_{k-3}q_{k-2} + n'r_{k - 3} \\ &= m'_{k-4} - r_{k-3}(m'q_{k-2} + n') \end{aligned}

We can now represent $$m'q_{k-2} + n'$$ as $$m''$$ and $$m'$$ as $$n''$$. We then repeat these steps until we get to a form that contains $$a$$ and $$b$$. You can see this in the table below:

$$\textrm{Iteration}$$ $$\textrm{Raw calculation}$$ $$\textrm{Rewritten calculation}$$ $$m$$ $$n$$
$$1$$ $$r_{k-3}-r_{k-2}q_{k-1}$$ $$m'r_{k-2}+n'r_{k-3}$$ $$-q_{k-1}$$ $$1$$
$$2$$ $$m'(r_{k-4}-r_{k-3}q_{k-2})+n'r_{k-3}$$ $$m''r_{k-3}+n''r_{k-4}$$ $$n'-m'q_{k-2}$$ $$m'$$
$$3$$ $$m''(r_{k-5}-r_{k-4}q_{k-3})+n''r_{k-4}$$ $$m'''r_{k-4}+n'''r_{k-5}$$ $$n''-m''q_{k-3}$$ $$m''$$
$$4$$ $$m'''(b-r_{k-5}q_{k-4})+n'''r_{k-5}$$ $$m''''r_{k-5}+n''''b$$ $$n'''-m'''q_{k-4}$$ $$m'''$$
$$5$$ $$m''''(a-bq_{k-5})+n''''b$$ $$m'''''b+n'''''a</td>$$n''''-m''''q_{k-5}m''''$$Let’s now apply this to our problem. To make it easier, let’s first get every value of $$r$$ and $$q$$ we’ll need to work with:$$\textrm{Line}rqk-161k-2188k-3242k-42101k-54443$$We can then solve for $$m$$ and $$n$$ like so:$$\textrm{Iteration}\textrm{Raw calculation}\textrm{Rewritten calculation}mn124-18\times1-1\times18+1\times24-112-1(210 - 24\times8)+1\times2419\times24+-1\times2109-139(444-210\times2)+-1(210)-19\times210+9\times444-1994-19(654-444\times1)+9(444)28\times444+-19\times6542819528(2406-654\times3)+-19(654)-103\times654 + 28\times2406-10328$$Which gives us our solution to $$d$$:$$d = 28 \times 2406 + (-103) \times 654