Outil pour appliquer l'algorithme d'Euclide étendu afin de retrouver les valeurs des coefficients de Bézout et la valeur du PGCD de 2 nombres.
Algorithme d'Euclide Etendu - dCode
Catégorie(s) : Arithmétique
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Algorithme d'Euclide Etendu
Calculatrice selon Euclide Etendu
Réponses aux Questions (FAQ)
Qu'est ce que l'algorithme d'Euclide étendu ? (Définition)
L'algorithme d'Euclide étendu est une modification de l'algorithme d'Euclide classique génération une combinaison linéaire. A partir de 2 entiers naturels a et b ses étapes permettent de calculer leur PGCD et leurs coefficients de Bézout (voir l'identité de Bezout).
Exemple : Soit $ a=12 $ et $ b=30 $, avec $ pgcd(12, 30) = 6 $
$$ 12 \times -10 + 30 \times 3 = 6 \\ 12 \times -3 + 30 \times 1 = 6 \\ 12 \times 4 + 30 \times -1 = 6 \\ 12 \times 11 + 30 \times -3 = 6 \\ 12 \times 18 + 30 \times -5 = 6 \\ 12 \times −2+30 \times 1 = 6 $$
Comment programmer l'algorithme d'Euclide ?
Voici une implémentation de l'algorithme en pseudo-code permettant de trouver la combinaison linéaire pgcd(a,b) = a.u+b.v :
fonction euclide_etendu(a, b) { // a,b entiers naturels a < b
r1 = b, r2 = a, u1 = 0, v1 = 1, u2 = 1, v2 = 0
tant que (r2 != 0) faire
q = r1÷r2 (division entiere)
r3 = r1, u3 = u1, v3 = v1,
r1 = r2, u1 = u2, v1 = v2,
r2 = r3 - q*r2, u2 = u3 - q*u2, v2 = v3 - q*v2
fin tant que
retourner (r1, u1, v1) (r1 entier naturel et u1, v1 entiers relatifs)
Les valeurs sont telles que r1 = pgcd(a, b) = a*u1+b*v1
Comment fonctionne l'algorithme d'Euclide avec des nombres négatifs ?
En utilisant les valeurs absolues pour a et b, le reste du calcul est identique grace à la propriété : $$ a(\text{signe}(a)\cdot x)+b(\text{signe}(b)\cdot y)=1 $$
Code source
dCode se réserve la propriété du code source pour "Algorithme d'Euclide Etendu". Tout algorithme pour "Algorithme d'Euclide Etendu", applet ou snippet ou script (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toutes fonctions liées à "Algorithme d'Euclide Etendu" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou toute base de données, ou accès API à "Algorithme d'Euclide Etendu" ou tout autre élément ne sont pas publics (sauf licence open source explicite type Creative Commons). Idem avec le téléchargement pour un usage hors ligne sur PC, mobile, tablette, appli iPhone ou Android.
Rappel : dCode est une ressource éducative et pédagogique, accessible en ligne gratuitement et pour tous.
Citation
Le contenu de la page "Algorithme d'Euclide Etendu" ainsi que ses résultats peuvent être copiés et réutilisés librement, y compris à des fins commerciales, à condition de mentionner dCode.fr comme source.
L'export des résultats est gratuit et se fait simplement en cliquant sur les icônes d'export ⤓ (format .csv ou .txt) ou ⧉ copier-coller.
Pour citer dCode.fr sur un autre site Internet, utiliser le lien :
Dans un article scientifique ou un livre, la citation bibliographique recommandée est : Algorithme d'Euclide Etendu sur dCode.fr [site web en ligne], consulté le 16/04/2025,
