PGCD et PPCM
Calculez le PGCD et le PPCM de deux entiers, avec le détail de l’algorithme d’Euclide.
Comment ce calcul a-t-il été fait ?
Algorithme d'Euclide pour le PGCD : 12 = 0 × 18 + 12 18 = 1 × 12 + 6 12 = 2 × 6 + 0 Le dernier reste non nul donne PGCD = 6. PPCM = a × b ÷ PGCD = 12 × 18 ÷ 6 = 36
PGCD et PPCM : les deux piliers de l’arithmétique des entiers
Le PGCD (plus grand commun diviseur) de deux nombres entiers est le plus grand entier qui les divise tous les deux sans laisser de reste. Le PPCM (plus petit commun multiple) est, à l’inverse, le plus petit entier strictement positif qui est multiple des deux à la fois. Ces deux notions, enseignées au collège, sont au cœur de l’arithmétique : elles servent à simplifier des fractions, à réduire au même dénominateur, et à résoudre des problèmes de cycles ou de synchronisation.
Cet outil calcule instantanément le PGCD et le PPCM de deux entiers strictement positifs, et détaille chaque étape de l’algorithme d’Euclide, la méthode la plus rapide pour trouver un PGCD à la main. Il indique aussi si les deux nombres sont premiers entre eux, c’est-à-dire si leur seul diviseur commun est 1. Une relation remarquable lie toujours ces deux quantités : le produit des deux nombres est égal au produit de leur PGCD par leur PPCM, ce qui permet d’obtenir le PPCM dès que le PGCD est connu.
Formules
PGCD(a, b) = PGCD(b, a mod b), jusqu’à un reste nulOn divise le plus grand nombre par le plus petit et on note le reste. On recommence en divisant l’ancien diviseur par ce reste, et ainsi de suite. Le dernier reste non nul (autrement dit le dernier diviseur avant le reste 0) est le PGCD. Cette méthode, vieille de plus de 2000 ans, est extrêmement rapide : quelques divisions suffisent même pour de grands nombres.
PPCM(a, b) = (a x b) / PGCD(a, b)Le produit de deux entiers est toujours égal au produit de leur PGCD par leur PPCM : a x b = PGCD x PPCM. On en déduit immédiatement le PPCM en divisant le produit a x b par le PGCD. Comme le PGCD divise toujours le produit, le résultat est un entier exact.
PGCD = produit des facteurs communs, à la plus petite puissanceOn décompose chaque nombre en produit de facteurs premiers, puis on garde les facteurs communs affectés du plus petit exposant. Pour le PPCM, on prend tous les facteurs (communs et non communs) affectés du plus grand exposant. Cette méthode éclaire bien la structure des deux nombres, mais l’algorithme d’Euclide reste plus rapide pour le seul PGCD.
a et b premiers entre eux si et seulement si PGCD(a, b) = 1Deux nombres sont dits premiers entre eux (ou copremiers) lorsque leur seul diviseur commun positif est 1. Dans ce cas, leur PPCM est tout simplement leur produit : PPCM = a x b. Attention : être premiers entre eux ne signifie pas que chaque nombre est un nombre premier ; par exemple 8 et 9 sont premiers entre eux alors qu’aucun des deux n’est premier.
a x b = PGCD(a, b) x PPCM(a, b)Cette identité relie toujours les quatre quantités. Elle sert de vérification (le produit a x b doit retomber sur PGCD x PPCM) et permet de retrouver l’une des grandeurs à partir des trois autres, par exemple le PPCM dès que le PGCD est connu.
Exemples
On cherche le plus grand commun diviseur de 12 et 18 en posant les divisions successives, comme on l’apprend au collège.
On divise le plus grand par le plus petit : 18 = 1 x 12 + 6 (reste 6)
On continue avec 12 et 6 : 12 = 2 x 6 + 0 (reste 0)
Le dernier reste non nul est 6PGCD(12, 18) = 6.
Dès que le reste est nul, on s’arrête : le diviseur de cette dernière division est le PGCD. On en déduit le PPCM : (12 x 18) / 6 = 36.
On veut rendre irréductible la fraction 48/36, c’est-à-dire la simplifier au maximum.
On calcule le PGCD du numérateur et du dénominateur : PGCD(48, 36) = 12
On divise les deux termes par 12 : 48 / 12 = 4 et 36 / 12 = 3
La fraction devient 4/348/36 = 4/3, fraction irréductible.
Diviser le numérateur et le dénominateur par leur PGCD donne directement la fraction irréductible en une seule étape. C’est l’usage le plus courant du PGCD.
Pour additionner 1/12 et 1/18, il faut un dénominateur commun. Le plus petit possible est le PPCM des dénominateurs.
On calcule le PPCM de 12 et 18 : PPCM(12, 18) = 36
On convertit : 1/12 = 3/36 et 1/18 = 2/36
On additionne : 3/36 + 2/36 = 5/361/12 + 1/18 = 5/36.
Utiliser le PPCM comme dénominateur commun évite de manipuler des nombres inutilement grands : 36 est bien plus pratique que 12 x 18 = 216.
Deux bus partent en même temps d’un terminus. Le premier passe toutes les 12 minutes, le second toutes les 18 minutes. Dans combien de temps repartiront-ils ensemble ?
On cherche le plus petit multiple commun des deux fréquences : PPCM(12, 18)
PPCM(12, 18) = 36
Les deux bus coïncident toutes les 36 minutesLes deux bus repartent ensemble toutes les 36 minutes.
Tous les problèmes de coïncidence d’événements périodiques (engrenages, feux, signaux) se ramènent au calcul d’un PPCM.
Cas d’usage
Diviser le numérateur et le dénominateur d’une fraction par leur PGCD donne en une étape la fraction irréductible. C’est l’application la plus fréquente du PGCD, du collège aux calculs de proportions au quotidien.
Pour additionner ou comparer des fractions, on les met au même dénominateur. Choisir le PPCM des dénominateurs comme dénominateur commun garde les nombres aussi petits que possible et simplifie les calculs.
Le PPCM résout tous les problèmes de coïncidence d’événements périodiques : passages de bus, rotations d’engrenages, clignotements de feux, retours simultanés à un point de départ. La réponse est le plus petit multiple commun des périodes.
Le PGCD répond aux questions de partage en parts égales : répartir deux quantités en lots identiques les plus grands possibles, ou découper deux longueurs en segments égaux maximaux sans perte.
PGCD, PPCM, algorithme d’Euclide et nombres premiers entre eux sont au programme du cycle 4 et du lycée. Cet outil détaille chaque division de l’algorithme pour contrôler un exercice étape par étape.