Rechercher un outil
Algorithme d'Euclide Etendu

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.

Résultats

Algorithme d'Euclide Etendu -

Catégorie(s) : Mathématiques

dCode et vous

dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les énigmes et les problèmes à résoudre au quotidien !
Vous avez un problème, une idée de projet, besoin d'un outil spécifique et dCode ne peut pas (encore) vous aider ? Vous désirez une prestation de développement sur mesure ? Contactez-moi !


dCodeur lit tous les messages et y répond si vous indiquez un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de Algorithme d'Euclide Etendu, Merci.

dCode est désormais sécurisé en HTTPS, merci de signaler toute anomalie

Algorithme d'Euclide Etendu

Annonces sponsorisées

Cet outil a été mis à jour, merci de signaler tout problème.

Calculatrice selon Euclide Etendu



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.

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 naturelshref a et b ses étapes permettent de calculer leur PGCDhref et leurs coefficients de Bézout (voir l'identité de Bezouthref).

Exemple : Soit \(a=12\) et \(b=30\), on a \( \mbox{pgcdhref}(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 naturelshref
r1 = a, r2 = b, u1 = 1, v1 = 0, u2 = 0, v2 = 1
tant que (r2 != 0) faire
q = r1÷r2 (divisionhref 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 naturelhref et u1, v1 entiers relatifshref)

Les valeurs sont telles que r1 = pgcd(a, b) = a*u1+b*v1

Poser une nouvelle question

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, etc.) dont dCode a les droits pourra être cédé après devis. Donc si vous avez besoin de télécharger le script en ligne Algorithme d'Euclide Etendu pour un usage hors ligne pour vous, votre entreprise ou association, rendez-vous sur la page de contact !

Questions / Commentaires


dCodeur lit tous les messages et y répond si vous indiquez 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
© 2017 dCode — La 'boite à outils' indispensable qui sait résoudre tous les jeux / énigmes / géocaches. dCode