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) : Arithmétique

Partager
Partager
dCode et plus

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 !


Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !


Remarques et suggestions sont les bienvenues afin que dCode propose le meilleur outil 'Algorithme d'Euclide Etendu' gratuit ! Merci !

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". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Algorithme d'Euclide Etendu", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les 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 les données, en téléchargement, script, ou les accès API à "Algorithme d'Euclide Etendu" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.

Citation

Le copier-coller de la page "Algorithme d'Euclide Etendu" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous citez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Algorithme d'Euclide Etendu sur dCode.fr [site web en ligne], consulté le 29/03/2024, https://www.dcode.fr/euclide-etendu

Besoin d'Aide ?

Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !

Questions / Commentaires

Remarques et suggestions sont les bienvenues afin que dCode propose le meilleur outil 'Algorithme d'Euclide Etendu' gratuit ! Merci !


https://www.dcode.fr/euclide-etendu
© 2024 dCode — La 'boite à outils' indispensable qui sait résoudre tous les jeux / énigmes / géocaches / CTF.
 
Un problème ?