Maths Cuicui, l'envolée mathématique

forum gratuit d'entraide mathématique de la 6ème à la 2ème année de licence
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 SPE : Remonter un algorithme d'Euclide

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
MrTheYo



Nombre de messages : 1062
Localisation : FRANCE
Date d'inscription : 20/11/2007

MessageSujet: SPE : Remonter un algorithme d'Euclide   Lun 22 Juin - 15:51

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 :
au + bv = 1


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!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nakor



Masculin Nombre de messages : 200
Age : 25
Localisation : Universe
Date d'inscription : 23/06/2008

MessageSujet: Re: SPE : Remonter un algorithme d'Euclide   Lun 22 Juin - 16:17

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 :

u = -19 et v=56


Bonne chance pour demain.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Blagu'cuicui
Admin'cuicui


Masculin Nombre de messages : 5009
Age : 30
Localisation : Bretagne (35)
Date d'inscription : 03/09/2007

MessageSujet: Re: SPE : Remonter un algorithme d'Euclide   Lun 22 Juin - 16:56

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?

_________________
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.maths-cuicui.fr
MrTheYo



Nombre de messages : 1062
Localisation : FRANCE
Date d'inscription : 20/11/2007

MessageSujet: Re: SPE : Remonter un algorithme d'Euclide   Lun 22 Juin - 17:18

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 Very Happy .



PS : Nakor bonne chance à toi aussi.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: SPE : Remonter un algorithme d'Euclide   Aujourd'hui à 16:04

Revenir en haut Aller en bas
 
SPE : Remonter un algorithme d'Euclide
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» L'algorithme du cycle des empires
» algorithme
» Un algorithme écologique
» [Salon] L'algorithme.
» Equation de Pythagore : Euclide vs Diophante !!!

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Maths Cuicui, l'envolée mathématique :: L'envolée du Lycée GT, Pro et du CAP :: Entre-aide pour la Terminale G, T et Pro :: Problèmes et exercices-
Sauter vers: