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
![Creative Commons Attribution/Share-Alike License 3.0 (Unported)](/img/lic/by-sa.png)
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
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.
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.
Calculatrices similaires
- • Le plus grand diviseur commun de deux entiers
- • Coefficients de Bézout
- • Le plus grand diviseur commun et le plut petit multiple commun de deux entiers
- • Le Plus Grand Commun Diviseur (PGCD) et le Plus Petit Commun Multiple (PPCM) de plusieurs nombres
- • Inverse modulaire
- • Section Math ( 196 calculatrices )
commentaires