CodeS-SourceS
Rechercher un code, un tuto, une réponse

Algorithme d'Euclide étendu

Soyez le premier à donner votre avis sur cette source.

Vue 423 fois - Téléchargée 32 fois

Cette source est considérée comme dangereuse, elle a néamoins été gardée dans un but pédagogique :

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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Donnez votre avis

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.