Calcul du PGCD (plus grand commun diviseur)

Entrez au moins 2 nombres entiers séparés par des points-virgules (;). Vous pouvez calculer d’un coup le PGCD de 3 nombres ou plus ; la décomposition en facteurs premiers de chaque nombre et les facteurs premiers communs s’affichent aussi.

Nombres entiers (séparés par des points-virgules)

Entrez uniquement des nombres entiers supérieurs ou égaux à 1, séparés par des points-virgules (exemple : 12 ; 18). 0, les nombres négatifs et les nombres décimaux ne sont pas acceptés.

Résultat

Saisissez des nombres entiers séparés par des points-virgules dans le champ à gauche et appuyez sur « Calculer ». Le résultat s’affiche ici.

Table des matières

[ Fermer X ]

Ce que vous pouvez faire sur cette page
À quoi sert ce calcul ?
Mode d'emploi
Formule
Symboles et termes
- Symboles
- Termes
Ce qu’il est utile de savoir avant de commencer
Calculer avec Excel
Calculer avec Google Sheets
Calculer avec Python
Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)
Faire faire le calcul par ChatGPT
Les atouts de DataChef
Fonctions connexes
Liste des calculatrices NumberChef

Ce que vous pouvez faire sur cette page

Saisissez des nombres entiers séparés par des points-virgules et obtenez aussitôt leur PGCD (plus grand commun diviseur)
Pas seulement 2 nombres : calculez d’un coup le PGCD de 3 nombres ou plus, par exemple « 16 ; 88 ; 104 »
La décomposition en facteurs premiers de chaque nombre et les facteurs premiers communs s’affichent aussi : vous apprenez à trouver le résultat et à le vérifier
Une explication simple des formules et des formules à copier-coller pour Excel, Google Sheets et Python sont réunies sur cette page

Seuls les nombres entiers supérieurs ou égaux à 1 (entiers positifs) sont acceptés. Cette page ne traite pas 0, les nombres négatifs ni les nombres décimaux.

À quoi sert ce calcul ?

Simplifier une fraction (l’usage le plus courant)

Pour simplifier \(\frac{12}{18}\), divisez le numérateur et le dénominateur par leur PGCD, 6, et vous obtenez \(\frac{2}{3}\) en une seule étape.
Au lieu de diviser par 2, puis par 3, etc., le PGCD donne directement la fraction irréductible. De l’école primaire au travail de tous les jours, c’est l’usage le plus fréquent du PGCD.

Répartir des objets en lots identiques sans reste (fêtes et distributions)

Vous voulez répartir 24 biscuits et 36 briquettes de jus dans le plus grand nombre possible de sachets identiques, sans rien laisser. Le nombre maximal de sachets est \(\gcd(24, 36) = 12\), avec 2 biscuits et 3 briquettes de jus dans chaque sachet.
Préparer des sachets de lots pour une kermesse ou des kits de fournitures identiques : c’est le calcul type pour répartir différents objets en groupes égaux.

Poser du carrelage et découper du papier (bricolage et conception)

Pour couvrir un sol de 330 cm sur 450 cm avec des carreaux carrés, sans joint vide ni découpe, le plus grand carreau possible mesure \(\gcd(330, 450) = 30\) cm de côté (11 rangées de 15 carreaux).
Découper un rectangle en carrés les plus grands possible sert pour carreler un sol ou un mur, ou pour découper sans perte des cartes de même taille dans une grande feuille.

Concevoir des engrenages (machines et horlogerie)

Si les nombres de dents de deux roues qui s’engrènent ont un grand PGCD, ce sont toujours les mêmes dents qui se rencontrent, et elles s’usent de façon inégale. En mécanique, une règle de base est donc de choisir des nombres de dents aussi proches que possible de nombres premiers entre eux (PGCD égal à 1).
Les engrenages des voitures et des horloges appliquent cette idée : garder le PGCD petit.

Le chiffrement qui protège Internet

Le chiffrement RSA, utilisé pour les achats en ligne et la banque en ligne, doit vérifier si deux nombres sont premiers entre eux au moment de créer ses clés, et c’est l’algorithme d’Euclide qui s’en charge.
Une méthode de calcul du PGCD vieille de plus de 2 000 ans protège aujourd’hui les communications du monde entier. Belle preuve de la longévité des mathématiques.

Formule

Avec la décomposition en facteurs premiers (la méthode de base)

Notation mathématique (l’écriture habituelle)

\(\gcd(a,\ b)\) \(=\) \(p_1 \times p_2 \times \cdots\)

