théorème de Lamé

CALCUL

Le théorème de Lamé établit que le nombre d’étapes de l’algorithme d’Euclide exécuté sur deux entiers est borné (supérieurement) par cinq fois le nombre de chiffres nécessaire à écrire (en base 10) le plus petit de ces deux entiers.
Et plus précisément, le nombre d’étapes de l’algorithme d’Euclide exécuté sur deux entiers a et b, avec b ≤ a , est majoré par la partie entière de ln b/ ln φ, où φ est le nombre d’or .
De plus, cette majoration est la meilleure possible, elle est atteinte quand a et b sont deux nombres de Fibonacci consécutifs, cas dans lequel le nombre d’itérations est le plus grand.
Ce théorème est utilisé en cryptographie.