Firstly, an algorithm is a routine. It is a list of instructions such as ‘you do this and then you do that’. We can see why computers like algorithms because they are very good at following instructions and never wander off track. Some mathematicians think algorithms are boring because they are repetitious, but to write an algorithm and then translate it into hundreds of lines of computer code containing mathematical instructions is no mean feat. There is a considerable risk of it all going horribly wrong. Writing an algorithm is a creative challenge. There are often several methods available to do the same task and the best one must be chosen. Some algorithms may not be ‘fit for purpose’ and some may be downright inefficient because they meander. Some may be quick but produce the wrong answer. It’s a bit like cooking. There must be hundreds of recipes (algorithms) for cooking roast turkey with stuffing. We certainly don’t want a poor algorithm for doing this on the one day of the year when it matters. So we have the ingredients and we have the instructions. The start of the (abbreviated) recipe might go something like this:

• Fill the turkey cavity with stuffing

• Rub the outside skin of the turkey with butter

• Season with salt, pepper and paprika

• Roast at 335 degrees for 3½ hours

• Let the cooked turkey rest for ½ hour

All we have to do is carry out the algorithm in sequential steps one after the other. The only thing missing in this recipe, usually present in a mathematical algorithm, is a loop, a tool to deal with recursion. Hopefully we won’t have to cook the turkey more than once.

In mathematics we have ingredients too – these are the numbers. Euclid’s division algorithm is designed to calculate the greatest common divisor (written gcd). The gcd of two whole numbers is the greatest number that divides into both of them. As our example ingredients, we’ll choose the two numbers 18 and 84.

The greatest common divisor

The gcd in our example is the largest number that exactly divides both 18 and 84. The number 2 divides both 18, and 84, but so does the number 3. So 6 will also divide both numbers. Is there a larger number that will divide them? We could try 9 or 18. On checking, these candidates do not divide 84 so 6 is the largest number that divides both. We can conclude that 6 is the gcd of 18 and 84, writing this as gcd(18, 84) = 6.

The gcd can be interpreted in terms of kitchen tiling. It is the side of the largest square tile that will tile a rectangular wall of breadth 18 and length 84, with no cutting of tiles allowed. In this case, we can see that a 6 × 6 tile will do the trick.

Tiling the square with a rectangular 18 × 84 tile

The greatest common divisor is also known as the ‘highest common factor’ or ‘highest common divisor’. There is also a related concept, the least common multiple (lcm). The lcm of 18 and 84 is the smallest number divisible by both 18 and 84. The link between the lcm and gcd is highlighted by the fact that the lcm of two numbers multiplied by their gcd is equal to the multiplication of the two numbers themselves. Here lcm(18, 84) = 252 and we can check that 6 × 252 = 1512 = 18 × 84.

Geometrically, the lcm is the length of the side of the smallest square that can be tiled by 18 × 84 rectangular tiles. Because lcm(a, b) = ab ÷ gcd(a, b), we’re going to concentrate on finding the gcd. We have already calculated gcd(18, 84) = 6 but to do it we needed to know the divisors of both 18 and 84. Recapping, we first broke both numbers into their factors: 18 = 2 × 3 × 3 and 84 = 2 × 2 × 3 × 7. Then, comparing them, the number 2 is common to both and is the highest power of 2 which will divide both. Likewise 3 is common and is the highest power dividing both, but though 7 divides 84 it does not divide 18 so it cannot enter into the gcd as a factor. We concluded: 2 × 3 = 6 is the largest number that divides both. Can this juggling of factors be avoided? Imagine the calculations if we wanted to find gcd(17640, 54054). We’d first have to factorize both these numbers, and that would be only the start. There must be an easier way.

The algorithm

There is a better way. Euclid’s algorithm is given in Elements, Book 7, Proposition 2 (in translation): ‘Given two numbers not prime to one another, to find their greatest common measure.’

The algorithm Euclid gives is beautifully efficient and effectively replaces the effort of finding factors by simple subtraction. Let’s see how it works.

The object is to calculate d = gcd(18, 84). We start by dividing 18 into 84. It does not divide exactly but goes 4 times with 12 (the remainder) left over:

84 = 4 × 18 + 12

Since d must divide 84 and 18, it must divide the remainder 12. Therefore d = gcd(12, 18). So we can now repeat the process and divide 18 by 12:

18 = 1 × 12 + 6

to get remainder 6, so d = gcd(6, 12). Dividing 6 into 12 we have remainder 0 so that d = gcd(0, 6). 6 is the largest number which will divide both 0 and 6 so this is our answer.

If computing d = gcd(17640, 54054), the successive remainders would be 1134, 630, 504 and 0, giving us d = 126.

Uses for the gcd

The gcd can be used in the solution of equations when the solutions must be whole numbers. These are called Diophantine equations, named after the early Greek mathematician Diophantus of Alexandria.

Let’s imagine Great Aunt Christine is going for her annual holiday to Barbados. She sends her butler John down to the airport with her collection of suitcases, each of which weighs either 18 or 84 kilograms, and is informed that the total weight checked-in is 652 kilograms. When he arrives back in Belgravia, John’s nine-year-old son James pipes up ‘that can’t be right, because the gcd 6 doesn’t divide into 652’. James suggests that the correct total weight might actually be 642 kilograms.

James knows that there is a solution in whole numbers to the equation 18x + 84y = c if and only if the gcd 6 divides the number c. It does not for c = 652 but it does for 642. James does not even need to know how many suitcases x, y of either weight Aunt Christine intends to take to Barbados.

The Chinese remainder theorem

When the gcd of two numbers is 1 we say they are ‘relatively prime’. They don’t have to be prime themselves but just have to be prime to each other, for example gcd(6, 35) = 1, even though neither 6 nor 35 is prime. We shall need this for the Chinese remainder theorem.

Let’s look at another problem: Angus does not know how many bottles of wine he has but, when he pairs them up, there is 1 left over. When he puts them in rows of five in his wine rack there are 3 left over. How many bottles does he have? We know that on division by 2 we get remainder 1 and on division by 5 we get remainder 3. The first condition allows us to rule out all the even numbers. Running along the odd numbers we quickly find that 13 fits the bill (we can safely assume Angus has more than 3 bottles, a number which also satisfies the conditions). But there are other numbers which would also be correct – in fact a whole sequence starting 13, 23, 33, 43, 53, 63, 73, 83, . . .

Let’s now add another condition, that the number must give remainder 3 on division by 7 (the bottles arrived in packs of 7 bottles with 3 spares). Running along the sequence 13, 23, 33, 43, 53, 63, . . . to take account of this, we find that 73 fits the bill, but notice that 143 does too, as does 213 and any number found by adding multiples of 70 to these numbers.

In mathematical terms, we have found solutions guaranteed by the Chinese remainder theorem, which also says that any two solutions differ by a multiple of 2 × 5 × 7 = 70. If Angus has between 150 and 250 bottles then the theorem nails the solution down to 213 bottles. Not bad for a theorem discovered in the third century.

The condensed idea

A route to the greatest