Le PGCD de deux entiers

En une phrase

Le PGCD de deux nombres, c'est le plus grand nombre qui les divise tous les deux à la fois. Par exemple, le PGCD de 24 et 36 est 12 : 12 divise 24 et 12 divise 36, et aucun nombre plus grand ne divise les deux.

Comprendre

Le PGCD de deux entiers, c'est leur Plus Grand Commun Diviseur : le plus grand nombre qui divise les deux à la fois. Il existe trois méthodes pour le trouver. Méthode 1 : on liste les diviseurs de chacun, on repère ceux qui sont communs, et on prend le plus grand.

Pour 24 et 36, les diviseurs communs sont 1, 2, 3, 4, 6, 12 : le plus grand est 12. Méthode 2, la plus sûre : la décomposition en facteurs premiers. On décompose 24 = 2³ × 3 et 36 = 2² × 3², puis on garde les facteurs premiers communs, chacun affecté du plus petit exposant : ici 2² (le plus petit entre 2³ et 2²) et 3 (le plus petit entre 3¹ et 3²), donc PGCD = 2² × 3 = 12. Méthode 3, l'algorithme d'Euclide : on divise le plus grand par le plus petit, puis on recommence avec le diviseur et le reste, jusqu'à un reste nul ; le dernier reste non nul est le PGCD. Pour 36 et 24 : 36 = 24 × 1 + 12, puis 24 = 12 × 2 + 0, donc PGCD = 12. Le PGCD sert surtout à rendre une fraction irréductible en une seule étape : on divise le numérateur et le dénominateur par leur PGCD, par exemple 24/36 = 2/3 en divisant les deux par 12. Enfin, deux entiers dont le PGCD vaut 1 sont dits premiers entre eux : ils n'ont aucun diviseur commun autre que 1. Attention à ne pas confondre le PGCD (plus grand DIVISEUR commun) avec le PPCM (plus petit MULTIPLE commun), et à bien prendre le plus PETIT exposant, jamais le plus grand.

Le cours

Un diviseur commun à deux entiers est un nombre qui les divise tous les deux. Le PGCD de deux entiers a et b (non nuls) est le Plus Grand Commun Diviseur : le plus grand des nombres qui divisent à la fois a et b. On le note PGCD(a ; b).

Comme 1 divise toujours tout le monde, il existe toujours au moins un diviseur commun, donc un PGCD. Trois méthodes permettent de le calculer. (1) Lister les diviseurs : on écrit tous les diviseurs de a, tous ceux de b, on repère les diviseurs communs et on prend le plus grand. Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24 ; diviseurs de 36 : 1, 2, 3, 4, 6, 9, 12, 18, 36 ; diviseurs communs : 1, 2, 3, 4, 6, 12 ; le plus grand est 12, donc PGCD(24 ; 36) = 12. (2) Décomposition en facteurs premiers : on décompose chaque nombre, puis on multiplie les facteurs premiers COMMUNS, chacun pris avec son PLUS PETIT exposant.

Avec 24 = 2³ × 3 et 36 = 2² × 3², le facteur 2 apparaît avec les exposants 3 et 2 (on garde 2²), le facteur 3 avec les exposants 1 et 2 (on garde 3¹) ; donc PGCD = 2² × 3 = 4 × 3 = 12. (3) Algorithme d'Euclide : on effectue la division euclidienne du plus grand par le plus petit, puis on recommence en remplaçant le dividende par l'ancien diviseur et le diviseur par le reste, jusqu'à obtenir un reste nul ; le PGCD est le dernier reste non nul. Pour 36 et 24 : 36 = 24 × 1 + 12, puis 24 = 12 × 2 + 0 ; le dernier reste non nul est 12, donc PGCD(24 ; 36) = 12. Les trois méthodes donnent bien le même résultat. Application essentielle : rendre une fraction irréductible en une seule étape.

Pour simplifier 24/36, on divise le numérateur et le dénominateur par leur PGCD : 24 ÷ 12 = 2 et 36 ÷ 12 = 3, donc 24/36 = 2/3, forme irréductible (car 2 et 3 n'ont plus que 1 comme diviseur commun). Enfin, deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1 : ils n'ont aucun diviseur commun autre que 1. « Premiers entre eux » ne veut pas dire « nombres premiers » : 8 et 9 sont premiers entre eux (PGCD 1) alors qu'aucun des deux n'est premier.

Les erreurs fréquentes

Confondre le PGCD (plus grand DIVISEUR commun) avec le PPCM (plus petit MULTIPLE commun), par exemple répondre 72 pour le PGCD de 24 et 36.

Le PGCD est un DIVISEUR : il est donc au plus égal au plus petit des deux nombres. PGCD(24 ; 36) = 12 (qui divise 24 et 36), alors que 72 est un multiple commun, pas un diviseur commun.

Dans la décomposition en facteurs premiers, prendre le plus GRAND exposant, par exemple PGCD = 2³ × 3² = 72 pour 24 = 2³ × 3 et 36 = 2² × 3².

Pour le PGCD, on prend chaque facteur commun avec son plus PETIT exposant : 2² (et non 2³) et 3 (et non 3²), donc PGCD = 2² × 3 = 12. Prendre le plus grand exposant donnerait le PPCM, pas le PGCD.

Tu maîtrises la notion si…

• Définir le PGCD de deux entiers comme le plus grand de leurs diviseurs communs.
• Calculer un PGCD par décomposition en facteurs premiers (facteurs communs au plus petit exposant) ou par l'algorithme d'Euclide.
• Utiliser le PGCD pour rendre une fraction irréductible en une seule étape et reconnaître deux nombres premiers entre eux (PGCD = 1).

Vérifie que tu as compris

1. Le PGCD de 24 et 36 est :

   Réponse 12

   24 = 2³×3 et 36 = 2²×3². On garde les facteurs communs au plus petit exposant : 2²×3 = 12 (72 serait le PPCM, avec le plus grand exposant).

2. Deux entiers dont le PGCD vaut 1 sont dits :

   Réponse premiers entre eux

   Un PGCD égal à 1 signifie qu'ils n'ont aucun diviseur commun autre que 1 : ils sont premiers ENTRE EUX (ex. 8 et 9), à ne pas confondre avec « nombres premiers ».

3. Pour calculer le PGCD de 60 et 24 avec l'algorithme d'Euclide, quel calcul fait-on en premier ?

   Réponse la division euclidienne de 60 par 24

   L'algorithme d'Euclide divise toujours le plus grand par le plus petit : 60 = 24 × 2 + 12. On recommence ensuite avec le diviseur et le reste : 24 = 12 × 2 + 0. Le dernier reste non nul est 12, donc le PGCD de 60 et 24 vaut 12.