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