Lamé's theorem
Pour deux entiers positifs a et b avec b ≤ a, le théorème de Lamé borne le nombre N de divisions de l’algorithme d’Euclide produisant un reste non nul par ⌊ln b / ln φ⌋ ; si b a d chiffres en base 10, le nombre total de divisions, division terminale comprise, est au plus 5d. Les couples de nombres de Fibonacci consécutifs expliquent le pire cas : le théorème établit ainsi que le calcul du PGCD demande un nombre d’étapes logarithmique en la taille du plus petit entier.
Contents
What you will learn
- Interpréter la borne décimale de cinq fois le nombre de chiffres.
- Distinguer les réductions à reste non nul de la division terminale.
- Refaire le calcul complet du PGCD de 89 et 55.
- Relier le pire cas aux nombres de Fibonacci consécutifs et au nombre d’or.
In plain terms
Pour calculer le PGCD de 89 et 55, on divise, puis on recommence avec 55 et le reste obtenu. Les nombres diminuent jusqu’au reste nul. Le théorème de Lamé garantit que cette descente ne peut pas s’éterniser : sa longueur est contrôlée par la taille du plus petit entier.
La descente la plus lente apparaît avec deux nombres de Fibonacci consécutifs. Chaque division enlève alors le moins possible, ce qui explique le rôle du nombre d’or dans la borne précise.
Definition
Le théorème de Lamé est un résultat de complexité sur l’algorithme d’Euclide. Soient deux entiers positifs a et b, avec b ≤ a. L’algorithme remplace successivement une paire par le diviseur et le reste de sa division euclidienne, jusqu’à obtenir un reste nul. Le dernier reste non nul est le PGCD.
Si b possède d chiffres en base 10, le calcul demande au plus 5d divisions selon la borne élémentaire. La formulation logarithmique fait intervenir le nombre d’or, noté φ : . Avec N pour le nombre de réductions produisant un reste non nul, la convention de la source s’écrit :
Si l’on compte aussi la division terminale dont le reste est nul, le total vaut N + 1. Les paires de nombres de Fibonacci consécutifs rendent la descente maximale et montrent que l’ordre logarithmique ne peut pas être amélioré en général.
The principle
Si a et b sont des entiers positifs tels que b ≤ a, et si b s’écrit avec d chiffres décimaux, alors l’algorithme d’Euclide comporte au plus 5d divisions. En comptant par N les réductions à reste non nul, on dispose de la borne plus précise : , où φ est le nombre d’or. Le cas maximal est porté par deux nombres de Fibonacci consécutifs.
When to use it
La borne s’applique à deux entiers positifs a et b, ordonnés de sorte que b ≤ a. Il faut préciser la base utilisée pour compter les chiffres : le coefficient 5 concerne l’écriture décimale. Il faut aussi fixer la convention de comptage, car la division finale à reste nul ajoute une unité au nombre de réductions à reste non nul.
Le cas b = 0 ne relève pas de la formule logarithmique, puisque ln 0 n’est pas défini. Le calcul ne se poursuit pas : on utilise directement PGCD(a, 0) = |a|. Pour des entiers signés, on applique l’algorithme à leurs valeurs absolues avant d’utiliser la borne.
A step-by-step example
Prenons a = 89 et b = 55, deux nombres de Fibonacci consécutifs. Le plus petit entier possède 2 chiffres décimaux, donc la borne élémentaire autorise au plus 5 × 2 = 10 divisions. La chaîne des restes permet de suivre toutes les réductions.
1. Les quatre premières divisions donnent :
89 = 1 × 55 + 34
55 = 1 × 34 + 21
34 = 1 × 21 + 13
21 = 1 × 13 + 8
89 = 1 × 55 + 34
55 = 1 × 34 + 21
34 = 1 × 21 + 13
21 = 1 × 13 + 8
2. La descente continue :
13 = 1 × 8 + 5
8 = 1 × 5 + 3
5 = 1 × 3 + 2
3 = 1 × 2 + 1
13 = 1 × 8 + 5
8 = 1 × 5 + 3
5 = 1 × 3 + 2
3 = 1 × 2 + 1
3. La division terminale est 2 = 2 × 1 + 0. Le dernier reste non nul est 1, donc PGCD(89, 55) = 1. On compte N = 8 réductions à reste non nul, ou 9 divisions en incluant la dernière.
4. Le contrôle logarithmique donne . Le contrôle décimal donne 9 ≤ 10 avec la division terminale : les deux lectures annoncées sont respectées.
In practice
Pour prévoir le coût d’un calcul de PGCD, on regarde d’abord la taille du plus petit entier. La borne 5d fournit immédiatement un plafond simple à partir de son nombre de chiffres décimaux.
En cryptographie, où des algorithmes utilisent le PGCD, le théorème donne une garantie sur le nombre d’itérations de la procédure d’Euclide. Si l’on veut une estimation plus serrée, la borne logarithmique est préférable au plafond décimal.
Pour tester une implantation, les couples de Fibonacci consécutifs constituent des entrées révélatrices : ils forcent une longue chaîne de restes. Un couple quelconque peut terminer plus vite sans contredire le théorème, qui donne un maximum et non une durée exacte.
Not to be confused with
Le théorème de Lamé n’est pas l’algorithme d’Euclide. L’algorithme effectue les divisions et calcule le PGCD ; le théorème borne leur nombre. Sur 89 et 55, les égalités successives relèvent de l’algorithme, tandis que les plafonds 8 et 10 relèvent du théorème.
La présence des nombres de Fibonacci ne signifie pas que l’algorithme d’Euclide calcule cette suite. Ils décrivent ses entrées les plus lentes. Avec deux entiers non consécutifs dans la suite, la chaîne peut être plus courte : le critère qui tranche est le nombre effectif de restes.
Limits and pitfalls
Convention de comptage. Pour 89 et 55, il y a huit restes non nuls après les divisions et une neuvième division qui produit 0. Une comparaison numérique n’a de sens que si l’on indique laquelle de ces deux conventions est employée.
Borne, pas prédiction. Deux entiers de 2 chiffres ne demandent pas nécessairement 10 divisions. Le nombre 10 est un plafond décimal ; il ne remplace pas l’exécution de l’algorithme lorsque l’on veut connaître le nombre réel d’étapes.
Base d’écriture. Le facteur 5 est attaché au nombre de chiffres en base 10. Si les entiers sont comptés dans une autre base, il faut repartir de la borne logarithmique au lieu de conserver mécaniquement ce coefficient.
Valeur nulle. Lorsque le plus petit entier vaut 0, le logarithme utilisé dans la borne n’existe pas. Le cas se traite directement par PGCD(a, 0) = |a|, sans invoquer la formule de Lamé.
Further reading
algorithme d'Euclide — Reprendre la procédure dont le théorème mesure le nombre de divisions.
PGCD — Revoir l’objet calculé par la chaîne des restes et le rôle du dernier reste non nul.
nombre d'or — Approfondir la constante φ qui relie la croissance de Fibonacci à la borne logarithmique.
Explore mathematics differently
Discover our magazines, podcasts and games to explore mathematics differently.
See our offers