Une variante de l'algorithme d'Euclide qui, pour deux entiers a et b, calcule leur plus grand commun diviseur g et fournit aussi des entiers x et y tels que ax + by = g (coefficients de Bézout).

Principe

Appliquer itérativement la division euclidienne entière en propageant des coefficients de combinaison linéaire de sorte qu'à chaque étape le reste courant soit conservé comme combinaison entière explicite des entrées d'origine.

Démonstration

Pour gcd(240, 46) : les divisions successives donnent des restes, puis la rétrosubstitution fournit 240·(−9) + 46·47 = 2 ; on obtient g = 2 et les coefficients x = −9, y = 47 exprimant le gcd comme combinaison linéaire.

Mauvaise application

Employer l'algorithme sans discernement sur des données non entières ou sur des structures sans division euclidienne appropriée (par exemple des anneaux arbitraires) donne des coefficients sans sens ; une autre erreur est de croire que les coefficients retournés sont uniques et minimalement normés sans tenir compte des unités.

Conséquence

Bien appliqué aux entiers, il fournit des coefficients de Bézout, permet de calculer des inverses modulaires lorsque gcd = 1, et donne une méthode constructive pour résoudre des équations diophantiennes linéaires et pour comprendre les idéaux dans les domaines principaux.

Inversion

L'algorithme d'Euclide simple qui rend seulement le gcd sans suivre la propagation des coefficients ; inverser la variante étendue revient à supprimer le suivi des coefficients et à perdre l'information de combinaison linéaire explicite.

Limite

Défini pour les entiers et, plus généralement, dans les domaines euclidiens ou les domaines principaux munis d'une division euclidienne significative ; il ne s'applique pas directement aux anneaux commutatifs généraux sans division euclidienne ni aux réels/complexes sans adaptation à une notion analytique de division.

Tension sémantique

S'oppose conceptuellement aux méthodes par exponentiation modulaire pour obtenir des inverses en algorithmique (qui reposent sur l'arithmétique modulaire et des propriétés de groupes) et aux méthodes d'algèbre linéaire pour résoudre des équations ; l'algorithme étendu est exact et discret, alors que d'autres méthodes peuvent être approximatives ou requérir une structure de corps.

Synthèse

Extension constructive de la procédure euclidienne qui conserve à chaque étape des coefficients entiers explicites reliant les restes aux entrées, fournissant à la fois le pgcd et les coefficients de Bézout utilisables pour les inverses et les solutions diophantiennes.