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
 

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
PLANETCALC, Algorithme d'Euclide étendu

commentaires