homechevron_rightLas étudechevron_rightMathchevron_rightGéométrie

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

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
 
Enregistrez le calcul pour le réutiliser la prochaine fois, pour extension l'intégrer dans votre site Web ou share le partager avec vos amis.

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_1y = 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.

commentaires