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

[Anonyme]

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]

"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]

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/

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