Aller au contenu

PGCD : définition, calcul et algorithme d'Euclide

Le PGCD (plus grand commun diviseur) de deux entiers est le plus grand nombre qui les divise tous les deux : PGCD(84 ; 126) = 42. Le calculateur ci-dessous trouve le PGCD de deux ou trois nombres et rédige l'algorithme d'Euclide ou celui des soustractions, avec une vérification par la décomposition en facteurs premiers.

Sommaire
  1. Qu'est-ce que le PGCD ?
  2. Méthode 1 : l'algorithme d'Euclide
  3. Méthode 2 : les soustractions successives
  4. Méthode 3 : la décomposition en facteurs premiers
  5. Quelle méthode choisir ?
  6. Le PGCD de trois nombres
  7. Nombres premiers entre eux
  8. Propriétés du PGCD
  9. À quoi sert le PGCD ?
  10. Les erreurs fréquentes
  11. Questions fréquentes

Calcul du PGCD

Étapes de résolution

La méthode en bref

  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
  2. Le PGCD est le dernier reste non nul
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant
  4. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre eux
  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
    Division euclidienneReste
    126 = 84 × 1 + 4242
    84 = 42 × 2 + 00
  2. Le PGCD est le dernier reste non nulPGCD(84 ; 126) = 42
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant84 = 22 × 3 × 7 ; 126 = 2 × 32 × 7facteurs communs : 2 × 3 × 7 = 42
  4. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre euxPGCD(84 ; 126) = 42

PGCD(84 ; 126) = 42

Choisissez la méthode avec les boutons, saisissez des entiers strictement positifs, puis lancez le calcul. Pour deux nombres, l'encadré « En bref » indique aussi si les nombres sont premiers entre eux, la fraction a/b simplifiée et le PPCM.

Qu'est-ce que le PGCD ?

Un diviseur commun à deux entiers a et b est un entier qui divise à la fois a et b. Le PGCD de deux entiers non nuls, noté PGCD(a ; b) ou p.g.c.d., est le plus grand de ces diviseurs communs. En anglais, on parle de gcd (greatest common divisor).

Exemple avec 24 et 36 :

  • diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24 ;
  • diviseurs de 36 : 1, 2, 3, 4, 6, 9, 12, 18, 36 ;
  • diviseurs communs : 1, 2, 3, 4, 6, 12.

Le plus grand est 12 : PGCD(24 ; 36) = 12. On remarque que les diviseurs communs (1, 2, 3, 4, 6, 12) sont exactement les diviseurs de 12. C'est une propriété générale : les diviseurs communs à a et b sont les diviseurs de leur PGCD.

Lister les diviseurs fonctionne pour de petits nombres, mais devient vite long. Trois méthodes plus efficaces existent ; elles s'appuient sur les notions du cours d'arithmétique : division euclidienne et nombres premiers.

Méthode 1 : l'algorithme d'Euclide

L'algorithme d'Euclide repose sur une propriété : si a = bq + r est la division euclidienne de a par b, alors

PGCD(a ; b) = PGCD(b ; r)

En effet, tout diviseur commun à a et b divise r = a − bq, et tout diviseur commun à b et r divise a = bq + r : les deux couples ont les mêmes diviseurs communs, donc le même PGCD.

  1. Diviser le plus grand par le plus petit. On note le reste.
  2. Recommencer avec le diviseur et le reste. Le diviseur devient le dividende, le reste devient le diviseur.
  3. S'arrêter au reste nul. Le PGCD est le dernier reste non nul.

Exemple : PGCD(84 ; 126) par l’algorithme d’Euclide

La méthode en bref

  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
  2. Le PGCD est le dernier reste non nul
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant
  4. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre eux
  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
    Division euclidienneReste
    126 = 84 × 1 + 4242
    84 = 42 × 2 + 00
  2. Le PGCD est le dernier reste non nulPGCD(84 ; 126) = 42
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant84 = 22 × 3 × 7 ; 126 = 2 × 32 × 7facteurs communs : 2 × 3 × 7 = 42
  4. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre euxPGCD(84 ; 126) = 42

PGCD(84 ; 126) = 42

Avec des nombres plus grands, la méthode reste courte. Pour 1 071 et 462 : 1 071 = 462 × 2 + 147, puis 462 = 147 × 3 + 21, puis 147 = 21 × 7 + 0. Le dernier reste non nul est 21 : PGCD(1 071 ; 462) = 21. Trois divisions ont suffi, là où la liste des diviseurs aurait demandé des dizaines d'essais.

Les restes diminuent strictement à chaque étape, ce qui garantit que l'algorithme s'arrête. Une erreur courante consiste à donner le dernier quotient, ou le reste nul, au lieu du dernier reste non nul.

Méthode 2 : les soustractions successives

L'algorithme des différences utilise une propriété voisine : PGCD(a ; b) = PGCD(b ; a − b) lorsque a > b. On soustrait le plus petit nombre au plus grand, on garde le plus petit et la différence, et l'on recommence jusqu'à obtenir deux nombres égaux : c'est le PGCD.

