Lamé's theorem

Lamé's Theorem is the result of Gabriel Lamé's analysis of the complexity of the Euclidean algorithm. Using Fibonacci numbers, he proved in 1844 that when looking for the greatest common divisor of two integers a and b, the algorithm finishes in at most 5k steps, where k is the number of digits of b.

Statement

The number of division steps in the Euclidean algorithm with entries and is less than times the number of decimal digits of.

Proof

Let be two positive integers. Applying to them the Euclidean algorithm provides two sequences and of positive integers such that, setting and one has
for and
The number is called the number of steps of the Euclidean algorithm, since it is the number of Euclidean divisions that are performed.
The Fibonacci numbers are defined by and
for
The above relations show that and By induction,
So, if the Euclidean algorithm requires steps, one has
One has for every integer, where is the Golden ratio. This can be proved by induction, starting with and continuing by using that
So, if is the number of steps of the Euclidean algorithm, one has
and thus
using
If is the number of decimal digits of, one has and
So,
and, as both members of the inequality are integers,
which is exactly what Lamé's theorem asserts.
As a side result of this proof, one gets that the pairs of integers that give the maximum number of steps of the Euclidean algorithm are the pairs of consecutive Fibonacci numbers.