En mots (les symboles remplacés par des mots)

② \(\gcd(a, b)\) : PGCD de \(a\) et \(b\) \(=\) ① produit de tous les facteurs premiers communs

La formule en mots

① On décompose les deux nombres en produits de facteurs premiers et on multiplie tous les \(p_1, p_2, \ldots\) : facteurs premiers communs

② pour obtenir le \(\gcd(a, b)\) : plus grand commun diviseur

Exemple simple

Le PGCD de 12 et 18 (12 = 2 × 2 × 3 et 18 = 2 × 3 × 3 : ils ont en commun un 2 et un 3) est

PGCD de 12 et 18 \(=\) produit des facteurs premiers communs (2 et 3)

\(12 = 2 \times 2 \times 3,\quad 18 = 2 \times 3 \times 3\)

\(\gcd(12,\ 18) = 2 \times 3 = 6\)

L’idée clé

Les facteurs premiers d’un nombre entier sont les nombres premiers obtenus en l’écrivant comme un produit de nombres premiers uniquement. Si un même facteur premier apparaît plusieurs fois dans les deux nombres, on le prend autant de fois qu’il apparaît dans le nombre qui en a le moins. Par exemple, 8 = 2 × 2 × 2 et 12 = 2 × 2 × 3 : le 2 apparaît 3 fois dans 8 et 2 fois dans 12, donc ils l’ont en commun 2 fois. Ainsi \(\gcd(8, 12) = 2 \times 2 = 4\).

L’algorithme d’Euclide (la méthode pour les grands nombres)

Notation mathématique (l’écriture habituelle)

\(\gcd(a,\ b)\) \(=\) \(\gcd(b,\ a \bmod b)\)

En mots (les symboles remplacés par des mots)

② \(\gcd(a, b)\) : PGCD de \(a\) et \(b\) \(=\) ① PGCD du « plus petit nombre \(b\) » et du « reste de la division de \(a\) par \(b\) »

La formule en mots

① On divise le plus grand nombre par le plus petit, et on remplace le couple par la paire « plus petit nombre \(b\) » et « reste \(a \bmod b\) »

② et le \(\gcd(a, b)\) : plus grand commun diviseur ne change pas. Les nombres diminuent à chaque étape, et quand le reste devient 0, le dernier diviseur est le PGCD

Exemple simple

Le PGCD de 48 et 18 (48 = 18 × 2 + 12 : le reste est 12) est

PGCD de 48 et 18 \(=\) PGCD de « 18 » et du « reste 12 »

\(48 = 18 \times 2 + 12\)

\(18 = 12 \times 1 + 6\)

\(12 = 6 \times 2 + 0\)

\(\gcd(48,\ 18) = 6\)

L’idée clé

La décomposition en facteurs premiers devient vite difficile quand les nombres grandissent (essayez de décomposer un nombre comme 134 221 : c’est en fait 79 × 1699). Avec l’algorithme d’Euclide, on répète seulement « diviser et prendre le reste », et on arrive toujours au PGCD, aussi grands que soient les nombres. La méthode figure dans les « Éléments » d’Euclide, vers le IIIe siècle av. J.-C., et on la présente souvent comme le plus ancien algorithme du monde.

PGCD de 3 nombres ou plus

Notation mathématique (l’écriture habituelle)

\(\gcd(a,\ b,\ c)\) \(=\) \(\gcd(\) \(\gcd(a,\ b)\) \(,\) \(c\) \()\)

En mots (les symboles remplacés par des mots)

③ \(\gcd(a, b, c)\) : PGCD des trois nombres \(=\) \(\gcd(\) ① PGCD de \(a\) et \(b\), calculé d’abord \(,\) ② \(c\) : le nombre restant \()\)

La formule en mots

① On calcule d’abord le \(\gcd(a, b)\) : PGCD de deux des nombres

② puis le PGCD de ce résultat et du \(c\) : le nombre restant

③ pour obtenir le \(\gcd(a, b, c)\) : PGCD des trois nombres

Exemple simple

Le PGCD de 16, 88 et 104 (d’abord, le PGCD de 16 et 88 vaut 8) est

PGCD de 16, 88 et 104 \(=\) \(\gcd(\) PGCD de 16 et 88 (8) \(,\) nombre restant (104) \()\)

\(\gcd(16,\ 88) = 8\)

\(\gcd(8,\ 104) = 8\)

\(\gcd(16,\ 88,\ 104) = 8\)

L’idée clé

