Algorithme d'Euclide étendu

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

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.

Algorithme d'Euclide étendu

Premier entier

Deuxième entier

Calculer

Plus grand diviseur commun

 

Coefficient pour le plus grand des entiers

 

Coefficient pour le plus petit des entiers

 

 Lien  sauvegarder  Widget

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 pour une paire , telle que :

,

et nous devons calculer les coefficients pour la paire , telle que :

Tout d'abord, nous remplaçons par :

, où

- quotient de la division entière de b par a,

et nous l'utilisons pour substituer :

Ensuite, après regroupement, nous obtenons :

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

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.