Euclid's algorithm¹ is an elegant method for finding the greatest common divisor of two numbers. The principle behind the algorithm is simple but effective, and it has a number of other uses in number theory.

Division Revision

Addition, subtraction, and multiplication of natural numbers² is pretty straightforward; you mostly end up with another natural number³. With division, things become a bit more complicated. For example, there is no natural number equal to 13/5.

We get around this in number theory by using remainders. 13 divided by 5 gives 2, with a remainder of 3. The remainder is the uncomfortable leftover bit once the divisor has been taken away from the dividend as many times as possible⁴. Occasionally there is no remainder. In this case, we say that the divisor is a factor of the dividend.

Greatest Common Factor

Often it is necessary to talk about the greatest common factor (GCF) of two numbers: the largest factor that they have in common. The notation for the GCF of two numbers a and b is (a, b). For example, (12, 21) = 3, while (31, 16) = 1.

The most obvious method for finding the GCF of two numbers is to list all the factors of each number, and compare the lists to find the largest factor the two lists have in common. Unfortunately, this tends to take a while, especially with large numbers.

Luckily, there is a faster way - Euclid's algorithm.

A Useful Fact

Given two natural numbers a and b, and r the remainder of a on division by b, (a, b) = (b, r).

Proof - Say that a = b * k + r. In order for a natural number to divide both a and b, it must also divide r, whereas if a natural number divides only one of a and b, it will not divide r. The list of common divisors of a and b is therefore identical to the list of common divisors of b and r, so the GCD of a and b is the GCD of b and r.

Euclid's Algorithm

The useful thing about the remainder in a division problem is that it is usually smaller than either the dividend or the divisor. This means that by using the 'useful fact', the task on hand immediately becomes less complicated; instead of having to find the GCD of two large numbers, we have to find the GCD of a large number and a medium-sized number.

Repeated use of the 'useful fact' eventually gives two numbers for which finding the GCD is trivial. This is Euclid's algorithm for finding the GCD of two numbers.

For example: What is the greatest common divisor of 162 and 57?

Therefore the greatest common divisor of 162 and 57 is 3.

Applications

Working backward, Euclid's algorithm can be used to express (a, b) as the sum of a multiple of a and a multiple of b. As an example, we'll use the working above to express 3 as the sum of a multiple of 162 and a multiple of 57:

Being able to express the GCD of two numbers in this way is a useful by-product of the Euclidean algorithm.

For example, having found one solution to (a, b) = ax + by using the method above, we can characterise all solutions to equations c(a, b) = ax + by. As an example, without proof that the solutions to the equation 3 = 162x + 57y are: x = 6 - 19m, y = 54m -17, m any integer. The Edited Guide Entry on diophantine equations explains this process in more detail.

Euclid's algorithm also provides a continued fraction expansion for any rational number.