Pgcd ou le Plus Grand Commun diviseur
1. Diviseurs, diviseurs communs et pgcd
Un nombre entier possède un nombre fini de diviseurs, en particulier 1 et lui-même.
Exemple 1 :
Le nombre 12 a pour diviseurs :
Puisque 12 = 1 × 12 , 1 et 12 sont des diviseurs de 12
on a également 12 = 2 × 6 , 2 et 6 sont donc aussi des diviseurs de 12
enfin , 12 = 3 × 4 donc la liste des diviseurs de 12 est : 1 ; 2 ; 3 ; 4 ; 6 ; 12.
Remarque : Un nombre entier qui n'est divisible que par 1 et lui-même est appelé nombre premier. 13 est un nombre premier par exemple.
Considérons les deux nombres 12 et 18 et leurs diviseurs
12 a pour diviseurs 1 ; 2 ; 3 ; 4 ; 6 ; 12
18 a pour diviseurs 1 ; 2 ; 3 ; 6 ; 9 ; 18
1 ; 2 ; 3 ; 6 sont donc des diviseurs communs à 12 et 18.
6 est le plus grand de ces diviseurs communs, on l'appelle pgcd.
On a donc pgcd(12 ; 18) = 6.
Remarque : Si le pgcd de deux nombres est égal à 1 , on dit alors que ces nombres sont premiers entre eux.
On a par exemple pgcd(9 ; 5) = 1 donc 9 et 5 sont premiers entre eux.
2. Méthodes pour déterminer le pgcd de deux nombres.
a) Déterminer l'ensemble des diviseurs des deux nombres
30 a pour diviseurs 1 ; 2 ; 3 ; 5 ; 6 ; 10 ; 15 ; 30
24 a pour diviseurs 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 12 ; 24
Les diviseurs communs à 30 et 24 sont donc 1 ; 2 ; 3 ; 6.
Le plus grand de ces diviseurs communs est 6 , donc pgcd(30 ; 24)=6.
b) La méthode des soustractions successives
Cette méthode consiste à effectuer différentes soustractions jusqu'à obtenir 0 et de pouvoir ainsi déterminer le pgcd.
Pour déterminer par cette méthode le pgcd de 30 et 24, je calcule la différence du plus grand nombre avec le plus petit :
30 - 24 = 6
On recommence l'opération avec les deux plus petits nombres de l'égalité, en effectuant toujours la différence du plus grand avec le plus petit (il s'agit des deux nombres les plus à droite dans mon égalité) :
24 - 6 = 18
18 - 6 = 12
12 - 6 = 6
6 - 6 = 0
Lorsque l'on obtient 0 comme résultat de la différence , on obtient le pgcd recherché.
Ici on retrouve le résultat précédent : pgcd(30 ; 24) = 6.
Exemple : Déterminons le pgcd de 56 et de 32 par la méthode de différences successives.
On a :
56 - 32 = 24
32 - 24 = 8
24 - 8 = 16
16 - 8 = 8
8 - 8 = 0
on a donc pgcd(56 ; 32) = 8.
c) L'algorithme d'Euclide
Cette méthode qui est souvent la plus efficace, surtout pour des grands nombres, consiste à effectuer une succession de divisons euclidiennes.
Pour déterminer le pgcd de 306 et de 459 :
j'effectue la division euclidienne du plus grand des nombres par le plus petit , on a ainsi :
459 = 1 × 306 + 153
je recommence avec le diviseur et le reste obtenu dans la précédente division :
306 = 2 ×153 + 0.
Lorsque le reste de la division est égal à 0, alors le pgcd recherché est égal au diviseur de la dernière division effectuée : pgcd(306 ; 459) = 153.
Exemple : Déterminons par l'algorithme d'Euclide le pgcd de 1 683 et de 693.
On a :
1 683 = 2 × 693 + 297
693 = 2 × 297 + 99
297 = 3 × 99 + 0
donc pgcd(1 683 ; 297) = 99.