Calcul du PGCD : plus grand commun diviseur
MathématiquesChoisissez le nombre de valeurs et saisissez-les : le calculateur donne le plus grand commun diviseur et détaille la décomposition en facteurs premiers et les divisions d’Euclide, pour suivre le calcul et le refaire à la main.
Détail du calcul
PGCD(12, 18) = 6
- Décomposez 12 et 18 en facteurs premiers, comme le montre le tableau ci-dessous.
- Multipliez les facteurs premiers communs, chacun avec son plus petit exposant : 2 · 3 (s’il n’y en a aucun, le produit vaut 1).
- Ce produit est le plus grand commun diviseur : 6.
- Les divisions successives d’Euclide donnent le même résultat : le dernier diviseur, celui qui laisse un reste nul, est 6.
Dès que toutes les valeurs sont valides, chaque étape du calcul s’affiche ici.
Formule
- PGCD
- plus grand commun diviseur, le plus grand entier qui divise tous les nombres donnés
- pi
- les nombres premiers qui divisent tous les nombres
- mi
- le plus petit exposant avec lequel ce nombre premier apparaît dans les décompositions
- q, r
- quotient et reste de la division euclidienne de a par b, avec r inférieur à b
Comment fonctionne le calcul
Le plus grand commun diviseur (PGCD) de deux entiers ou plus est le plus grand entier qui les divise tous sans laisser de reste. Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12, ceux de 18 sont 1, 2, 3, 6, 9 et 18 : les diviseurs communs sont 1, 2, 3 et 6, et le plus grand est 6, donc PGCD(12, 18) = 6. Quand le PGCD vaut 1, les nombres sont dits premiers entre eux.
La première méthode est la décomposition en facteurs premiers : on écrit chaque nombre comme un produit de nombres premiers, on garde les facteurs présents dans tous les nombres et on les multiplie, chacun avec son plus petit exposant. C’est la méthode apprise au collège, et le calculateur affiche la décomposition de chaque nombre dans le tableau sous le résultat. Par exemple, 360 = 2³ × 3² × 5 et 48 = 2⁴ × 3 donnent PGCD = 2³ × 3 = 24.
La seconde méthode est l’algorithme d’Euclide, par divisions euclidiennes successives, qui évite toute décomposition : on divise le plus grand nombre par le plus petit, puis le diviseur par le reste obtenu, et on recommence jusqu’à obtenir un reste nul. Le dernier diviseur, celui qui laisse un reste nul, est le PGCD. C’est la méthode la plus rapide pour de grands nombres. Avec trois ou quatre nombres, on calcule le PGCD des deux premiers, puis celui de ce résultat et du nombre suivant : le second tableau liste toutes les divisions. La division euclidienne sert aussi à convertir un nombre décimal en binaire : on divise le nombre par 2, puis chaque quotient par 2, jusqu’à un quotient nul, et les restes, lus du dernier au premier, forment son écriture en base 2.
Le PGCD sert à rendre une fraction irréductible, en divisant le numérateur et le dénominateur par leur PGCD : PGCD(30, 18) = 6, donc 30/18 = 5/3. Il sert aussi à partager en parts égales sans reste : un sol de 360 cm sur 240 cm se couvre de carreaux carrés entiers, tous identiques, de 120 cm de côté au plus. Pour simplifier une fraction pas à pas, voir le calcul de fractions ; pour la part d’un total en pourcentage, le calcul de pourcentage ; pour agrandir ou réduire un plan, le calcul d’échelle.
À propos de la formule
Avec la décomposition, 12 = 2² × 3 et 18 = 2 × 3² : les facteurs premiers communs sont 2 et 3, de plus petit exposant 1, donc PGCD = 2 × 3 = 6. Un facteur absent de l’un des nombres n’entre pas dans le produit, et s’il n’y a aucun facteur commun, le PGCD vaut 1.
L’algorithme d’Euclide repose sur PGCD(a, b) = PGCD(b, r), où r est le reste de la division de a par b : chaque division remplace le couple par un couple plus petit de même PGCD, si bien que le reste nul est atteint en peu d’étapes. Avec 18 et 12 : 18 = 1 × 12 + 6, puis 12 = 2 × 6 + 0, et le dernier diviseur est 6.
Entre le PGCD et le PPCM de deux entiers, on a la relation PGCD(a, b) × PPCM(a, b) = a × b : avec 12 et 18, le PPCM vaut 36 et 6 × 36 = 216 = 12 × 18. Pour obtenir directement le plus petit commun multiple de 2 à 5 nombres, avec leur PGCD, utilisez le calcul du PPCM.
Exemple de calcul
Quel est le PGCD de 360 et 48 ?
- Décomposition en facteurs premiers : 360 = 2³ × 3² × 5 et 48 = 2⁴ × 3.
- Les facteurs communs sont 2 et 3, pris avec leur plus petit exposant (3 pour le 2, 1 pour le 3) : 2³ · 3 = 24.
- Avec les divisions successives : 360 = 7 × 48 + 24, puis 48 = 2 × 24 + 0. Le dernier diviseur est 24, le même résultat.
Le PGCD de 360 et 48 est 24 : c’est le plus grand entier qui divise les deux nombres.
Reprendre l’exemple dans le calculateurQuestions fréquentes
Comment calculer le PGCD avec la décomposition en facteurs premiers ?
Écrivez chaque nombre comme un produit de nombres premiers, repérez les facteurs communs à tous les nombres et multipliez-les, chacun avec son plus petit exposant. Pour 12 = 2² × 3 et 18 = 2 × 3², les facteurs communs sont 2 et 3, tous deux à la puissance 1 : PGCD = 2 × 3 = 6. Le calculateur affiche la décomposition de chaque nombre.
Quel est l’algorithme pour calculer le PGCD de deux nombres ?
C’est l’algorithme d’Euclide. Divisez le plus grand nombre par le plus petit et notez le reste, puis divisez le diviseur par ce reste, et ainsi de suite jusqu’à un reste nul. Le dernier diviseur est le PGCD. Pour 75 et 60 : 75 = 1 × 60 + 15, puis 60 = 4 × 15 + 0, donc PGCD(75, 60) = 15. La méthode reste rapide avec de très grands nombres, que décomposer en facteurs premiers rendrait long.
Quel est le PGCD de 12 et 18 ?
C’est 6. Les diviseurs communs de 12 et 18 sont 1, 2, 3 et 6, et le plus grand est 6. Avec les facteurs premiers, 12 = 2² × 3 et 18 = 2 × 3², donc PGCD = 2 × 3 = 6. C’est aussi le résultat affiché à l’ouverture de la page.
Quel est le PGCD de 20 et 30, de 16 et 14, de 3 et 6 ou de 5 et 7 ?
PGCD(20, 30) = 10, car leurs diviseurs communs sont 1, 2, 5 et 10. PGCD(16, 14) = 2, puisque 16 = 2⁴ et 14 = 2 × 7 n’ont qu’un 2 en commun. PGCD(3, 6) = 3 : quand le plus petit nombre divise le plus grand, c’est lui le PGCD. PGCD(5, 7) = 1 : deux nombres premiers distincts n’ont que 1 comme diviseur commun.
Comment trouver le PGCD de 18 et 24 ?
C’est 6. Les diviseurs de 18 sont 1, 2, 3, 6, 9 et 18, ceux de 24 sont 1, 2, 3, 4, 6, 8, 12 et 24 : le plus grand diviseur commun est 6. Avec Euclide, 24 = 1 × 18 + 6 puis 18 = 3 × 6 + 0, et avec les facteurs premiers, 18 = 2 × 3² et 24 = 2³ × 3 donnent 2 × 3 = 6. Saisissez 18 et 24 dans le calculateur pour voir les deux tableaux.
Comment calculer le PGCD de deux polynômes ?
On transpose l’algorithme d’Euclide : on divise le polynôme de plus haut degré par l’autre, puis le diviseur par le reste, jusqu’à un reste nul. Le dernier reste non nul est un PGCD, défini à un facteur constant près, et l’on choisit en général le polynôme unitaire. Pour X² − 1 et X² − 2X + 1, le dernier reste non nul est 2X − 2, donc le PGCD unitaire est X − 1. Ce calculateur ne traite que des entiers.
Qu’est-ce que le plus grand commun diviseur ?
C’est le plus grand entier qui divise tous les nombres donnés sans laisser de reste. Pour deux nombres a et b, on le note PGCD(a, b), et GCD (greatest common divisor) en anglais. Il existe toujours et il est unique : PGCD(30, 45) = 15, car 15 divise 30 comme 45 et aucun entier plus grand n’en est capable.
Comment calculer le PGCD de trois nombres ou plus ?
Vous pouvez décomposer chaque nombre et multiplier les facteurs communs à tous, ou appliquer l’algorithme d’Euclide deux nombres à la fois : PGCD(a, b, c) = PGCD(PGCD(a, b), c). Pour 36, 48 et 60, les diviseurs communs sont 1, 2, 3, 4, 6 et 12 donc PGCD = 12 ; avec Euclide, PGCD(36, 48) = 12 puis PGCD(12, 60) = 12. Le calculateur traite de deux à quatre nombres et écrit toutes les divisions.
Quand deux nombres sont-ils premiers entre eux ?
Quand leur PGCD vaut 1, c’est-à-dire qu’ils n’ont aucun diviseur commun autre que 1. Ils n’ont pas besoin d’être premiers eux-mêmes : 8 et 15 sont premiers entre eux sans qu’aucun des deux soit premier. Avec trois nombres ou plus, le PGCD vaut 1 quand aucun diviseur supérieur à 1 ne les divise tous, même si certains couples en ont un : 6, 10 et 15 ont pour PGCD 1, alors que 6 et 10 sont tous deux pairs.
À quoi sert le PGCD ?
Il sert à rendre une fraction irréductible, à simplifier un rapport et à partager en parts égales sans reste. Par exemple, 36/60 devient 3/5 en divisant par 12, et le plus grand carreau carré qui couvre un sol de 360 cm sur 240 cm mesure 120 cm de côté, puisque PGCD(360, 240) = 120.
Comment rendre une fraction irréductible avec le PGCD ?
Calculez le PGCD du numérateur et du dénominateur, puis divisez les deux par ce nombre. Pour 30/18, PGCD(30, 18) = 6, donc 30/6 = 5 et 18/6 = 3 : la fraction irréductible est 5/3. Elle est irréductible parce que 5 et 3 sont premiers entre eux, leur PGCD valant 1.
Comment calculer un PGCD et un PPCM ?
Le PGCD se calcule par la décomposition en facteurs premiers ou par l’algorithme d’Euclide. Le PPCM s’en déduit, car PGCD(a, b) × PPCM(a, b) = a × b, soit PPCM(a, b) = a × b / PGCD(a, b). Avec 12 et 18, le PGCD vaut 6 et le PPCM 36 : 6 × 36 = 216 = 12 × 18. Avec la décomposition, le PPCM prend chaque facteur premier avec son plus grand exposant : 2² × 3² = 36.
Que se passe-t-il si les nombres sont égaux ou si l’un divise l’autre ?
Le PGCD est alors le plus petit des nombres : PGCD(7, 7) = 7 et PGCD(3, 6) = 3, puisque le plus petit divise déjà le plus grand. Le calculateur accepte des entiers positifs jusqu’à mille milliards (1 000 000 000 000).
- Plus grand commun diviseur de nombres entiers (Wikipédia)
- Plus grand commun diviseur (Wikipédia)
- Algorithme d’Euclide (Wikipédia)
- Nombres premiers entre eux (Wikipédia)