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

Soit an 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.