Quel que soit le nombre d’entiers, en calculant le PGCD deux par deux, on obtient le PGCD de tous. Cela marche de la même façon pour 4 nombres ou plus, et changer l’ordre ne change pas le résultat. La calculatrice de cette page traite elle aussi les nombres deux par deux, exactement comme dans cette formule.

Le lien entre le PGCD et le PPCM

Notation mathématique (l’écriture habituelle)

\(\gcd(a,\ b)\) \(\times\) \(\mathrm{lcm}(a,\ b)\) \(=\) \(a \times b\)

En mots (les symboles remplacés par des mots)

① \(\gcd(a, b)\) : plus grand commun diviseur \(\times\) ② \(\mathrm{lcm}(a, b)\) : plus petit commun multiple \(=\) ③ \(a \times b\) : produit des deux nombres

La formule en mots

① On multiplie le \(\gcd(a, b)\) : plus grand commun diviseur

② par le \(\mathrm{lcm}(a, b)\) : plus petit commun multiple

③ et on obtient toujours le \(a \times b\) : produit des deux nombres

Exemple simple

Pour 12 et 18 (PGCD 6, PPCM 36) :

PGCD (6) \(\times\) PPCM (36) \(=\) produit des deux nombres (12 × 18)

\(6 \times 36 = 216\)

\(12 \times 18 = 216\)

L’idée clé

Grâce à cette relation, une fois le PGCD connu, on trouve le PPCM par \(\mathrm{lcm}(a, b) = a \times b \div \gcd(a, b)\) (pour de grands nombres, c’est plus sûr que d’écrire la liste des multiples). Attention : cette relation n’est valable telle quelle que pour deux nombres. Pour 3 nombres ou plus, elle est fausse en général.

Le plus grand commun diviseur est le plus grand nombre entier positif qui divise tous les nombres sans reste. Pour de petits nombres, multipliez leurs facteurs premiers communs. Pour de grands nombres, utilisez l’algorithme d’Euclide, qui remplace sans cesse le couple par le reste.

Symboles et termes

Symboles

\(\gcd(a, b)\)	PGCD de a et b	Le plus grand commun diviseur de \(a\) et \(b\). C’est la notation internationale, formée sur l’anglais « greatest common divisor ». En France, on écrit plutôt \(\mathrm{PGCD}(a\,;\,b)\) : c’est exactement la même chose.
\(a \bmod b\)	a modulo b	Le reste de la division euclidienne de \(a\) par \(b\). (Exemple : \(48 \bmod 18 = 12\), car 48 = 18 × 2 + 12)
\(\mathrm{lcm}(a, b)\)	PPCM de a et b	Le plus petit commun multiple de \(a\) et \(b\), d’après l’anglais « least common multiple ». En France, on écrit plutôt PPCM(a ; b). (Exemple : \(\mathrm{lcm}(12, 18) = 36\))
\(p_1, p_2, \ldots\)	p indice 1, p indice 2, etc.	Les facteurs premiers communs, dans l’ordre. Les petits nombres en bas à droite (les indices) indiquent seulement premier, deuxième, etc. Ils ne servent pas au calcul.
\(\cdots\)	points de suspension	Un symbole qui veut dire « et ainsi de suite, selon la même règle ». Ici, il indique qu’on multiplie les facteurs premiers de la même façon, quel que soit leur nombre.

Termes

diviseur	Un nombre entier positif qui divise un nombre entier sans reste. 12 a 6 diviseurs : 1, 2, 3, 4, 6 et 12.
diviseur commun	Un diviseur partagé par deux nombres entiers ou plus. Les diviseurs communs de 12 et 18 sont 1, 2, 3 et 6. Tout diviseur commun est un diviseur du plus grand commun diviseur (ici 6).
PGCD (plus grand commun diviseur)	Le plus grand des diviseurs communs. C’est le nom appris à l’école en France ; en anglais, on dit GCD (greatest common divisor) ou GCF (greatest common factor).
nombre premier	Un nombre entier supérieur ou égal à 2 dont les seuls diviseurs sont 1 et lui-même : 2, 3, 5, 7, 11, 13… 1 n’est pas un nombre premier.
décomposition en facteurs premiers	Écrire un nombre entier sous forme de produit de nombres premiers uniquement. (Exemple : \(12 = 2 \times 2 \times 3\)) Chaque nombre premier utilisé s’appelle un facteur premier.
premiers entre eux	Se dit de deux nombres entiers dont le PGCD vaut 1 (leur seul diviseur commun est 1). Comme 17 et 13, ils n’ont aucun facteur premier en commun.
algorithme d’Euclide	Une méthode pour trouver le PGCD en répétant « diviser le plus grand nombre par le plus petit, puis remplacer le couple par le plus petit nombre et le reste ». Longtemps enseignée en 3e, on la retrouve aujourd’hui en option maths expertes (Terminale). Connue depuis l’Antiquité, on la présente souvent comme le plus ancien algorithme du monde.
PPCM (plus petit commun multiple)	Le plus petit nombre entier positif qui est un multiple commun de deux nombres entiers ou plus. Il sert à réduire des fractions au même dénominateur. Pour deux nombres, \(\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b\).

