Une procédure itérative fondée sur la division qui calcule un plus grand commun diviseur (pgcd) de deux éléments dans un domaine euclidien (ou tout anneau muni d’une fonction euclidienne adaptée) en effectuant des restes successifs jusqu’à l’arrêt sur zéro.

Principe

Utiliser l’opération de division avec reste pour produire une suite strictement décroissante de normes euclidiennes ; la terminaison donne le dernier reste non nul comme pgcd, et la rétro-substitution fournit des coefficients de Bézout lorsque cela est pertinent.

Démonstration

Exemple entier : pgcd(1071,462). Calculs : 1071 = 462·2 + 147, 462 = 147·3 + 21, 147 = 21·7 + 0 ; le dernier reste non nul est 21, donc pgcd(1071,462)=21. L’algorithme étendu donne des entiers x,y tels que 1071x+462y=21.

Mauvaise application

Appliquer l’algorithme de division dans des anneaux dépourvus de fonction euclidienne ou supposer que l’algorithme fournit des pgcd uniques dans des anneaux sans propriété de norme appropriée ; aussi supposer la terminaison sans vérifier une mesure strictement décroissante.

Conséquence

Fournit une méthode effective pour calculer des pgcd, déterminer l’inversibilité modulo un élément et produire des représentations de Bézout via l’algorithme étendu ; sous-tend les inverses modulaires et de nombreuses procédures algorithmiques en théorie des nombres.

Inversion

Plutôt que de réduire par restes, on peut synthétiser un pgcd en factorisant les deux éléments et en intersectant les multiensembles de facteurs ; cette inversion échange une réduction itérative contre une analyse factorielle globale.

Limite

Valable dans les domaines euclidiens (par ex. Z, F[x]) ou dans des contextes équipés d’une valuation euclidienne ; exclut les anneaux sans algorithme de division ni norme bien fondée et nécessite des ajustements (pseudo-division) sur des anneaux de coefficients plus généraux.

Tension sémantique

Souvent confondu avec des constructions de pgcd plus générales (pgcd idéaux, algorithmes de sous-résultants) ou avec les variantes étendues vs classiques ; tension entre l’usage pour des pgcd algébriques exacts et des approximations numériques.

Synthèse

L’algorithme euclidien est la procédure de divisions successives avec reste pilotée par une valuation euclidienne ; il termine en un nombre fini d’étapes pour produire le pgcd et, par rétro-substitution, des coefficients de Bézout lorsque le domaine le permet.