Algorithme d'Euclide, théorème de Bézout

Forum d'archive d'entraide mathématique
Anonyme

algorithme d'Euclide, théorème de Bézout

par Anonyme » 30 Avr 2005, 17:37

Bonjour,

j'ai besoin d'un peu d'aide.

Tout d'abord, je dois déterminer le PGCD de a=77982 et de b=9225 en
utilisant l'algorithme d'Euclide. De ce côté là, pas de problèmes, je trouve
123.

Ensuite c'est là où je suis embêté car je n'ai pas de méthode rigoureuse.
Je dois déterminer des éléments u et v de Z tels que au+bv=PGCD (a,b) ce qui
est si je ne m'abuse l'identité de Bézout.

Quelle est la méthode pour trouver ces entiers relatifs ? (77982u+9225v=123)

Merci

JD



Anonyme

Re: algorithme d'Euclide, théorème de Bézout

par Anonyme » 30 Avr 2005, 17:37

"JD" wrote:

>Bonjour,
>
>j'ai besoin d'un peu d'aide.
>
>Tout d'abord, je dois déterminer le PGCD de a=77982 et de b=9225 en
>utilisant l'algorithme d'Euclide. De ce côté là, pas de problèmes, je trouve
>123.
>
>Ensuite c'est là où je suis embêté car je n'ai pas de méthode rigoureuse.
>Je dois déterminer des éléments u et v de Z tels que au+bv=PGCD (a,b) ce qui
>est si je ne m'abuse l'identité de Bézout.
>
>Quelle est la méthode pour trouver ces entiers relatifs ? (77982u+9225v=123)
>
>Merci
>
>JD
>



Chercher sur google "algorithme euclide étendu" ex:
http://www.jura.ch/lcp/cours/dm/codage/rabin/euclide.html
http://www.bibmath.net/crypto/complements/algoeuclid.php3

Anonyme

Re: algorithme d'Euclide, théorème de Bézout

par Anonyme » 30 Avr 2005, 17:37

On Sun, 28 Sep 2003 17:54:27 +0200, "JD" wrote:

>Bonjour,
>
>j'ai besoin d'un peu d'aide.
>
>Tout d'abord, je dois déterminer le PGCD de a=77982 et de b=9225 en
>utilisant l'algorithme d'Euclide. De ce côté là, pas de problèmes, je trouve
>123.
>
>Ensuite c'est là où je suis embêté car je n'ai pas de méthode rigoureuse.
>Je dois déterminer des éléments u et v de Z tels que au+bv=PGCD (a,b) ce qui
>est si je ne m'abuse l'identité de Bézout.
>
>Quelle est la méthode pour trouver ces entiers relatifs ? (77982u+9225v=123)
>

le 1er reste est une combi de a et b
le 2ième reste est une combi de b et du 1er reste donc une combi de a
et b
etc
tout reste est une combi de a et b
donc le dernier reste, soit le pgcd

en pratique il suffit d'écrire successivement ces combi
(on y voit peut être plus clair en ne remplacant pas a et b par leurs
valeurs )
pour avoir celle cherchée ;
on peut aussi remonter les calculs : question de goût
ex
a=784 b=77
784=77*10+14
77=14*5+7
14=7*2+0
le pgcd=7
14=a-10*b
7=b-5*(a-10*b)=51b-5a

*****************

Pichereau Alain

adresse mail antispam : ôter antispam et les 3 lettres devant wana

http://perso.wanadoo.fr/alain.pichereau/

*****************

 

Retourner vers ♲ Grenier mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite