Calcul PGCD
En bref : Calculez le Plus Grand Commun Diviseur.
Calculateur
Resultat
Le PGCD : définition, algorithmes et applications pratiques
Le Plus Grand Commun Diviseur (PGCD) de deux entiers est le plus grand entier qui divise exactement les deux sans laisser de reste. C'est un outil central en arithmétique : il sert à simplifier les fractions, résoudre des problèmes de partage équitable, et constitue la base de la cryptographie moderne (algorithme RSA). Le PGCD est au programme de 4e et reste présent jusqu'en terminale.
Algorithme d'Euclide — la méthode la plus efficace
PGCD(a, b) :
Tant que b ≠ 0 :
r = a modulo b (reste de la division euclidienne)
a ← b
b ← r
Résultat = a
Exemple : PGCD(48, 36).
48 = 36 × 1 + 12 → PGCD(48,36) = PGCD(36,12)
36 = 12 × 3 + 0 → PGCD(36,12) = 12
PGCD(48, 36) = 12
Méthode de décomposition en facteurs premiers : décomposer chaque nombre, prendre les facteurs communs avec les exposants les plus petits. 48 = 2⁴ × 3 et 36 = 2² × 3² → PGCD = 2² × 3 = 12.
3 exemples concrets avec des situations du quotidien
Exemple 1 — Partage équitable : carreaux de cuisine
Vous voulez carreler un couloir de 84 cm de large et 120 cm de long avec des carreaux carrés identiques, sans les couper. Quelle est la plus grande taille possible ?
PGCD(84, 120) = ? Algorithme d'Euclide :
120 = 84×1 + 36 → PGCD(120,84) = PGCD(84,36)
84 = 36×2 + 12 → PGCD(84,36) = PGCD(36,12)
36 = 12×3 + 0 → PGCD = 12 cm
Des carreaux de 12×12 cm. Il en faudra (84/12) × (120/12) = 7 × 10 = 70 carreaux.
Exemple 2 — Simplification de fraction : recette nutritive
Un biscuit contient 36 g de sucre pour 48 g de farine. Quelle est la proportion de sucre sous forme de fraction simplifiée ?
PGCD(36, 48) = ? 36 = 2² × 3² et 48 = 2⁴ × 3 → PGCD = 2² × 3 = 12.
36/48 = (36÷12)/(48÷12) = 3/4. Le biscuit contient 3/4 du poids de farine en sucre.
Exemple 3 — Organisation : distribution de lots
Un organisateur dispose de 60 stylos et 84 carnets à distribuer en lots identiques avec aucun reste. Combien de lots au maximum peut-il faire ?
PGCD(60, 84) = ? 60 = 2²×3×5 et 84 = 2²×3×7 → PGCD = 2²×3 = 12 lots.
Chaque lot contiendra 60/12 = 5 stylos et 84/12 = 7 carnets.
Tableau de référence : PGCD de paires courantes
| Paire (a, b) | PGCD | a/PGCD | b/PGCD | Fraction simplifiée |
|---|---|---|---|---|
| 12 et 18 | 6 | 2 | 3 | 2/3 |
| 24 et 36 | 12 | 2 | 3 | 2/3 |
| 100 et 75 | 25 | 4 | 3 | 4/3 |
| 17 et 13 | 1 | 17 | 13 | 17/13 (irréductible) |
Méthode pas-à-pas : algorithme d'Euclide à la main
- Identifier le plus grand des deux nombres (appelons-le a) et le plus petit (b).
- Effectuer la division euclidienne : diviser a par b, noter le reste r.
- Remplacer a par b et b par r.
- Répéter jusqu'à ce que le reste soit 0.
- Le PGCD est le dernier diviseur non nul (la valeur de b juste avant r = 0).
3 erreurs fréquentes avec le PGCD
- Confondre PGCD et PPCM : le PGCD divise les deux nombres (le plus grand commun diviseur) ; le PPCM est divisible par les deux nombres (le plus petit commun multiple). Ce sont des opérations inverses en quelque sorte, reliées par : PGCD(a,b) × PPCM(a,b) = a × b.
- S'arrêter trop tôt dans l'algorithme d'Euclide : il faut continuer jusqu'à obtenir un reste nul. Beaucoup d'élèves s'arrêtent dès que le reste est petit, sans vérifier qu'il vaut zéro.
- Oublier que PGCD(a, 0) = a : tout entier divise 0, donc le plus grand diviseur commun de a et 0 est a lui-même. Utile à mémoriser pour le cas de base des algorithmes récursifs.
Pack Examens 2026 — Maths : fractions + équations + dérivées + suites
- Fractions, équations 1er/2nd degré, racines, logs
- Dérivées, primitives, intégrales, limites + exercices
- Suites (arithmétique/géométrique) + PGCD/PPCM
Coefficients officiels · Éducation Nationale 2026
Questions fréquentes sur le calcul du PGCD
Quelle est la différence entre PGCD et PPCM ?
Le PGCD (Plus Grand Commun Diviseur) est le plus grand entier qui divise a et b sans reste. Le PPCM (Plus Petit Commun Multiple) est le plus petit entier qui est multiple de a et de b. Ils sont reliés par : PGCD(a,b) × PPCM(a,b) = a × b. Exemple : PGCD(4,6) = 2, PPCM(4,6) = 12, et 2 × 12 = 24 = 4 × 6. Le PGCD sert à simplifier les fractions, le PPCM à trouver un dénominateur commun.
Quand deux nombres sont-ils premiers entre eux ?
Deux nombres sont premiers entre eux (ou copremiers) quand leur PGCD est 1. Exemples : PGCD(8,15) = 1 (8 = 2³, 15 = 3×5, aucun facteur commun). Les nombres premiers entre eux n'ont aucun diviseur commun supérieur à 1. Dans le cours de 4e, on dit qu'une fraction a/b est irréductible si et seulement si PGCD(a,b) = 1.
Comment calculer le PGCD de trois nombres ou plus ?
On calcule successivement. PGCD(a, b, c) = PGCD(PGCD(a, b), c). Exemple : PGCD(12, 18, 30). PGCD(12, 18) = 6. PGCD(6, 30) = 6. Résultat : 6. La propriété d'associativité du PGCD garantit qu'on peut appliquer l'algorithme d'Euclide plusieurs fois de suite.
Le PGCD peut-il valoir 0 ?
Conventionnellement, PGCD(0, 0) = 0 car tout entier divise 0. Mais pour tout entier a ≠ 0, PGCD(a, 0) = a. En pratique, le PGCD de deux entiers strictement positifs est toujours au moins 1 (puisque 1 divise tout nombre). Il est donc toujours entre 1 et min(a, b).
L'algorithme d'Euclide fonctionne-t-il avec des grands nombres ?
Oui, et c'est précisément son avantage. L'algorithme d'Euclide est très efficace : le nombre de divisions nécessaires est proportionnel au logarithme du plus petit des deux nombres. Pour des nombres à 100 chiffres (utilisés en cryptographie RSA), l'algorithme d'Euclide ne nécessite que quelques centaines d'étapes, contre des milliards pour une approche par énumération des diviseurs.
Le PGCD est-il utilisé en cryptographie ?
Absolument. Le chiffrement RSA (qui sécurise les communications HTTPS) repose sur des propriétés liées au PGCD. La clé publique utilise deux nombres premiers p et q. La clé privée est calculée via l'algorithme d'Euclide étendu (qui fournit les coefficients de l'identité de Bézout : u×a + v×b = PGCD(a,b)). Chaque fois que vous accédez à un site sécurisé, le PGCD joue un rôle en arrière-plan.
Comment utiliser le PGCD pour simplifier une fraction ?
Calculez le PGCD du numérateur et du dénominateur, puis divisez les deux par ce PGCD. Exemple : 90/126. PGCD(90,126) = 18. 90/18 = 5 et 126/18 = 7. La fraction simplifiée est 5/7. Vérification : PGCD(5,7) = 1, donc 5/7 est bien irréductible. C'est l'application la plus directe du PGCD en classe.
Quel est le lien entre PGCD et identité de Bézout ?
L'identité de Bézout (programme de terminale option maths expertes) affirme que pour tous entiers a et b, il existe des entiers u et v tels que a×u + b×v = PGCD(a,b). Exemple : PGCD(35, 15) = 5. Identité : 35×(−1) + 15×3 = −35 + 45 = 10... On cherche : 35×1 + 15×(−2) = 35−30 = 5. ✓. Cette identité est fondamentale pour résoudre les équations diophantiennes (équations à solutions entières).