CoupleSoustractionNouveau couple
(126 ; 84)126 − 84 = 42(84 ; 42)
(84 ; 42)84 − 42 = 42(42 ; 42)
(42 ; 42)nombres égauxPGCD = 42

La méthode ne demande que des soustractions, mais elle peut être très longue quand les nombres sont éloignés : pour 1 000 et 3, il faut soustraire 3 plus de 330 fois, alors que l'algorithme d'Euclide conclut en deux divisions (1 000 = 3 × 333 + 1, puis 3 = 1 × 3 + 0). Une division euclidienne regroupe en fait plusieurs soustractions du même nombre.

Méthode 3 : la décomposition en facteurs premiers

On écrit la décomposition en produit de facteurs premiers de chaque nombre, puis on garde les facteurs premiers communs, chacun avec son plus petit exposant.

Avec 360 et 756 : 360 = 23 × 32 × 5 et 756 = 22 × 33 × 7. Les facteurs communs sont 2 et 3 ; le plus petit exposant de 2 est 2, celui de 3 est 2. Donc PGCD(360 ; 756) = 22 × 32 = 36. Vérification : 360 = 36 × 10 et 756 = 36 × 21, et 10 et 21 n'ont plus de diviseur commun autre que 1.

Cette méthode est la plus visuelle et elle donne le PPCM en même temps (on prend alors le plus grand exposant). Elle suppose en revanche de savoir décomposer, ce qui devient difficile quand les nombres ont de grands facteurs premiers.

Quelle méthode choisir ?

MéthodeAvantageLimite
Liste des diviseursIntuitive, montre la définitionRéservée aux petits nombres
Algorithme d'EuclideRapide, même pour de grands nombresDemande de poser des divisions
Soustractions successivesSeulement des soustractionsTrès longue si les nombres sont éloignés
DécompositionDonne aussi le PPCM, se lit facilementDifficile si les facteurs premiers sont grands

Le PGCD de trois nombres

Pour trois entiers, on calcule le PGCD des deux premiers, puis le PGCD de ce résultat avec le troisième. Par décomposition, on garde les facteurs premiers présents dans les trois nombres, avec leur plus petit exposant.

PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c)

Exemple : PGCD de trois nombres

La méthode en bref

  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
  2. Le PGCD est le dernier reste non nul
  3. On utilise PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c) : on recommence avec 42 et 210
  4. Dernier reste non nul
  5. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant
  6. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre eux
  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
    Division euclidienneReste
    126 = 84 × 1 + 4242
    84 = 42 × 2 + 00
  2. Le PGCD est le dernier reste non nulPGCD(84 ; 126) = 42
  3. On utilise PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c) : on recommence avec 42 et 210
    Division euclidienneReste
    210 = 42 × 5 + 00
  4. Dernier reste non nulPGCD(84 ; 126 ; 210) = 42
  5. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant84 = 22 × 3 × 7 ; 126 = 2 × 32 × 7 ; 210 = 2 × 3 × 5 × 7facteurs communs : 2 × 3 × 7 = 42
  6. Le PGCD est différent de 1 : les nombres ne sont pas premiers entre euxPGCD(84 ; 126 ; 210) = 42

PGCD(84 ; 126 ; 210) = 42

Nombres premiers entre eux

Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1. Ce n'est pas la même chose que d'être des nombres premiers : 8 et 9 sont premiers entre eux, alors qu'aucun des deux n'est premier. À l'inverse, deux nombres premiers distincts sont toujours premiers entre eux, de même que deux entiers consécutifs.

Exemple : 35 et 64 sont-ils premiers entre eux ?

La méthode en bref

  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
  2. Le PGCD est le dernier reste non nul
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant
  4. Le PGCD vaut 1 : les nombres sont premiers entre eux
  1. Algorithme d’Euclide : on divise le plus grand par le plus petit, puis le diviseur par le reste, jusqu’à obtenir un reste nul
    Division euclidienneReste
    64 = 35 × 1 + 2929
    35 = 29 × 1 + 66
    29 = 6 × 4 + 55
    6 = 5 × 1 + 11
    5 = 1 × 5 + 00
  2. Le PGCD est le dernier reste non nulPGCD(35 ; 64) = 1
  3. Vérification par la décomposition en facteurs premiers : on garde les facteurs communs, avec le plus petit exposant35 = 5 × 7 ; 64 = 26aucun facteur premier commun, donc PGCD = 1
  4. Le PGCD vaut 1 : les nombres sont premiers entre euxPGCD(35 ; 64) = 1

PGCD(35 ; 64) = 1

Propriétés du PGCD

  • Si b divise a, alors PGCD(a ; b) = b : PGCD(45 ; 15) = 15.
  • PGCD(a ; 1) = 1 et PGCD(a ; a) = a. Par convention, PGCD(a ; 0) = a, puisque tout entier divise 0.
  • Multiplier les deux nombres par k multiplie le PGCD par k : PGCD(840 ; 1 260) = 10 × PGCD(84 ; 126) = 420.
  • Si d = PGCD(a ; b), alors a/d et b/d sont premiers entre eux : 84/42 = 2 et 126/42 = 3.
  • Le PGCD et le PPCM sont liés : PGCD(a ; b) × PPCM(a ; b) = a × b.

