Algorithme euclide spé maths

[mimi_chokoolat]

bonjour a tous, voila jaurais besoin de quelques pistes sur cet exo...



cet exo présente une variante de lagorithme deuclide bcp plus proche de celle developpee par euclide

1) on suppose que a et b sont deux entiers naturels avc a>b
montrer que pgcd (a,b)= pgcd(a-b,b)

2) en deduire un moyen ne mettant en oeuvre que des soustractions pour calculer pgcd (90,72)

3)Calculer pgcd (2566,2155) en utilisant cette methode dite des soustractions" puis en utilisant llgorithme deuclide.
lequel de ces deux algorithme est le plus rapides?



par avance merci

[Imod]

Pour la première question il suffit de remarquer que a et b ont les mêmes diviseurs communs que a-b et b ( en raisonnant dans un sens puis dans l'autre ) .

Imod

[mimi_chokoolat]

Pour la première question il suffit de remarquer que a et b ont les mêmes diviseurs communs que a-b et b ( en raisonnant dans un sens puis dans l'autre ) .

Imod

je ne comprend pas tres bien....en "raisonant ds un sens puis ds lotre"....

[Imod]

en "raisonant ds un sens puis ds lotre"....

J'espère que je ne l'ai pas écrit comme ça :doh:

Si x divise a et b alors x divise a et a-b .
Si x divise a-b et b alors x divise a et b .

Imod

[mimi_chokoolat]

[FONT=Comic Sans MS]ok!! jai compris (ya fallu du temps lol)
et en plus jai reussi a trouver la methode des soustractions (un peu relou les calculs mais bon..) merci à tous pour votre aide!!!!
bonne journée
mimi[/FONT]

[Imod]

Le plus simple est de voir sur un exemple . PGCD(40;15) .

Méthode des soustractions :

40 - 15 = 25 donc PGCD(40;15) = PGCD(25;15)
25 - 15 = 10 donc PGCD(25;15) = PGCD(10;15) = PGCD(15;10)
15 - 10 = 5 donc PGCD(15;10) = PGCD( 5;10) = 5 .

Méthode d'Euclide :

40:15 = 3 reste 10 donc PGCD(40;15) = PGCD(15;10)
15:10 = 1 reste 5 donc PGCD(15;10) = PGCD(10;5) = 5 .

Imod

[mimi_chokoolat]

ok ok jai bien capter! ya pas de doute euclide est plus rapide!!! :)
:++: merci beaucoup Imod pour ton aide!!!
bonnne journée