PLANETCALC Calculatrices en ligne

S'identifier
Las étudeMath

Algorithme d'Euclide étendu

Ce calculateur met en oeuvre l'algorithme d'Euclide étendu qui calcule, en plus du plus grand diviseur commun de deux entiers a et b, l'identité des coefficients de Bézout

Cette page existe grâce aux efforts des personnes suivantes :

Timur

Timur

GM

Gaulthier Marrel

Créé: 2017-12-10 03:32:41, Dernière mise à jour: 2020-11-03 14:19:34
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Ce contenu est sous License Creative Commons Attribution/Partage à l'Identique 3.0(Unported). Cela signifie que vous pouvez redistribuer ou modifier librement ce contenu avec les mêmes modalités de licence et que vous devez créditer l'auteur original en plaçant un lien hypertexte de votre site vers l'œuvre https://fr.planetcalc.com/3298/. Vous ne pouvez pas modifier (le cas échéant) les références dans le contenu de l'œuvre originale.

Ce site possède déjà Le plus grand diviseur commun de deux entiers, qui utilise l'algorithme d'Euclide. Il s'avère (dans mon cas), qu'il existe l'algorithme d'Euclide étendu. Cet algorithme calcule, en plus de plus grand diviseur commun de deux entiers a et b, l'identité des coefficients de Bézout, qui sont les entiers x et y tels que

ax + by = {\rm gcd} (a, b)

Ainsi, il permet de calculer les quotients de a et b et leur plus grand diviseur commun.

Vous pouvez voir le calculateur ci-après et la théorie est comme d'habitude en-dessous du calculateur.

PLANETCALC, Algorithme d'Euclide étendu

Algorithme d'Euclide étendu

Plus grand diviseur commun
 
Coefficient pour le plus grand des entiers
 
Coefficient pour le plus petit des entiers
 

L'algorithme étendu utilise une récursions et calcule les coefficients avec un retour sur trace. Les formules de calculs peuvent être obtenues grâce aux considérations suivantes :

Faites-nous savoir les coefficients (x_1,y_1) pour une paire (b\%a,a), telle que :

(b \% a)x_1 + ay_1 = g,

et nous devons calculer les coefficients pour la paire (a,b), telle que :

ax + by = g

Tout d'abord, nous remplaçons b\%a par :

b\%a = b - \left\lfloor \frac{b}{a} \right\rfloor a, où

\left\lfloor \frac{b}{a} \right\rfloor - quotient de la division entière de b par a,

et nous l'utilisons pour substituer :

g = (b \% a) x_1 + a y_1 = \left( b -\left\lfloor \frac{b}{a} \right\rfloor a\right) x_1 + ay_1

Ensuite, après regroupement, nous obtenons :

g = bx_1 + a \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1\right)

En comparant cela avec les équations de départ, nous pouvons exprimer x et y :

x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1
y = x_1

Le début de la récursion avec retour sur trace représente la fin de l'algorithme d'Euclide, lorsque a = 0 et PGCD = b, ainsi x et y sont tout d'abord respectivement 0 et 1. Les autres coefficients sont calculés en utilisant les formules ci-dessus.

URL copiée dans le presse-papiers

Calculatrices similaires

 algorithme d'Euclide Algorithme d'Euclide étendu algorithme euclidien identité de Bézout Math PGCD plus grand diviseur commun
PLANETCALC, Algorithme d'Euclide étendu
Timur2020-11-03 14:19:34

commentaires