Algorithme d'Euclide étendu - Définition

Généralisations

Les entiers relatifs

On pourrait facilement ramener le calcul du pgcd et des coefficients de Bezout de deux entiers relatifs, à celui de deux entiers naturels. L'algorithme indiqué s'applique cependant sans aucune modification aux entiers relatifs. Il suffit de remarquer que, dans la division euclidienne, c'est alors la valeur absolue du reste qui est plus petite que la valeur absolue du diviseur, ce qui assure la terminaison de l'algorithme. En effet, si on définit de la même façon à partir de deux entiers relatifs a et b la suite (r_i, u_i, v_i), c'est cette fois-ci la suite des valeurs absolues des r_i qui est strictement décroissante à partir du second rang. On montre de façon identique que r_n, l'avant dernier terme de la suite, est un diviseur commun de a et de b, multiple de tout diviseur commun de a et de b, c'est-à-dire un plus grand (au sens de la divisibilité) diviseur commun de a et b, et donc le pgcd de a et b ou son opposé. Pour les mêmes raisons les nombres u_n, v_n satisfont l'identité de Bezout.

Les anneaux euclidiens

L'anneau des entiers relatifs est un anneau euclidien, et ce sont les seules propriétés utiles pour l'algorithme d'Euclide étendu. Celui-ci se généralise donc directement aux anneaux euclidiens, et se justifie de la même façon. Seules changent les opérations de base, et la division. Comme pour les entiers relatifs, il n'y a pas forcément unicité, et l'algorithme détermine un plus grand diviseur commun, les autres s'en déduisent par multiplication par une unité (1 et -1. pour les entiers relatifs). De même que pour les entiers, il peut être légèrement modifié quand le pgcd est défini de façon unique grâce à une condition supplémentaire, de façon à ce que le résultat vérifie celle-ci.