The Euclidean Algorithm¶
We now return to the familiar world of the integers, where we will learn (or perhaps remind ourselves) about what the greatest common divisor of two integers is, and about an algorithm which allows us to compute them easily, and why it works. This will form part of the motivation for the idea of a euclidean ring, a structure which generalises the integers.
Integer division¶
Let \(a, b \in \mathbb{Z}\). We say that \(a\) divides \(b\) if there exists some \(q \in \mathbb{Z}\) such that \(aq = b\). Another way of understanding this is that \(b\) can be divided exactly by \(a\) to yield \(q\). In symbols, this is written \(a \mid b\).
For example, \(5 \mid 20\), and also \(4 \mid 20\).
Of course, we often have to deal with the less happy situation where integers don’t divide exactly into each other. All hope is not lost, though: if we have two integers \(a, b\), with \(b > 0\), then there always exists a pair of integers \(q\) and \(r\) such that \(a = qb + r\), and \(0 \leq r < b\). We usually call \(q\) the quotient and we call \(r\) the remainder. You probably know already that a remainder of \(0\) indicates that the pair of integers we are dealing with do divide into each other exactly.
Greatest common divisors¶
If \(d\) divides \(a\), and \(d\) also divides \(b\), we say that \(d\) is a common divisor of \(a\) and \(b\). If \(d\) is greater than any other common divisor of \(a\) and \(b\), we say that \(d\) is the greatest common divisor of \(a\) and \(b\). This chapter is mostly concerned with finding the greatest common divisor of any pair of integers; we can do this by using an algorithm called the Euclidean Algorithm.
Before we go on to talk about the Euclidean Algorithm, though, we first need a result concerning divisors. Here it comes:
Let \(a, b, d \in \mathbb{Z}\), and suppose that \(d \mid a\) and that \(d \mid b\). Then, \(d \mid ma + nb\) for any \(m, n \in \mathbb{Z}\).
To prove this, we go back to the definition; we just need to find an integer \(c\) such that \(cd = ma + nb\). How might we go about that? Well we already know that \(d \mid a\), so we know that there is an integer \(c_1\) such that \(c_1d = a\). We also know that \(d \mid b\), so we know that there is another integer \(c_2\) such that \(c_2d = b\). It follows, then, that \(mc_1d = ma\), and that \(nc_2d = nb\). Add these equations together and you get \(mc_1d + nc_2d = ma + nb\). The distributive law allows us to rearrange the left hand side, yielding \((mc_1 + nc_2)d = ma + nb\), from which we can immediately deduce that \(d \mid ma + nb\).
The Euclidean Algorithm¶
We will start by working through an example; suppose we want to find the greatest common divisor of \(a = 1071\) and \(b = 462\). Let’s call their greatest common divisor \(d\). So immediately we have that \(d \mid 1071\) and that \(d \mid 462\).
We start by dividing \(a\) by \(b\):
That is, we get a quotient of \(2\) and a remainder of \(147\). How does this help? Well, we now know that \(147 = 1071 - 2*462\). Using the result from a moment ago, if we choose \(m = 1\) and \(n = -2\), we have that \(d \mid ma + nb\), that is, \(d \mid 147\).
We now divide \(462\) by the remainder:
Using the same argument as before, we see that \(21 = 462 - 3*147\) and therefore \(d \mid 21\). We now divide our previous remainder by our new remainder:
This time, it goes exactly. The significance of this is that we have found our GCD: it is \(21\). Why? Well, starting from the final step and working backwards, we now know that \(21 \mid 147\). Looking to the previous step, since \(21 \mid 147\) and \(21 \mid 21\) (note that any integer divides itself), we can deduce using that same result from a moment ago that \(21 \mid 3 * 147 + 21\) i.e. \(21 \mid 462\). Now going back to the very first step, we can use a similar argument to show that since \(21 \mid 462\) and \(21 \mid 147\), we have that \(21 \mid 1071\). So we have established that \(21\) is a common divisor of \(1071\) and \(462\). It then follows that \(d \geq 21\).
The only way that we can have \(d \geq 21\) and \(d \mid 21\) simultaneously is if \(d = 21\), so we’re done.
So the general form of the algorithm is that we keep dividing successive remainders into each other until we find a pair that go exactly, and then the last remainder is the greatest common divisor. In PureScript:
gcd :: Int -> Int -> Int
gcd a 0 = a
gcd a b = gcd b (a `mod` b)
(note that a `mod` b computes the remainder when dividing a by b.)
Exercise 9.1. Perform the Euclidean Algorithm on \(a = 1938\), \(b = 782\).
How do we know that the algorithm terminates, though? We refer to the theorem from the beginning of the chapter:
Note
If we have two integers \(a, b\), with \(b > 0\), then there always exists a pair of integers \(q\) and \(r\) such that \(a = qb + r\), and \(0 \leq r < b\).
In particular, \(r < b\). That is, the remainders keep getting smaller. A sequence of nonnegative integers which keep getting smaller is guaranteed to eventually reach \(0\), so we know that our algorithm will always terminate and all is well.