Euclidean Algorithm

The Euclidean algorithm determines the greatest common factor (GCF) of two integers. It is one of the oldest algorithms known, appearing in Euclid's Elements around 300 BC. However, the algorithm was probably known 200 years earlier in Babylonia and Egypt. Euclid originally formulated the problem geometrically, as the problem of finding a common measure for two line lengths, and his algorithm uses repeated subtraction of the shorter from the longer segment. This method does not require factoring.

PROCEDURE: Given two integers a and b, check if b is zero. If it is, then a is the GCF. If not, repeat the process using b and the remainder after integer division of a and b.

EXAMPLE: GCF (5760,2322) = ???

2322|5760 = 2 R 1116
1116|2322 = 2 R 90
90|1116 = 12 R 36
36|90 = 2 R 18
18|36 = 2 R 0

So GCF(5760,2322) = 18, the last non-zero remainder

When considering how many steps it takes to complete the algorithm, it turns out that the numbers requiring the most divisions are two successive Fibonacci numbers. A graph of the running time when finding the algorithm using a computer program can be found here.