Il n’y a pas plus de … dans l’algorithme d’Euclide

Soit a_n le plus petit nombre d’un couple pour lequel l’algorithme d’Euclide exige n étapes. On a

Tous les termes de la suite décroissante sont supérieurs à 1 et , donc . En remontant à partir de l’inégalité , on a , chaque vaut au moins le n-ième terme de la suite de Fibonacci  :

.

En attaquant sur on obtient

.

Ceci signifie que le terme a au moins un chiffre de plus que . Comme a 1 chiffre pour n compris entre 0 et 5 (compris), a au moins 2 chiffres pour n compris entre 5 et 10… a au moins k+1 chiffres pour , donc si on revient sur il a également au moins 5(k+1) chiffres qui est plus grand que n. Le nombre n d’étapes est donc bien inférieur ou égal à 5 fois le nombre de chiffres du plus petit des deux nombres.