〜 ★ dCode présente ★ 〜

Algorithme d'Euclide Etendu

Résultats
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.

Calculatrice selon Euclide Etendu



Réponses aux Questions

Qu'est ce que l'algorithme d'Euclide étendu ?

L'algorithme d'Euclide étendu est une modification de l'algorithme d'Euclide classique. 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 :
fonction euclide_etendu(a, b) { // a,b entiers naturels
r1 = a, r2 = b, u1 = 1, v1 = 0, u2 = 0, v2 = 1
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 du script Algorithme d'Euclide Etendu en ligne. Sauf code licence open source explicite (indiqué Creative Commons / gratuit), tout algorithme, applet, snippet ou logiciel (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toute fonction (convertir, résoudre, décrypter, encrypter, déchiffrer, chiffrer, décoder, traduire) codé en langage informatique (PHP, Java, C#, Python, Javascript, Matlab, etc.) dont dCode a les droits ne sera pas cédé gratuitement. Pour télécharger le script en ligne Algorithme d'Euclide Etendu pour un usage hors ligne, PC, iPhone ou Android, demandez un devis sur la page de contact !

Questions / Commentaires


dCode aime toutes les remarques et commentaires pertinents, pour avoir une réponse, laisser un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de Algorithme d'Euclide Etendu, Merci.

Source : https://www.dcode.fr/euclide-etendu
Un problème ?