En terminale (option mathématiques expertes), le théorème de Bézout précise qu'il existe des entiers u et v tels que au + bv = PGCD(a ; b). Pour 84 et 126 : 84 × (−1) + 126 × 1 = 42. On les obtient en « remontant » l'algorithme d'Euclide.

À quoi sert le PGCD ?

Rendre une fraction irréductible

Diviser le numérateur et le dénominateur par leur PGCD donne directement la fraction irréductible, en une seule étape. Comme PGCD(84 ; 126) = 42 :

84126 = 84 ÷ 42126 ÷ 42 = 23

Diviser par un diviseur commun plus petit, comme 2 ou 6, simplifie aussi, mais il faut alors recommencer. La méthode complète est sur la page pour simplifier une fraction.

Résoudre un problème de partage

Énoncé. Un fleuriste dispose de 84 roses et de 126 tulipes. Il veut composer le plus grand nombre possible de bouquets identiques en utilisant toutes les fleurs. Combien de bouquets peut-il faire, et que contient chacun ?

Raisonnement. Le nombre de bouquets doit diviser 84 (pour répartir les roses) et 126 (pour répartir les tulipes) : c'est un diviseur commun. On veut le plus grand, donc on cherche PGCD(84 ; 126) = 42.

Conclusion. Il compose 42 bouquets, chacun formé de 84 ÷ 42 = 2 roses et de 126 ÷ 42 = 3 tulipes.

Paver un rectangle avec des carrés

Une pièce mesure 3,60 m sur 2,25 m. On veut la carreler avec des dalles carrées identiques, les plus grandes possible, sans découpe. En centimètres, le côté de la dalle doit diviser 360 et 225. Par l'algorithme d'Euclide : 360 = 225 × 1 + 135, 225 = 135 × 1 + 90, 135 = 90 × 1 + 45, 90 = 45 × 2 + 0. Les dalles mesurent donc 45 cm de côté, et il en faut 8 × 5 = 40, puisque 360 ÷ 45 = 8 et 225 ÷ 45 = 5.

Repérez les mots-clés de l'énoncé : « le plus grand nombre de… », « la plus grande taille possible », « identiques », « sans reste » signalent un PGCD. « La prochaine fois que… », « en même temps » signalent un PPCM.

Les erreurs fréquentes

  • Donner le reste nul ou le dernier quotient : le PGCD est le dernier reste non nul.
  • Inverser dividende et diviseur à l'étape suivante : on divise toujours l'ancien diviseur par le reste.
  • Prendre le plus grand exposant dans la décomposition : c'est la règle du PPCM, pas du PGCD.
  • Confondre « premiers entre eux » et « premiers » : 8 et 9 sont premiers entre eux sans être premiers.
  • Oublier de vérifier : le PGCD doit diviser les deux nombres, et les quotients obtenus doivent être premiers entre eux.

Pour contrôler un exercice entier, le solveur mathématique en ligne rédige aussi les calculs de fractions qui suivent souvent un calcul de PGCD.

Questions fréquentes

Que veut dire PGCD ?

PGCD signifie « plus grand commun diviseur ». Le PGCD de deux entiers non nuls a et b, noté PGCD(a ; b), est le plus grand entier qui divise à la fois a et b. Par exemple, PGCD(24 ; 36) = 12.

Comment trouver le plus grand diviseur commun de deux nombres ?

Pour de petits nombres, listez les diviseurs de chacun et prenez le plus grand qui leur est commun. Pour de grands nombres, utilisez l'algorithme d'Euclide : divisez le plus grand par le plus petit, puis le diviseur par le reste, et recommencez jusqu'à obtenir un reste nul. Le PGCD est le dernier reste non nul.

Comment calculer le PGCD de 3 nombres ?

On calcule le PGCD des deux premiers, puis le PGCD de ce résultat et du troisième : PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c). Avec 84, 126 et 210 : PGCD(84 ; 126) = 42, puis PGCD(42 ; 210) = 42. Par décomposition, on garde les facteurs premiers communs aux trois nombres, avec leur plus petit exposant.

Quel est le PGCD de deux nombres premiers entre eux ?

Il vaut 1, par définition : deux nombres sont premiers entre eux quand leur seul diviseur commun positif est 1. C'est le cas de deux entiers consécutifs, de deux nombres premiers distincts, ou de nombres comme 35 et 64, qui ne sont pourtant pas premiers.

Quelle est la différence entre PGCD et PPCM ?

Le PGCD est le plus grand diviseur commun : il est inférieur ou égal au plus petit des deux nombres. Le PPCM est le plus petit multiple commun : il est supérieur ou égal au plus grand. Pour 12 et 18, PGCD = 6 et PPCM = 36, et l'on a toujours PGCD × PPCM = a × b : 6 × 36 = 12 × 18.

À lire aussi

Mis à jour le 6 octobre 2026