Algorithme d'Euclide étendu
Description
Bonjour chers utilateurs de CodeS-SourceS,
Je vous propose un petit code Python de calcul concernant l'algorithme d'Euclide étendu :
(Merci à qui a rédigé la page web :
url{http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu}) dont j'ai
appliqué l'algorithme et dont je reprends le texte de début
(voir pdf joint en plus digeste) :
L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet,
à partir de deux entiers a et b, de calculer non seulement leur plus grand commun
diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout
(deux entiers u et v tels que au + bv = PGCD(a, b)).
Quand a et b sont premiers entre eux, u est alors l'inverse pour la
multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b,
modulo a), ce qui est un cas particulièrement utile.
L'algorithme d'Euclide étendu fournit également une méthode efficace non
seulement pour déterminer quand une équation diophantienne ax+by = c
possède une solution, ce que permet déjà l'algorithme d'Euclide simple,
mais également pour en calculer dans ce cas une solution particulière,
dont on déduit facilement la solution générale.
Bonne journée ou bonne soirée,
hbouia
Je vous propose un petit code Python de calcul concernant l'algorithme d'Euclide étendu :
(Merci à qui a rédigé la page web :
url{http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu}) dont j'ai
appliqué l'algorithme et dont je reprends le texte de début
(voir pdf joint en plus digeste) :
L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet,
à partir de deux entiers a et b, de calculer non seulement leur plus grand commun
diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout
(deux entiers u et v tels que au + bv = PGCD(a, b)).
Quand a et b sont premiers entre eux, u est alors l'inverse pour la
multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b,
modulo a), ce qui est un cas particulièrement utile.
L'algorithme d'Euclide étendu fournit également une méthode efficace non
seulement pour déterminer quand une équation diophantienne ax+by = c
possède une solution, ce que permet déjà l'algorithme d'Euclide simple,
mais également pour en calculer dans ce cas une solution particulière,
dont on déduit facilement la solution générale.
Bonne journée ou bonne soirée,
hbouia
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.