Arithmétique et PGCD

[cassandra_ltr]

Bonjour,

J'ai un problème, je voudrais savoir comment on fait pour trouver le diviseur commun de deux nombres entiers. Puis comment trouver le PGCD de deux nombres en utilisant l'Algorithme des soustractions ou d'Euclide.

[titine]

Bonjour,

J'ai un problème, je voudrais savoir comment on fait pour trouver le diviseur commun de deux nombres entiers. Puis comment trouver le PGCD de deux nombres en utilisant l'Algorithme des soustractions ou d'Euclide.

Exemple : 84 et 396
Ils ont plusieurs diviseurs communs :
2 car 84 et 296 sont divisibles par 2 (nombres pairs)
3 car 84 et 396 sont divisibles par 3 (car 8+4=12 divisible par 3 et 3+9+6=18 divisible par 3)
4 car 84 et 396 sont divisibles par 4 (84/4 = 21 et 396/4 = 99)
...

Pour le PGCD par l'algorithme de soustraction :
396 - 84 = 312
312 - 84 = 228
228 - 84 = 144
144 - 84 = 60
84 - 60 = 24
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0
PGCD(396;84) = 12

[cassandra_ltr]

Merci. J'aurais voulu savoir aussi pour l'algorithme d'Euclide.

[titine]

PGCD de 396 et 84 par l'algorithme d'Euclide :
On fait la division euclidienne de 396 par 84 : 396 = 4*84 + 60
On fait la division euclidienne de 84 par 60 : 84 = 1*60 + 24
On fait la division euclidienne de 60 par 24 : 60 = 2*24 + 12
On fait la division euclidienne de 24 par 12 : 24 = 2*12 + 0
Le PGCD est le dernier reste non nul, c'est à dire 12.

[cassandra_ltr]

Merci beaucoup.