Ce qu’il est utile de savoir avant de commencer

Voici ce qu’il est utile de savoir pour utiliser le calcul de cette page en le comprenant, et pas seulement en appuyant sur le bouton.
Si vous bloquez, revoir ces notions est le chemin le plus court.

Tables de multiplication et division euclidienne (CE1-CM1, 7-10 ans)	Savoir distinguer « la division tombe juste » et « il y a un reste » Savoir faire une division avec reste, par exemple 48 divisé par 18 donne 2, reste 12
Diviseurs et diviseurs communs (CM2-5e, 10-13 ans)	Savoir écrire tous les diviseurs de 12 : 1, 2, 3, 4, 6, 12 Savoir trouver les diviseurs que deux nombres ont en commun (diviseurs communs)
Simplifier une fraction (6e-5e, 11-13 ans)	Savoir que diviser le numérateur et le dénominateur par un même nombre ne change pas la valeur d’une fraction
Nombres premiers et décomposition en facteurs premiers (5e-3e, 12-15 ans)	Savoir reconnaître les nombres premiers (nombres qui n’ont pas d’autres diviseurs que 1 et eux-mêmes) Savoir décomposer un nombre entier en produit de nombres premiers, comme \(12 = 2 \times 2 \times 3\)

Calculer avec Excel

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 d’Excel. Il fonctionne tel quel.

Tableau pour calculer le PGCD de deux nombres

Premier nombre a	12
Deuxième nombre b	18
PGCD(a ; b)	=PGCD(B1;B2)

Tableau pour calculer le PGCD de 3 nombres ou plus

Nombre 1	16
Nombre 2	88
Nombre 3	104
PGCD	=PGCD(B1:B3)

Tableau pour vérifier l’algorithme d’Euclide

Plus grand nombre a	48
Plus petit nombre b	18
Reste de la division de a par b (a mod b)	=MOD(B1;B2)
PGCD(a ; b)	=PGCD(B1;B2)
PGCD(b ; reste) (identique à la ligne du dessus)	=PGCD(B2;B3)

Tableau pour vérifier PGCD × PPCM = produit des deux nombres

Premier nombre a	12
Deuxième nombre b	18
PGCD(a ; b)	=PGCD(B1;B2)
PPCM(a ; b)	=PPCM(B1;B2)
PGCD × PPCM	=B3*B4
a × b (identique à la ligne du dessus)	=B1*B2

Excel propose d’origine la fonction PGCD pour le plus grand commun diviseur. « =PGCD(B1;B2) » donne le PGCD des valeurs de B1 et B2 : le premier tableau affiche donc 6 en B3.
Avec une plage, comme « =PGCD(B1:B3) » dans le deuxième tableau, vous obtenez d’un coup le PGCD de 3 nombres ou plus (B4 affiche 8).
Le troisième tableau vérifie l’algorithme d’Euclide. Avec la fonction MOD (le reste), vous constatez que PGCD(a ; b) et PGCD(b ; reste) ont la même valeur (6 tous les deux).
Dans le quatrième tableau, PGCD × PPCM et a × b donnent tous les deux 216, ce qui confirme le lien avec le PPCM. Il suffit de remplacer les nombres saisis par les vôtres.

Calculer avec Google Sheets

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 de Google Sheets. Il fonctionne tel quel.

Tableau pour calculer le PGCD de deux nombres

Premier nombre a	12
Deuxième nombre b	18
PGCD(a ; b)	=PGCD(B1;B2)

Tableau pour calculer le PGCD de 3 nombres ou plus

Nombre 1	16
Nombre 2	88
Nombre 3	104
PGCD	=PGCD(B1:B3)

Tableau pour vérifier l’algorithme d’Euclide

Plus grand nombre a	48
Plus petit nombre b	18
Reste de la division de a par b (a mod b)	=MOD(B1;B2)
PGCD(a ; b)	=PGCD(B1;B2)
PGCD(b ; reste) (identique à la ligne du dessus)	=PGCD(B2;B3)

