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[1][2] that when looking for the greatest common divisor (GCD) of two integers a and b, the algorithm finishes in at most 5k steps, where k is the number of digits (decimal) of b.
[3][4] The number of division steps in the Euclidean algorithm with entries
times the number of decimal digits of
min ( u , v )
be two positive integers.
Applying to them the Euclidean algorithm provides two sequences
of positive integers such that, setting
and The number n 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
The above relations show that
By induction, So, if the Euclidean algorithm requires n steps, one has
φ
φ =
is the Golden ratio.
This can be proved by induction, starting with
φ
= 2 > φ ,
and continuing by using that
φ
So, if n is the number of steps of the Euclidean algorithm, one has and thus using
log
If k is the number of decimal digits of
log
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 (for a given size of
) are the pairs of consecutive Fibonacci numbers.