Soustraction successive , pgcd

[Amelia59150]

Bonjours ,
est-ce que quelqu'un connaitrait la demonstration des soustraction successive pour calculer le PGCD
aPGCD (a;b) = PGCD (b;a-b)

[oscar]

Soit 60 et 36

60 - 36 = 24

36 - 24 = 12

24 - 12 = 12

12 - 12 =0

Donc le pgcd est 12 ( dernier reste non nul)

[Anonyme]

Soit 60 et 36

60 - 36 = 24

36 - 24 = 12

24 - 12 = 12

12 - 12 =0

Donc le pgcd est 12 ( dernier reste non nul)

Euh je suis désolé mais ceci n'est pas une démonstration:ptdr: ça c'est un exemple
Dans une démonstration on utilise des variables.
J'essaierai d'y réfléchir...un peu plus tard...
A+
96IAP2010

[Sve@r]

Dans une démonstration on utilise des variables.
J'essaierai d'y réfléchir...un peu plus tard...

Soient deux nombres a et b et m diviseur commun
m divise a donc a=km
m divise b donc b=k'm

Et donc a-b = m(k - k'). Ainsi on démontre que m divise aussi a - b. Ne reste plus qu'à démontrer que m est le plus grand diviseur possible. Je pense qu'on peut y arriver en raisonnant par récurrence...

[Anonyme]

[quote="Amelia59150"]Bonjour ,
est-ce que quelqu'un connaitrait la démonstration des soustractions successives pour calculer le PGCD
ab et pas le contraire.

Je m'excuse car je n'ai toujours pas trouvé de démonstration pour cette propriété mais si ça intéresse quelqu'un :

J'ai la démonstration de l'algorithme d'Euclide pour trouver le PGCD :

(ce qui est entre crochets est censé être en indice)

Soient a et b deux nombres tel que a>b ainsi que q1 le quotient de la division euclidienne de a par b et r1 le reste de cette division :

a=b*q[1]+r[1]

On part de la propriété PGCD(a;b) = PGCD(b;r[1])

D'où b=r[1]*q[2]+r[2] ==> PGCD(a;b) = PGCD(r[1];r[2])...

On continue comme cela en mettant le diviseur de la division en dividende et le reste en diviseur :
r[1]=r[2]*q[3]+r[3]
r[2]=r[3]*q[4]+r[4]....

r[k-3]=r[k-2]*q[k-1]+r[k-1] ==> PGCD(a;b) = PGCD(r[k-2];r[k-1])

r[k-2]=r[k-1]*q[k]+r[k] Quand r[k]=o on a

r[k-2]=r[k-1]*q[k] ==> PGCD(a;b) = PGCD(r[k-1];0).

Or le PGCD de deux nombres dont l'un est égal à 0 est l'autre nombres :

PGCD(r[k-1];0) = r[k-1].

D'où PGCD(a;b) = r[k-1].

Voilà.

A+

96IAP2010

PS : Je n'ai pas réussi à mettre des balises spoiler

[Anonyme]

Ah aussi pour ceux qui ne connaissent pas cette méthode de détermination du PGCD je rajoute un exemple car j'ai conscience que ma démonstration n'est peut être pas très claire :

Soient a ==> 60 et b ==> 36 :

60=36*1+24
36=24*1+12
24=12*2+0 ==> 24=12*2 ==> PGCD(a;b) = PGCD(60;36) = 12 (dernier diviseur)