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.

Algorithme d'Euclide Etendu

Annonces sponsorisées

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 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\), on a \( \mbox{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 $$

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
© 2018 dCode — La 'boite à outils' indispensable qui sait résoudre tous les jeux / énigmes / géocaches. dCode