SPE : Remonter un algorithme d'Euclide

Salut!
En relisant ma spé. pour demain, je me suis rendu compte que je n'arrivais pas à remonter l'algorithme d'Euclide pour trouver u et v dans une égalité de Bezout du type :


Voici l'exemple qui me bloque :
a = 165 et b = 56

165 = 2*56 + 53
56 = 1*53 + 3
53 = 17*3 + 2
3 = 2*1 + 1
Le reste vaut 1 donc le PGCD(a;b) = 1 donc ils sont premiers donc on peut appliquer l'égalité de Bezout.

Pour trouver u et v, je remonte l'égalité de Bezout :

1 = 3 - 1*2
1 = 3 - 1*(53 - 17 *3)
1 = 3 - 1*(53 - 17 *(56 - 1*53))
1 = 3 - 1*(53 - 17 *(56 -1*(165-2*56))

A partir de là, je ne vois pas comment procéder pour trouver u et v...
J'aurais donc besoin qu'on m'explique cela svp.
Merci d'avance!

Pourquoi tu ne simplifies pas au fur et à mesure ? Enfin c'est comme ça que je fais, au moins tu t'y perds pas.

1 = 3 - 1*2
1 = 3 - 1 * (53 - 17*3)
1 = -1*53 + 18*3
1 = -1*53 + 18*(56 - 1*53)
1 = 18*56 - 19*53

etc et au final je trouve qu'une solution de l'équation 165u + 56v = 1 est :



Bonne chance pour demain.

Bonsoir,

En fait, on cherche u et v tels que a*u + b*v=1 lorsque pgcd(a,b)=1

Donc lrosqu'on remonte l'algorithme d'Euclide, il faut toujours garder a et b en évidence et on ne cherche que les coefficients de ces deux quantité.


Alors tu arrive à ça:

Citation :

1 = 3 - 1*(53 - 17 *(56 -1*(165-2*56))

Cependant, tu as oublié certain changment. En effet, il reste le 3 devant qui n'estp as exprimé en fonction de 165 et 56 ce qui n'estp as normal et de même pour 53.

En fait l'algorithme d'euclide c'est: t=q*p+r et lorsqu'on remonte, on écrit r=t-q*p.

C'est exactement ce que tu penses et c'est exactement ce qu'il ne faut pas faire!!! En effet, t et p sont eu-même le reste d'une division euclidienne et s'exprime donc comme des différences et ainsi de suite jusqu'à retrouver a et b.

En fait sur ton exemple on a l'algorithme d'Euclide qui nous donne:

Citation :

165 = 2*56 + 53
56 = 1*53 + 3
53 = 17*3 + 2
3 = 1*2 + 1

En mettant ainsi des couleur tu vois exactement tout ce qui va changer. Je laisse les couleurs dans les étapes de remontée (le but étant de ne plus avoir de couleur à la fin sauf le 1 qui est le pgcd):

1=3-1*2
1=3-1*[53 - 17*3] (il n'y a plus de marron mais attetnion il y a deux 3 en vert !!)
1=[ 56 - 1*[ 53 ] - 1*[ 53 - 17*[ 56 - 1*53 ] ] (là il n'y a plus de vert! mais attention il y a trois 53 bleu !!!)

1=[ 56 - 1*[ 165 - 2*56 ] ] - 1*[ [165 - 2*56] - 17*[ 56 - 1*[ 165 - 2*56 ] ] ] (il n'y a plus de couleurs mis à part le 1 et il n'y a plus que des 56 et des 165 qui ont des facteurs qu'il faut calculer maintenant)

1=56 - 165 + 2*56 - 1*[ 165 - 2*56 - 17*[ 56 - 165 + 2*56 ] ]
Donc:
1=56 - 165 + 2*56 - 1*[ 165 - 2*56 - 17*56 + 17*165 - 34*56 ]
D'où
1=56 - 165 + 2*56 - 165 + 2*56 + 17*56 - 17*165 + 34*56

Conclusion: 1=56*56 - 19*165


Il y a un moyen plus rapide qui évite de se poser trop de question. Il s'agit d'effectuer les claculs au fur et à mesure en fait:

1=3-1*2
1=3-1*[53 - 17*3]
Donc:
1=3-53 + 17*3
D'où:
1=18*3-53

1=18*[ 56 - 1*53 ]-53
Donc:
1=18*56 - 18*53 ]-53
D'où:
1=18*56 - 19*53 ]

1=18*56 - 19*[ 165 - 2*56 ]
Donc:
1=18*56 - 19*165 + 38*56

Conclusion: 1=56*56 - 19*165

On trouve donc u=-19 et v=56

Est-ce plus clair ainsi?

Merci à vous deux pour vos réponses.
En fait, je ne voyais pas comment passer de ceci :

1 = 3 - 1*2
1 = 3 - 1 * (53 - 17*3)
à cela :
1 = -1*53 + 18*3

mais l'histoire de simplification et autre m'a permis d'y voir plus clair donc le problème semble réglé donc merci à vous deux .



PS : Nakor bonne chance à toi aussi.