Sciences · Mathématiques
PGCD et PPCM
Le PGCD de deux entiers est leur plus grand diviseur commun, le PPCM leur plus petit multiple commun non nul. Pour 12 et 18 : PGCD = 6 et PPCM = 36. On les calcule par l’algorithme d’Euclide ou les facteurs premiers.
Mis à jour le 4 min de lecture
Simplifier une fraction, trouver un dénominateur commun, découper un rectangle en carrés identiques le plus grands possible, savoir quand deux événements périodiques coïncideront : tous ces problèmes reviennent à calculer un PGCD ou un PPCM. Ce sont deux notions fondamentales de l’arithmétique des entiers.
Rappels : diviseur et multiple
Un entier d est un diviseur de a (et a un multiple de d) s’il existe un entier k tel que a = d × k. Ainsi 6 est un diviseur de 18 (18 = 6 × 3) et 18 un multiple de 6. Les critères de divisibilité permettent de repérer rapidement les diviseurs.
Méthode 1 : lister les diviseurs et les multiples
Adaptée aux petits nombres.
Méthode 2 : l’algorithme d’Euclide
Décrit par Euclide dans le livre VII des Éléments, vers 300 av. J.-C., c’est l’un des plus anciens algorithmes connus (voir algorithme). Il repose sur une propriété : PGCD(a ; b) = PGCD(b ; r), où r est le reste de la division euclidienne de a par b.
Méthode : on divise le plus grand nombre par le plus petit, puis le diviseur par le reste, et ainsi de suite. Le PGCD est le dernier reste non nul.
Exemple : PGCD de 1 071 et 462
| Division | Quotient | Reste |
|---|---|---|
| 1 071 = 462 × 2 + 147 | 2 | 147 |
| 462 = 147 × 3 + 21 | 3 | 21 |
| 147 = 21 × 7 + 0 | 7 | 0 |
Le dernier reste non nul est 21 : PGCD(1 071 ; 462) = 21.
Variante : l’algorithme des soustractions successives
On remplace le plus grand nombre par la différence des deux, jusqu’à obtenir deux nombres égaux : PGCD(a ; b) = PGCD(b ; a − b). Pour 48 et 18 : (48 ; 18) → (30 ; 18) → (18 ; 12) → (12 ; 6) → (6 ; 6). PGCD = 6. Plus intuitive, la méthode est plus lente pour de grands nombres.
Méthode 3 : la décomposition en facteurs premiers
Tout entier supérieur à 1 se décompose de façon unique en produit de nombres premiers.
- PGCD : produit des facteurs premiers communs, chacun avec son plus petit exposant.
- PPCM : produit de tous les facteurs premiers présents, chacun avec son plus grand exposant.
La relation fondamentale
Pour deux entiers positifs a et b :
PGCD(a ; b) × PPCM(a ; b) = a × b
D’où un moyen rapide de calculer le PPCM une fois le PGCD connu : PPCM(a ; b) = (a × b) / PGCD(a ; b).
Vérification : 12 × 18 = 216 et 6 × 36 = 216. Pour 360 et 84 : 12 × 2 520 = 30 240 = 360 × 84.
Nombres premiers entre eux
Deux entiers sont premiers entre eux si leur PGCD vaut 1 : ils n’ont aucun diviseur commun autre que 1. Exemples : 8 et 15, 14 et 25. Dans ce cas, leur PPCM est simplement leur produit (PPCM(8 ; 15) = 120). Attention : deux nombres premiers entre eux ne sont pas forcément premiers eux-mêmes.
Applications
Simplifier une fraction
Diviser le numérateur et le dénominateur par leur PGCD donne directement la fraction irréductible :
462 / 1 071 = (462 ÷ 21) / (1 071 ÷ 21) = 22 / 51
Additionner des fractions
Le plus petit dénominateur commun est le PPCM des dénominateurs :
5/12 + 7/18 = 15/36 + 14/36 = 29/36 (PPCM(12 ; 18) = 36)
Voir fractions.
Problèmes types
Plus de deux nombres
Les définitions s’étendent : on calcule de proche en proche, PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c), et de même pour le PPCM. Avec la décomposition en facteurs premiers, on applique les mêmes règles à tous les nombres à la fois.
Questions fréquentes
Comment calculer rapidement un PGCD ?
Avec l’algorithme d’Euclide : diviser le grand nombre par le petit, puis le petit par le reste, et ainsi de suite ; le dernier reste non nul est le PGCD.
Quelle est la différence entre PGCD et PPCM ?
Le PGCD est le plus grand nombre qui divise les deux nombres ; il est inférieur ou égal au plus petit d’entre eux. Le PPCM est le plus petit nombre que les deux divisent ; il est supérieur ou égal au plus grand.
Que vaut le PGCD de deux nombres premiers distincts ?
1, puisqu’un nombre premier n’a pour diviseurs que 1 et lui-même. Leur PPCM est leur produit.
À quoi sert le PPCM ?
À trouver le plus petit dénominateur commun de fractions et à résoudre des problèmes de cycles qui se répètent (horaires, engrenages, événements périodiques).