Tableau pour vérifier PGCD × PPCM = produit des deux nombres

Premier nombre a	12
Deuxième nombre b	18
PGCD(a ; b)	=PGCD(B1;B2)
PPCM(a ; b)	=PPCM(B1;B2)
PGCD × PPCM	=B3*B4
a × b (identique à la ligne du dessus)	=B1*B2

Google Sheets en français propose les fonctions PGCD, PPCM et MOD sous les mêmes noms qu’Excel : les mêmes formules fonctionnent telles quelles.
Copiez tout le tableau, collez-le dans la cellule A1 et remplacez les nombres saisis par les vôtres.

Calculer avec Python

from math import gcd
from functools import reduce

numbers = [330, 75, 450, 225]  # nombres entiers dont on cherche le PGCD (autant qu’on veut)

greatest_common_divisor = reduce(gcd, numbers)  # applique gcd deux par deux depuis le début

print(f"PGCD de {numbers} : {greatest_common_divisor}")

Fonctionne avec la seule bibliothèque standard. math.gcd calcule le PGCD de deux nombres entiers, et reduce s’occupe du « deux par deux ». Remplacez la liste en haut par vos nombres et lancez le programme (cet exemple affiche 15).

Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)

Avec la décomposition en facteurs premiers (la méthode de base)

gcd(a, b) = p₁ × p₂ × ⋯

\gcd(a, b) = p_1 \times p_2 \times \cdots

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <msub><mi>p</mi><mn>1</mn></msub>
    <mo>&#xD7;</mo>
    <msub><mi>p</mi><mn>2</mn></msub>
    <mo>&#xD7;</mo>
    <mo>&#x22EF;</mo>
  </mrow>
</math>

gcd(a, b) = p_1 xx p_2 xx cdots

GCD[a, b]

igcd(a, b);

g = gcd(a, b);

gcd(a, b) = p_1 × p_2 × ⋯

L’algorithme d’Euclide (la méthode pour les grands nombres)

gcd(a, b) = gcd(b, a mod b)

\gcd(a, b) = \gcd(b,\ a \bmod b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>b</mi><mo>,</mo>
    <mi>a</mi><mspace width="0,3em"/><mi>mod</mi><mspace width="0,3em"/><mi>b</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b) = gcd(b, a mod b)

GCD[a, b] == GCD[b, Mod[a, b]]

igcd(a, b) = igcd(b, a mod b);

gcd(a, b) == gcd(b, mod(a, b))

gcd(a, b) = gcd(b, a mod b)

PGCD de 3 nombres ou plus

gcd(a, b, c) = gcd(gcd(a, b), c)

\gcd(a, b, c) = \gcd(\gcd(a, b),\ c)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>,</mo><mi>c</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b, c) = gcd(gcd(a, b), c)

GCD[a, b, c]

igcd(igcd(a, b), c);

g = gcd(gcd(a, b), c);

gcd(a, b, c) = gcd(gcd(a, b), c)

Le lien entre le PGCD et le PPCM

gcd(a, b) × lcm(a, b) = a × b

\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>lcm</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>a</mi>
    <mo>&#xD7;</mo>
    <mi>b</mi>
  </mrow>
</math>

gcd(a, b) xx lcm(a, b) = a xx b

GCD[a, b]*LCM[a, b] == a*b

igcd(a, b)*ilcm(a, b) = a*b;

gcd(a, b)*lcm(a, b) == a*b

gcd(a, b) × lcm(a, b) = a × b

Faire faire le calcul par ChatGPT

Tu es un assistant de calcul sur les nombres entiers. Effectue le calcul suivant en exécutant réellement du code Python, et fonde ta réponse uniquement sur les nombres obtenus à l’exécution (ne réponds pas de tête ni par estimation).

Pour les quatre nombres entiers 330, 75, 450 et 225, trouve :
1. Le PGCD (plus grand commun diviseur) des quatre nombres
2. La décomposition en facteurs premiers de chaque nombre
3. Les facteurs premiers communs aux quatre nombres

Indique les formules utilisées et les nombres obtenus à l’exécution.

Mode d'emploi

1

Saisissez vos nombres

Tapez les nombres à calculer dans les champs de saisie
2

Calculez

Appuyez sur le bouton « Calculer »
3

Lisez le résultat

Le résultat s’affiche aussitôt. La même page explique aussi le raisonnement et la formule