Euclid’s Algorithm

Euclid of Alexandria is one of the most influential names in the entire history of mathematics. Although best known for his work on geometry, he also devised a mathematical algorithm for finding the greatest common factor of two numbers.

What if we wanted to find the greatest common factor (GCF) of 897 and 481? Euclid’s first step was to divide the biggest number by the smallest

The next step is to divide the denominator above by the remainder. This process of dividing the previous denominator by the remainder continues until there is no remainder. At this point the last denominator is the highest common factor of both numbers.

So our above example continues as:

As there is no longer a remainder, 13 is the greatest common factor (GCF) of 897 and 481.

This version of Euclid’s algorithm is an efficient way to compute the GCF of two numbers. In fact, the number of steps required never exceeds five times the number of digits in the smaller integer. This was proved by French mathematician Gabriel Lamé in 1844 using the Fibonacci sequence.

To see how Lamé did it, let’s consider a general case where we are trying to find the GCF of two numbers s and t where s > t.

We can say that:

and

In the case above 897 = (481 × 1) + 416 and 481 = (416 × 1) + 65

We can continue the chain:

Since the the quotients q_i, are always greater than or equal to 1 (since s > t) we can say that:

Similarly, we can say that:

By substituting (2) into (1)

Then substitute (3) into (5)

The next step shows that:

Writing it all out together shows that:

Lamé spotted the presence of the famous Fibonacci sequence in (8). This allowed him to write:

The remainders are ever decreasing, and r_n-1 is the last non-zero remainder, and so we can write:

This allows us to write the following:

A property of the Fibonacci sequence is the following identity:

(Try testing this out with the first few Fibonacci numbers)

Combining (11) and (12) gives:

Let’s park (13) for later and note that the golden ratio is the limit (as n goes to infinity) of the ratio between successive numbers in the Fibonacci series and is often designated with the Greek letter ?, such that ? ~ 1.618.

Another property of the Fibonacci sequence is that:

If we use the simple fact that 2 > ?, then the following is true:

So,

Another property of the Fibonacci sequence is that:

(Again test it out with the first few Fibonacci numbers)

So,

If that is true then so is:

And we know from (13) that:

Therefore,

Let’s say t is an integer with a length of d digits. If this is the case then:

This is always the case, since log is an increasing function. Take 100,000 – the first 6 digit number – then, log (100,000) = 5. (To check that (22) is valid, observe that:  d > d-1 = log(10^(d-1))> log t, where t is any integer with d digits).

Using (21)

We also know that:

So we can say that:

Combining (22), (23) and (25) gives:

Finally, this shows that:

The total number of steps in Euclid’s algorithm cannot exceed five times the number of digits in the smallest of the two numbers. Two thousands years passed between Euclid’s formulation of his algorithm in around 300BC, and this proof was given by Gabriel Lamé in 1844.