Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme d'Euclide étendu
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.