So, if the Euclidean algorithm requires n 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 n is the number of steps of the Euclidean algorithm, one has
and thus
using
If k 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 (for a given size of ) are the pairs of consecutive Fibonacci numbers.
References
^Lamé, Gabriel (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes rendus des séances de l'Académie des Sciences (in French). 19: 867–870.
Bach, Eric (1996). Algorithmic number theory. Jeffrey Outlaw Shallit. Cambridge, Mass.: MIT Press.
ISBN0-262-02405-5.
OCLC33164327
Carvalho, João Bosco Pitombeira de (1993). Olhando mais de cima: Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, São Paulo, n. 24, p. 32-40, 2 sem.