Calculatrice PGCD & PPCM
Trouvez le plus grand commun diviseur et le plus petit commun multiple de deux entiers ou d’une liste entière — avec l’algorithme d’Euclide étape par étape, les décompositions en facteurs premiers, un test de primalité entre eux et l’identité de Bézout.
Rédigé par Suhaib Hassan. Les algorithmes sont ceux d’Euclide, et chaque exemple détaillé est recalculé à la main. Notre méthodologie.
Elle exécute l’algorithme de division d’Euclide sur des entiers de taille arbitraire, puis obtient le PPCM à partir de pgcd(a, b) · ppcm(a, b) = |a · b| et les coefficients de Bézout grâce à l’algorithme étendu.
Elle présente côte à côte la voie rapide (Euclide) et la voie intuitive (facteurs premiers communs), afin de pouvoir vérifier l’une par l’autre.
—
Facteurs premiers communs et distincts
L’intersection se multiplie pour donner le PGCD ; l’ensemble se multiplie pour donner le PPCM.
Algorithme d’Euclide
—
| Étape | Division | Quotient | Reste |
|---|
Calcul étape par étape
—
Identités à retenir
Résultats clés sur les plus grands communs diviseurs et les plus petits communs multiples.
| Identité | Énoncé | Remarque |
|---|---|---|
| Algorithme d’Euclide | pgcd(a, b) = pgcd(b, a mod b) | Au plus environ 5 × le nombre de chiffres du plus petit nombre, en nombre d’étapes |
| Identité de Bézout | ax + by = pgcd(a, b) | Des solutions x, y existent toujours dans les entiers |
| Dualité du produit | pgcd(a, b) · ppcm(a, b) = |a · b| | Vraie pour deux nombres, pas pour trois ou plus |
| Exposants premiers | min(eₐ, e_b) pour le pgcd, max pour le ppcm | Comparez les exposants de chaque nombre premier |
| Associativité | pgcd(a, b, c) = pgcd(pgcd(a, b), c) | Réduisez une liste paire par paire |
| Premiers entre eux | pgcd(a, b) = 1 | Aucun facteur premier commun |
Exemples détaillés
Carrelage d’un sol
Quel est le plus grand carreau carré qui recouvre exactement un sol de 12 × 18 ?
Les carreaux font 6 × 6, et (12 ÷ 6) × (18 ÷ 6) = 6 carreaux
Horaires de bus
Deux lignes partent d’une gare toutes les 12 et toutes les 18 minutes. Quand repartent-elles ensemble ?
Dents d’engrenage
Des engrenages de 19 et 30 dents sont premiers entre eux. Au bout de combien de temps les mêmes dents se retrouvent-elles en contact ?
ppcm = 19 × 30 = 570 dents — chaque dent rencontre toutes les autres, ce qui répartit l’usure uniformément
Que sont le PGCD et le PPCM ?
Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand entier qui divise les deux. Le plus petit commun multiple (PPCM) est le plus petit entier positif que les deux divisent. Ils servent à simplifier des fractions, à additionner des fractions (le PPCM des dénominateurs) et à synchroniser des cycles répétitifs.
Deux méthodes
- Décomposition en facteurs premiers : écrivez chaque nombre comme un produit de nombres premiers. Le PGCD prend le plus petit exposant de chaque facteur premier commun ; le PPCM prend le plus grand exposant de chaque facteur premier présent.
- Algorithme d’Euclide : remplacez de façon répétée (a, b) par (b, a mod b) jusqu’à ce que le reste soit 0 ; le dernier reste non nul est le PGCD. Il est bien plus rapide pour les grands nombres, car il n’a jamais besoin de factoriser.
Par Suhaib Hassan · Vérifié le 28 septembre 2026 · Comment CalculatePilot vérifie ses formules →
Sources
- Euclide, Éléments, livre VII, propositions 1–2, et livre X — l’algorithme de division euclidienne.
- Gauss, C. F. (1801). Disquisitiones Arithmeticae. Leipzig — unicité de la décomposition en facteurs premiers.
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, 3e éd., section 4.5.2 (le plus grand commun diviseur).
- ISO 80000-2:2019, Quantities and units — Part 2: Mathematics.
Questions fréquentes
L’égalité pgcd(a, b) · ppcm(a, b) = a · b est-elle valable pour trois nombres ou plus ?
Non. L’identité du produit n’est vraie que pour deux nombres. Pour une liste, on calcule le PGCD en prenant de façon répétée le pgcd du résultat courant avec le nombre suivant, et le PPCM de la même manière. Pour 4, 6 et 10 : pgcd = 2 et ppcm = 60, mais 2 × 60 = 120 alors que 4 × 6 × 10 = 240.
Que se passe-t-il si l’une des valeurs saisies, ou les deux, est nulle ?
pgcd(a, 0) = |a| car tout nombre divise 0. pgcd(0, 0) vaut conventionnellement 0. Le ppcm avec 0 vaut 0 par convention. Les valeurs négatives donnent les mêmes résultats que leurs valeurs absolues.
Pourquoi l’algorithme d’Euclide est-il tellement plus rapide que la factorisation ?
Chaque division réduit au moins de moitié le plus grand nombre tous les deux pas, il faut donc au plus environ log₂(min(a, b)) × 2 étapes. Il n’existe aucune méthode connue d’une rapidité comparable pour factoriser de grands nombres, ce qui explique que la cryptographie RSA repose sur cette difficulté.
À quoi sert l’identité de Bézout ?
Elle garantit l’existence d’entiers x et y tels que ax + by = pgcd(a, b). Lorsque pgcd(a, b) = 1, x est l’inverse modulaire de a modulo b, ce qui permet à RSA de calculer une clé privée à partir d’un exposant public.
Comment utiliser le PGCD pour simplifier une fraction ?
Divisez le numérateur et le dénominateur par leur PGCD. Pour 48/180, pgcd = 12, donc 48/180 = 4/15. Si le PGCD vaut 1, la fraction est déjà irréductible.
Que signifie « premiers entre eux » ?
Deux entiers sont premiers entre eux lorsque leur seul diviseur positif commun est 1, c’est-à-dire pgcd = 1. Ils n’ont pas besoin d’être premiers eux-mêmes : 8 et 15 sont premiers entre eux. Un ensemble est premier deux à deux si chaque paire qu’il contient est première entre elle.
Calculateurs associés
Poursuivez avec la théorie des nombres.