Qu'est-ce que le plus grand commun diviseur ?
Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand nombre entier positif qui divise les deux nombres sans laisser de reste. Par exemple, le PGCD de 48 et 36 vaut 12, car 12 est le plus grand nombre qui divise exactement ces deux valeurs. Ce calculateur de PGCD vous donne instantanément ce résultat et affiche également le plus petit commun multiple (PPCM).
Comment utiliser ce calculateur
Saisissez vos deux nombres entiers dans les champs A et B, puis consultez le résultat. L'outil utilise la valeur absolue de chaque saisie : les nombres négatifs sont donc pris en charge correctement. Si vous entrez 0 pour l'un des nombres, le PGCD est égal à l'autre nombre (puisque tout entier divise 0).
L'algorithme d'Euclide expliqué
Ce calculateur s'appuie sur l'algorithme d'Euclide, l'un des plus anciens algorithmes encore largement utilisés aujourd'hui. Il repose sur une propriété simple : \(\gcd(a,\ b) = \gcd(b,\ a \bmod b)\). On remplace de façon répétée le plus grand nombre par le reste de la division des deux nombres, jusqu'à ce que ce reste atteigne 0. Le dernier diviseur non nul est le PGCD. Cette méthode évite de factoriser les nombres et reste extrêmement rapide, même pour de très grandes valeurs.
Exemple détaillé
Calculons \(\gcd(48,\ 36)\) :
$$48 \bmod 36 = 12 \rightarrow \gcd(36,\ 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12,\ 0) = \mathbf{12}.$$
Le PPCM vaut alors $$\frac{\left|48 \times 36\right|}{12} = \frac{1728}{12} = \mathbf{144}.$$
FAQ
Quelle est la différence entre PGCD et HCF ? Aucune : ce sont deux noms pour la même valeur. En français on parle de « PGCD » (plus grand commun diviseur), tandis que l'anglais utilise « greatest common divisor » (GCD) aux États-Unis et « highest common factor » (HCF) au Royaume-Uni.
Quel est le PGCD de deux nombres premiers entre eux ? Il vaut toujours 1. Des nombres comme 8 et 15 n'ont aucun diviseur commun autre que 1 : on dit qu'ils sont premiers entre eux (ou coprimes).
Le PGCD peut-il être plus grand que le plus petit des deux nombres ? Non. Le PGCD ne peut jamais dépasser le plus petit des deux nombres saisis, et il lui est exactement égal lorsque ce nombre divise le plus grand.
