Algorithme d'Euclide étendu
En mathématiques, l'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide. À partir de deux entiers a et b, il calcule non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout, c'est-à-dire deux entiers u et v tels que au + bv = PGCD(a, b). Quand a et b sont premiers entre eux, u est alors l'inverse pour la multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b, modulo a), ce qui est un cas particulièrement utile. Alors que l'algorithme d'Euclide détermine quand une équation diophantienne possède une solution, l'algorithme d'Euclide étendu en fournit également une solution particulière, dont on déduit facilement la solution générale. Comme l'algorithme d'Euclide, l'algorithme étendu se généralise aux anneaux euclidiens, tels celui des polynômes à une variable sur un corps commutatif. De même que pour les entiers, il permet alors de calculer l'inverse d'un polynôme modulo un polynôme avec lequel il est premier et donc des calculs d'inverse dans les anneaux ou corps construits par quotient sur l'anneau des polynômes : corps de rupture, corps finis, etc. Considérons par exemple le calcul du PGCD de 120 et 23 avec l'algorithme d'Euclide : Dans ce cas, le reste obtenu à l'avant-dernière ligne donne le PGCD égal à 1 ; c'est-à-dire que 120 et 23 sont premiers entre eux. Maintenant présentons autrement les divisions précédentes : Observons que 120 et 23 apparaissent sur les deux premières lignes. D'autre part, la valeur la plus à droite dans chaque ligne (à partir de la du tableau) est le reste de la ligne précédente, et le dividende est — dans chaque égalité à partir de la — le reste obtenu deux lignes plus haut. Nous pouvons ainsi calculer progressivement chaque reste successif comme combinaison linéaire des deux valeurs initiales 120 et 23. Cependant cette méthode n'est pas la plus efficace. On écrit d'abord ces calculs de façon à faire apparaître un algorithme plus direct, qui est parfois attribué à W. A.