Calculer PGCD

C'est quoi le PGCD ?

Le PGCD c'est le plus grand commun diviseur de plusieurs chiffres. C'est un chiffre qui permet de diviser tous les chiffres entrés en obtenant un résultat entier.

Par exemple le PGCD de 3, 6, 9 est 3. En effet le chiffre le plus grand qui permet de diviser 3, 6, 9 en obtenant un entier est 3. (3/3 = 1, 6/3 = 2, 9/3 = 3).

Comment trouver le PGCD de deux nombres ?

Pour calculer le plus grand commun diviseur, il existe plusieurs techniques. Sur cette page, nous vous présenterons 3 techniques : la méthode des diviseurs, celle de l'algorithme des différences et l'algorithme d'Euclide.

Méthode 1 : les diviseurs

La première méthode consiste a prendre tous les diviseurs des chiffres et de regarder celui en commun le plus grand.

Par exemple pour 12 et 18 :

• Diviseurs de 12 : 1, 2, 3, 4, 6, 12
• Diviseurs de 18 : 1, 2, 3, 6, 9, 18

On voit que le plus grand commun diviseur (PGCD) est 6.

Méthode 2 : l'algorithme des différences

Cette méthode se base sur le principe suivant : si un nombre est diviseur de a et b (deux nombres), alors il est aussi diviseur de la différence (a-b).

Essayons d'appliquer cette formule à l'exemple précédent, trouver le PGCD entre 12 et 18. Pour cet exemple ça ira très vite :

• 18 - 12 = 6
• 12 - 6 = 6
• 6 - 6 = 0

Le PGCD est donc 6.

Essayons maintenant avec un exemple un peu plus complexe. Le PGCD entre 72 et 54:

• 72 - 54 = 18
• 54 - 18 = 36
• 36 - 18 = 18
• 18 - 18 = 0

Le PGCD est donc 18.

Méthode 3 : l'algorithme d'Euclide

Cette méthode est assez similaire à la méthode 2 sauf qu'ici, on utilisera la division Euclidienne basé sur le lemme d'Euclide. Cette méthode est la plus rapide pour trouver le PGCD de deux nombres.

Voici les étapes pour effectuer cette méthode :

1. On effectue une division euclidienne du plus grand nombre par le plus petit
2. On effectue, à nouveau, une division euclidienne du plus petit des deux nombres de la division précédente par le reste de cette division
3. On répète l'étape 2 jusqu'à avoir un reste nul. Le PGCD est le premier membre de la dernière division euclidienne

En pratique, voilà ce que ça donne pour trouver le PGCD de 455 et 221 :

• 455 / 221 = 221 x 2 + 13
• 221 / 13 = 13 x 17 + 0

Le PGCD est ici 13.