Calculer en ligne le PGCD ou Plus Grand Commun Diviseur


Avez-vous des suggestions pour améliorer cette page ?

Utilisez ce calculateur pour calculer le PGCD (ou Plus Grand Commun Diviseur) de deux ou plusieurs nombres entiers.
Saisissez des nombres entiers positifs séparés par des virgules pour calculer leur PGCD. Exemple : 125,35,15,45

Qu'est ce que le PGCD ?

Le PGCD (ou Plus Grand Commun Diviseur) de 2 entiers est le plus grand diviseur commun à ces 2 entiers.

Exemple: quelle est le PGCD de 14 et 49 ?

Diviseurs de 14 = 1, 2, 7, 14
Diviseurs de 49 = 1, 7, 49

On remarque que les diviseurs communs à 14 et 49 sont 1 et 7. Le PGCD est le plus grand d'entre eux, donc,
PGCD(14 , 49) = 7.

Comment calculer le PGCD ?

Il existe plusieurs méthodes pour calculer le PGCD.

Méthode des diviseurs : C'est la méthode qui découle directement de la définition.
- On liste les diviseurs des entiers en question (par exemple à l'aide ce calculateur Trouver les diviseurs d'un nombre).
- On extrait la liste des diviseurs communs.
- Le PGCD est le plus grand nombre de cette dernière liste.

Exemple : Quelle est le PGCD de 54 et 81 ?

Diviseurs de 54 = 1, 2, 3, 6, 9, 18, 27, 54
Diviseurs de 81 = 1, 3, 9, 27, 81

La liste des diviseurs communs à 54 et 81 est : 1, 3, 9, 27
Le plus grand élément de cette liste est 27. On déduit,
PGCD(54,81) = 27

Cette méthode n'est pas recommandée car elle exige de calculer tous les diviseurs des entiers en question ce qui peut être fastidieux pour les grands nombres. Les 2 méthodes ci-dessous sont plus rapides.

Méthode des soustractions successives

Cette méthode découle du principe suivant: si un nombre est un diviseur commun à 2 entiers alors il divise leur différence.
Appliqué au PGCD de 2 entiers a et b (qui est un diviseur commun à a et b) cela donne, le PGCD (a , b) divise a - b !

On reprend le même exemple : Quelle est le PGCD de 54 et 81 ?

On calcule la différence entre les 2 entiers
81 - 54 = 27
On répète l'opération avec le couple constitué du plus petit nombre (54) et de la différence calculée (27):
54 - 27 = 27
On répète l'opération avec le couple constitué du plus petit nombre (27) et de la différence calculée (27):
27 - 27 = 0

le PGCD est le dernier résultat de la différence avant 0. Si on atteint 1, le PGCD = 1 (nombres premiers entre eux!).

Dans notre cas, PGCD(81,54) = 27

Méthode d'Euclide

Cette méthode est la conséquence du lemme d'Euclide. C'est la méthode la plus rapide pour trouver le PGCD de deux nombres !

Pour trouver le PGCD de 2 nombres a et b, procéder par étapes,

- Faire la division euclidienne de a (le plus grand des 2 entiers) par b, on obtient un quotient q et un reste r
- Répéter la même opération en remplaçant le couple (a,b) par (b,r) jusqu'à arriver à un reste nul
- Le PGCD (a,b) est égale au dernier reste non nul

Exemple: Quelle est le PGCD de 54 et 81 ?

- 81 ÷ 54 = 1 reste 27
- on répète la même opération en remplaçant a par b (= 54) et b par le reste (= 27)
54 ÷ 27 = 2 reste 0

Le PGCD = 27 (dernier reste non nul).

Autre exemple: Quelle est le PGCD de 544 et 88 ?

- 544 ÷ 88 = 6 reste 16
- 88 ÷ 16 = 5 reste 8
- 16 ÷ 8 = 2 reste 0

Le dernier reste non nul est 8 donc PGCD(544, 88) = 8

Cas particuliers

- Si b est un diviseur de a, alors le PGCD de a et b est égal à b.
- Si le PGCD de a et b est égal à 1, on dit que a et b sont des nombres premiers entre eux (ou étrangers).

Propriétés du PGCD (avancé)

a et b sont deux entiers non nuls alors,
- PGCD(a , b) divise PPCM(a , b) (plus petit commun multiple commun)

- Si on multiplie a et b par un même entier naturel k alors leur PGCD est multiplié par k.
PGCD(k.a , k. b) = k.PGCD(a , b)

- Le produit de leur PGCD par leur PPCM est égal à la valeur absolue de leur produit. Cela peut s'écrire,
PGCD(a , b) x PPCM(a , b) = |a x b|

- Tout diviseur commun à deux entiers divise leur PGCD. Autrement dit, si a et b sont 2 entiers et p un diviseur commun à a et b alors, p divise PGCD(a , b).

Programmation

Voici comment on programme le calcul du PGCD de deux nombres entiers.

Python


def pgcd(a,b):
    while b:
        a, b = b, a%b
    return a

Voir aussi

Trouver les diviseurs d'un nombre
PPCM (plus petit commun multiple)
Division euclidienne (ou entière)