L'algorithme d'Euclide donne le PGCD et la recette pour le fabriquer
Publié le 27/10/2026 · 3 min de lecture · Calculateurs du quotidien
Daniel Okonkwo — Développeur front-end et rédacteur Tech chez OneKitly
Performance web · Formats de fichiers
Vérifié à partir de 2 sources
L'algorithme ordinaire remplace sans cesse le plus grand nombre par son reste contre le plus petit : 252 laisse 42 contre 105, 105 laisse 21 contre 42, et 42 ne laisse rien contre 21 — le PGCD vaut donc 21. La version étendue garde la trace de la façon dont chaque reste a été construit en chemin et rend deux entiers combinant les nombres d'origine en ce diviseur — ici −2 et 5, puisque 252 × (−2) + 105 × 5 = −504 + 525 = 21. Cette combinaison existe toujours, fait appelé identité de Bézout, et c'est elle qui produit un inverse modulaire : quand le diviseur vaut un, le coefficient du premier nombre est exactement l'inverse de ce nombre modulo le second.
252 et 105 ont un PGCD de 21, et la version étendue rend aussi −2 et 5 : 252 × (−2) + 105 × 5 = 21 exactement.
Pourquoi il se termine si vite
Chaque étape remplace un couple par un couple plus petit, et la décroissance est rapide : après deux étapes, le plus grand nombre vaut au plus la moitié de ce qu'il était, car un reste est toujours plus petit que le diviseur et l'un des deux doit passer sous la moitié. Le nombre d'étapes est donc proportionnel au nombre de chiffres et non aux nombres eux-mêmes, d'où la facilité avec laquelle la méthode traite des valeurs de plusieurs centaines de chiffres. Le pire cas se trouve être celui des nombres de Fibonacci consécutifs, détail plaisant et raison pour laquelle la borne s'énonce d'ordinaire en logarithme.
Les coefficients ne sont pas uniques
Pour 240 et 46, l'algorithme rend −9 et 47, d'où 240 × (−9) + 46 × 47 = 2, et c'est une réponse parmi une infinité : ajouter vingt-trois au premier coefficient et retrancher cent vingt au second donne un autre couple valide, et ainsi de suite sans fin. L'algorithme rend le couple de plus petites amplitudes, représentant utile, et toute implémentation qui compare deux résultats doit normaliser avant de conclure qu'ils diffèrent. C'est un piège général des problèmes dont les réponses forment une famille et non un point.
| Étape | Reste |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — fin |
Questions fréquentes
- Quel âge a cette méthode ?
- Elle figure dans les Éléments d'Euclide, écrits environ trois cents ans avant notre ère, ce qui en fait le plus ancien algorithme encore d'usage courant. Rien n'y a été amélioré au sens qui compte : il existe des variantes évitant la division ou mieux adaptées au matériel binaire, mais le nombre d'étapes et l'idée sous-jacente sont inchangés. Qu'une procédure écrite pour la géométrie sur papyrus se trouve à l'intérieur de tout appareil faisant de la cryptographie à clé publique est l'une des continuités les plus frappantes du domaine.
- À quoi servent les coefficients hors des inverses ?
- À résoudre des équations en nombres entiers, usage pour lequel on les a d'abord voulus. Une équation demandant des quantités entières de deux grandeurs devant totaliser une troisième a une solution exactement quand le PGCD des deux divise la troisième, et les coefficients en donnent une directement ; les autres suivent en ajoutant des multiples d'un pas fixe. Cela couvre la composition d'un montant avec deux valeurs de pièces, la synchronisation de deux cycles répétitifs, et toute question analogue où les réponses fractionnaires sont interdites. C'est aussi la mécanique derrière la reconstitution d'une valeur à partir de plusieurs restes simultanés.
Articles qui pourraient t'intéresser
Tous les guides →Outils similaires
Sources
Tu as repéré une erreur dans cet article ?