{"partition": "head_middle", "source_domain": "www.ilemaths.net", "digest": "sha1:PMNPV7RLFFVO2IWEKC46VCO2ALI45QSW", "path": "/lustre/fsn1/projects/rech/qgz/uzq54wg/processed_redpajama/base_processing/output/fr/2014-15/000_00024.parquet"}
Algorithme d'Euclide étendu
Recherche : Encyclopédie
Les définitions
Top définitions
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z toutes les définitions
Algorithme d'Euclide étendu : encyclopédie mathématiques
Cet article est issu de l'encyclopédie libre Wikipedia.Vous pouvez consulter l'article ici ainsi que son historique.Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.
L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet, à partir de deux entiers a et b, de calculer non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout (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. L'algorithme d'Euclide étendu fournit également une méthode efficace non seulement pour déterminer quand une équation diophantienne ax+by = c possède une solution, ce que permet déjà l'algorithme d'Euclide simple, mais également pour en calculer dans ce cas 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…
1 Exemple introductif
2 L'algorithme
3 Complexité de l'algorithme
4 Généralisations