Algorithme d'Euclide étendu (TS spé Math)

[Jon83]

Bonjour!

Je n'arrive pas à trouver une présentation pratique de l'algorithme d'Euclide étendu afin de mener les calculs à la main, sans faire d'erreur!
Si vous en avez une, elles sera la bienvenue!
-----

[sylvainc2]

Il y a deux versions de l'algo, récursive et itérative, je vais donner un exemple de la version itérative.

On veut calculer 99x + 78y = pgcd(98,78):



À chaque ligne à partir de la ligne 3, on calcule:
a_i = b_i-1
b_i = r_i-1
q_i = quotient de a_i / b_i
r_i = reste de a_i / b_i
x_i = x_i-2 - q_i x_i-1
y_i = y_i-2 - q_i y_i-1

le pgcd est le dernier r_i > 0, et x et y ceux de la même ligne, donc 99 * -11 + 78 * 14 = 3

La version récursive est un peu différente, je peux donner aussi un tableau pour son détail. Je peux aussi expliquer pourquoi l'algo fonctionne, le calcul des x_i et y_i est pas évident, pour la version itérative en tout cas.

[inviteb9469e86]

Bonjour,

Je te renvoie à cette adresse où est détaillée une méthode pour y arriver
http://storage.canalblog.com/27/79/477615/53797774.pdf
Bon courage

[Jon83]

Super! Merci pour vos réponses

[A voir en vidéo sur Futura]

[invite7d8bc1d8]

Bonjour ,

Je ne sais pas si c'est une bonne chose de donner une deuxième "vie"(je préfère dire cela à la place de "déterrer") à cette discussion
et ce malgré que Jon83 a été très satisfait des réponses qui lui ont été proposées. Si non alors j'en ouvrirai une autre page de discussion.
Cordialement.