PGCD
PGCD : Plus Grand Commun Diviseur (ou Plus Grand Diviseur Commun)
Soit deux nombres entiers naturels non nuls a et b. Chacun de ces deux nombres disposent d'un certain nombre de diviseurs. a et b ont au moins 1 comme diviseur commun (car 1 divise tous les nombres entiers). Le plus grand diviseur commun à a et b sera noté PGCD (a;b).
Prenons un exemple
Cherchons le plus grand diviseur commun entre 24 et 56. Il existe plusieurs méthodes pour trouver le PGCD :
Méthode 1 :
On liste les diviseurs des deux nombres et on cherche le plus grand nombre commun aux deux listes :
24 = 1x24 = 2x12 = 3x8 = 4x6 = 6x4 = 8x3 = 12x2
Soit les diviseurs de 24 sont D(24) = {1;2;3;4;6;8;12;24}
56 = 1x56 = 2x28 = 4x14 = 7x8 = 8x7
Soit les diviseurs de 56 sont D(56)={1;2;4;7;8;14;28;56}
Donc PGCD(24;56) = 8
Cette méthode est longue et fastidieuse.
Méthode 2 :
Utilisons la méthode des soustractions. C'est une méthode simple.
56-24 = 32
32-24 = 8
24-8 = 16
16-8 = 8
8-8 = 0
Donc PGCD(24;56) = 8
Méthode 3 :
Il existe également une autre méthode simple appelée méthode par division Euclidienne. Cette méthode se base sur l'algorithme d'Euclide :
Soit a et b deux nombres entiers tel que a > b,
et soit r le reste de la division euclidienne de a par b.
PGCD (a ; b) = PGCD (b ; r)
Dans notre exemple cela donne :
56 = 24x2 + 8
24 = 8x3 + 0
Donc PGCD(24;56) = 8
Méthode 4 :
On utilise les facteurs premiers. On écrit les décompositions en facteurs premiers des deux nombres. Le PGCD est alors égal au produit des facteurs premiers communs aux deux décompositions, chacun étant affecté de son plus petit exposant.
24 = 23x3
56 = 23x7
Donc PGCD(24;56) = 23 = 8 (2 est le seul facteur premier commun dans notre cas).
