Calculateur PGCD et PPCM — Algorithme d'Euclide
Maths Pro : calculatrice avancée + exercices corrigés illimités (3e-Terminale). Géométrie, algèbre, stats, trigo. Hors-ligne, sans pub.
Découvrir Maths Pro →14,90 € une fois · 27 templates exos · Export PDF
📌 En bref : PGCD par algorithme d'Euclide : O(log n). PPCM = a×b / PGCD. Relation : PGCD × PPCM = a×b (pour 2 nombres). Décomposition en facteurs premiers affichée.
Calculateur PGCD et PPCM
Algorithme d'Euclide pour le PGCD
L'algorithme d'Euclide (300 av. J.-C.) calcule le PGCD par divisions successives : PGCD(a,b) = PGCD(b, a mod b) jusqu'à ce que le reste soit 0. Exemple : PGCD(48, 36) :
- 48 = 1 × 36 + 12 → PGCD(48,36) = PGCD(36,12)
- 36 = 3 × 12 + 0 → PGCD(36,12) = 12
Donc PGCD(48,36) = 12. L'algorithme est O(log min(a,b)) — très efficace même pour de grands nombres.
Relation PGCD-PPCM
PGCD(a,b) × PPCM(a,b) = a × b
PPCM(48,36) = 48×36 / 12 = 1728 / 12 = 144
3 exemples concrets de PGCD et PPCM
Exemple 1 — Simplifier une fraction. La fraction 84/120 peut être simplifiée en cherchant PGCD(84,120). Par l'algorithme d'Euclide : 120 = 1×84+36 → 84 = 2×36+12 → 36 = 3×12+0. Donc PGCD = 12. 84/12 = 7, 120/12 = 10 → la fraction simplifiée est 7/10. Sans le PGCD, on risque de ne simplifier que par 2 puis par 6, en plusieurs étapes.
Exemple 2 — Synchronisation de tâches périodiques. Une maintenance A est faite tous les 8 jours, une maintenance B tous les 12 jours, une maintenance C tous les 18 jours. Quand seront-elles toutes simultanées ? PPCM(8,12) = 24, puis PPCM(24,18) : PGCD(24,18)=6 → PPCM = 24×18/6 = 72. Les trois maintenances coïncident tous les 72 jours. En planification industrielle, ce calcul évite les conflits de ressources.
Exemple 3 — Additionner des fractions. 5/12 + 7/18. Le dénominateur commun minimum est PPCM(12,18). PGCD(12,18) = 6. PPCM = 12×18/6 = 36. Donc 5/12 = 15/36 et 7/18 = 14/36. Somme = 29/36. Si on avait utilisé 12×18=216 comme dénominateur commun, on aurait obtenu 90/216 + 84/216 = 174/216 = 29/36 après simplification — plus laborieux.
Vous avez votre résultat ? Maths Pro génère des exercices corrigés illimités sur ce thème. Fiches PDF par niveau (3e-Terminale).
M'entraîner avec Maths Pro →14,90 € une fois · Sources officielles · Export PDF
3 erreurs fréquentes sur le PGCD et le PPCM
Erreur 1 — Confondre PGCD et PPCM. Le PGCD est le plus grand diviseur commun — il est toujours ≤ au plus petit des deux nombres. Le PPCM est le plus petit multiple commun — toujours ≥ au plus grand. Erreur classique : écrire PGCD(6,4)=12 (c'est le PPCM) au lieu de 2.
Erreur 2 — Oublier de diviser dans la relation PGCD × PPCM = a × b. PGCD(12,8) = 4. La formule donne PPCM = 12×8/4 = 24 — et non 12×8=96. Cette dernière valeur est le produit des deux nombres, non leur PPCM. La relation est PGCD × PPCM = a × b, ce qui implique PPCM = a×b / PGCD.
Erreur 3 — Appliquer la relation PGCD×PPCM=a×b à trois nombres. Cette relation ne s'applique qu'à deux nombres. Pour PGCD(6,10,15) et PPCM(6,10,15), il faut procéder en cascade : PGCD(PGCD(6,10),15) = PGCD(2,15) = 1 ; PPCM(PPCM(6,10),15) = PPCM(30,15) = 30. On ne peut pas écrire PGCD×PPCM = 6×10×15 = 900.
| A | B | PGCD | PPCM | Application |
|---|---|---|---|---|
| 12 | 8 | 4 | 24 | Fraction 8/12 → 2/3 |
| 48 | 36 | 12 | 144 | Carrelage 48×36 cm |
| 100 | 75 | 25 | 300 | Simplifier 75/100 = 3/4 |
| 17 | 13 | 1 | 221 | Deux nombres premiers → coprimes |
| 60 | 45 | 15 | 180 | Cycles 60 et 45 jours → 180 j |
Questions fréquentes
À quoi sert le PGCD dans la vie courante ?
Simplifier les fractions (diviser par PGCD), partager équitablement (ex: 48 chocolats et 36 bonbons → 12 enfants reçoivent chacun 4 chocolats et 3 bonbons), découper du tissu/carrelage sans chute (ex: pièce 48×36 cm → carrés de 12 cm max).
À quoi sert le PPCM dans la vie courante ?
Synchroniser des cycles (ex: un bus toutes les 12 min et un autre toutes les 18 min → se croisent toutes les PPCM(12,18)=36 minutes). Additionner des fractions (dénominateur commun = PPCM). Planification projet : tâche A toutes les 8 jours, tâche B toutes les 6 jours → coïncident toutes les 24 jours.
Comment calculer le PGCD de plus de deux nombres ?
PGCD(a,b,c) = PGCD(PGCD(a,b),c). La propriété est associative. Exemple : PGCD(24,36,60) = PGCD(PGCD(24,36),60) = PGCD(12,60) = 12.
Deux nombres premiers sont-ils toujours coprimes ?
Oui. Deux nombres distincts premiers p et q ont PGCD(p,q)=1 (coprimes) car leurs seuls diviseurs sont 1 et eux-mêmes. Plus généralement, a et b sont coprimes si PGCD(a,b)=1. Exemple : PGCD(15,28) = 1 (15=3×5, 28=2²×7 → aucun facteur commun).
Comment étendre l'algorithme d'Euclide à trois nombres ?
PGCD(a,b,c) = PGCD(PGCD(a,b),c). On calcule d'abord PGCD des deux premiers, puis on applique l'algorithme entre ce résultat et le troisième. Exemple : PGCD(180,120,84) = PGCD(PGCD(180,120),84) = PGCD(60,84) = 12. Identique pour le PPCM par cascade.
Quelle est la relation entre PGCD et décomposition en facteurs premiers ?
Le PGCD est le produit des facteurs premiers communs pris avec leur plus petit exposant. Exemple : 180 = 2²×3²×5 et 120 = 2³×3×5. PGCD = 2^min(2,3) × 3^min(2,1) × 5^min(1,1) = 4×3×5 = 60. Le PPCM prend l'exposant maximal : 2³×3²×5 = 360.
Le PGCD peut-il être supérieur à l'un des deux nombres ?
Non. Le PGCD est toujours ≤ au plus petit des deux nombres (car il doit diviser les deux). Si PGCD(a,b)=a, cela signifie que a divise b. Exemple : PGCD(6,18)=6 car 6 divise 18. Le PPCM, à l'inverse, est toujours ≥ au plus grand des deux nombres.
Comment utiliser le PGCD pour simplifier une fraction rapidement ?
Calculez PGCD(numérateur, dénominateur), puis divisez les deux par ce PGCD. Exemple : 420/560. PGCD(420,560) : 560=1×420+140 → 420=3×140+0 → PGCD=140. Fraction simplifiée : 420/140=3 et 560/140=4 → 3/4. On obtient la forme la plus simple en une seule opération.
