Aller au contenu
OneKitly

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

Daniel Okonkwo — Développeur front-end et rédacteur Tech chez OneKitly

Performance web · Formats de fichiers

Vérifié à partir de 2 sources

Voir le profil →
En bref

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.

Publicité

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.

Les étapes de division pour 252 et 105
ÉtapeReste
252 = 2 × 105 + 4242
105 = 2 × 42 + 2121
42 = 2 × 21 + 00 — fin
Calculateur de l'algorithme d'Euclide étenduExécute l'algorithme d'Euclide étendu sur deux entiers a et b : il renvoie leur plus grand commun diviseur ainsi que les coefficients de Bézout x et y vérifiant a·x + b·y = pgcd(a, b). Au-delà du pgcd, ces coefficients servent à construire les inverses modulaires et à résoudre les équations diophantiennes linéaires. Le tableau complet des divisions est affiché pour suivre chaque réduction.Essayer l'outil →
Publicité

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 ?