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) : Mathématiques
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 !
Annonces sponsorisées
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.
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 $$
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
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 $$
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, rendez-vous sur la page de contact !