¤ Plus Grand Commun Diviseur ¤

I. Définition

Soit deux nombres entiers a et b.
Un diviseur commun à 2 entiers est un nombre qui divise à la fois le nombre a et le nombre b en 2 entiers.
Le plus grand diviseur commun de a et de b est appelé PGCD.

Pour trouver ce PGCD, nous avons 3 méthodes.
Cherchons ensemble le PGCD de 60 et 48.

1ère méthode : Lister les diviseurs

Diviseurs de 60 : 1 - 60; 2 - 30; 3 - 20; 4 - 15; 5 - 12; 6 - 10
Diviseurs de 48 : 1 - 48; 2 - 24; 3 - 16; 4 - 12; 8

12 est donc le plus grand diviseur commun. On dit alors :

PGCD (60 ; 48) = 12

2ème méthode : Soustractions successives

On commence à soustraire le plus grand nombre et on le soustrait avec le plus petit nombre. On prend le résultat et ainsi de suite. Regardez bien avec 80 et 48.

80 - 48 = 32
48 - 32 = 16
32 - 16 = 16
16 - 16 = 0

On fait des soustractions jusqu'à trouver à 0.
Le PGCD est le dernier reste non nul.
Donc PGCD ( 80 ; 48 ) = 16.

3ème méthode : L'algorithme d'Euclide.

Cette méthode est la plus utilisée. Voici l'énoncé de la méthode :

• On fait la division euclidienne du plus grand nombre par le plus petit nombre.

• On recommence avec le diviseur et le reste de la division précèdente.

• On s'arrête lorsque le reste = 0

• Le PGCD est le dernier reste non nul.

Trouver le PGCD de 5915 et 2429.

On réalise ce tableau.



D'après l'algorithme d'Euclide, le PGCD de 5915 et 2429 est 7 car c'est le dernier reste non nul.



Définition

Quand le PGCD de deux nombres est 1, on dit alors que ceux-ci sont premiers entre-eux.