PGCD

Définition

Le plus grand commun diviseur (PGCD) de deux nombres est le plus grand nombre entier qui divise ces deux nombres.

Soit a et b deux entiers naturels non nuls. On appelle PGCD de a et b le plus grand commun diviseur de a et b. PGCD (a;b).

Exemple 1 : quel est le PGCD de 18 et 24 ?

Prenons 18 et 24 :
Diviseurs de 18 : 1, 2, 3, 6, 9, 18
Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24
Diviseurs communs : 1, 2, 3, 6

Le PGCD de 18 et 24 est donc 6.

Calcul du PGCD avec l'algorithme d'Euclide

L'algorithme d'Euclide est une méthode efficace pour calculer le PGCD (Plus Grand Commun Diviseur) de deux nombres entiers positifs.
Principe : Le PGCD de deux nombres a et b (avec a > b) est égal au PGCD de b et du reste de la division de a par b.
On répète ce processus en remplaçant successivement a par b et b par le reste, jusqu'à obtenir un reste nul. Le PGCD est alors la dernière valeur non nulle.

Vous trouverez ci-dessous les différentes étapes détaillées du calcul :

Étape 1 : Poser les deux nombres, par exemple a = 24 et b = 18 (avec a > b).

Étape 2 : Faire la division euclidienne de a par b :
Trouver le quotient q et le reste r tels que a = b × q + r.
Pour notre exemple : 24 = 18 × 1 + 6.

Étape 3 : Remplacer a par b (ici 18), et b par le reste r (ici 6).
Donc maintenant, calculer le PGCD de 18 et 6.

Étape 4 : Répéter la division euclidienne :
18 = 6 × 3 + 0, le reste est 0.

Étape 5 : Lorsque le reste est nul, l'algorithme s'arrête.
Le PGCD est alors la dernière valeur non nulle, ici 6.

Conclusion : le PGCD (24,18) = 6.

L'algorithme d'Euclide fonctionne aussi pour tous les couples d'entiers positifs et est très efficace même pour les grands nombres.

Exemple 2

Trouvons ensemble le PGCD de 325 et 212 en utilisant l'algorithme d'Euclide.

Étape 1 : Poser les deux nombres, a = 325 et b = 212 (avec a > b).

Étape 2 : Faire la division euclidienne de a par b :
Trouver le quotient q et le reste r tels que a = b × q + r.
Pour notre exemple : 325 = 212 × 1 + 113.

Étape 3 : Remplacer a par b (ici 212), et b par le reste r (ici 113).
Donc maintenant, calculer le PGCD de 212 et 113.

Étape 4 : Répéter la division euclidienne :
212 = 113 × 1 + 99.

Étape 5 : Remplacer a par 113, et b par 99.
Calculer le PGCD de 113 et 99.

Étape 6 : Répéter la division euclidienne :
113 = 99 × 1 + 14.

Étape 7 : Remplacer a par 99, et b par 14.
Calculer le PGCD de 99 et 14.

Étape 8 : Répéter la division euclidienne :
99 = 14 × 7 + 1.

Étape 9 : Remplacer a par 14, et b par 1.
Calculer le PGCD de 14 et 1.

Étape 10 : Répéter la division euclidienne :
14 = 1 × 14 + 0.

Étape 11 : Lorsque le reste est nul, l'algorithme s'arrête.
Le PGCD est alors la dernière valeur non nulle, ici 1.

Le PGCD (325,212) = 1, ce qui signifie que 325 et 212 sont premiers entre eux. L'algorithme d'Euclide fonctionne aussi pour tous les couples d'entiers positifs et est très efficace même pour les grands nombres.

Exemple 3

Calculer un PGCD avec l'algorithme d'Euclide peut paraître complexe mais en réalité avec des exemples cela est beaucoup plus simple à comprendre. Prenons un troisième et dernier exemple.

Étape 1 : Poser les deux nombres, par exemple a = 560 et b = 24 (avec a > b).

Étape 2 : Faire la division euclidienne de a par b :
Trouver le quotient q et le reste r tels que a = b × q + r.
Pour notre exemple : 560 = 24 × 23 + 8.

Étape 3 : Remplacer a par b (ici 24), et b par le reste r (ici 8).
Donc maintenant, calculer le PGCD de 24 et 8.

Étape 4 : Répéter la division euclidienne :
24 = 8 × 3 + 0.

Étape 5 : Lorsque le reste est nul, l'algorithme s'arrête.
Le PGCD est alors la dernière valeur non nulle, ici 8.

Conclusion : le PGCD (560, 24) = 8.

Pour aller plus loin

Plus Grand Diviseur Commun ou Plus Grand Commun Diviseur ? Nous disons plutôt "Plus Grand Commun Diviseur" pour correspondre à "PGCD" mais nous pouvons entendre les 2 expressions. Le P.G.C.D. de deux nombres est le plus grand entier naturel qui divise les deux nombres.

Quelle est l'utilité d'un PGCD ? La connaissance du PGCD de 2 nombres entiers permet de simplifier en une fraction irréductible une fraction dont ils sont les numérateurs et dénominateurs.