Calcul du PGCD

Q: Quel est le PGCD d’un nombre et de 0 ?

Tout entier divise 0, donc gcd(a, 0) = |a|. Le PGCD de 0 et 0 n’est pas défini.

À propos du calcul du PGCD

Le plus grand commun diviseur d’un ensemble d’entiers est le plus grand entier positif qui divise exactement chacun d’eux. Il sert à simplifier des fractions, à mettre en facteur dans des expressions et à répartir des quantités en groupes égaux.

La calculatrice décompose chaque nombre en facteurs premiers et applique aussi l’algorithme d’Euclide, pour que vous puissiez comparer une méthode visuelle à la méthode la plus rapide.

Qu’est-ce que le plus grand commun diviseur ?

Un diviseur d’un nombre entier le divise sans laisser de reste : les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12. Un diviseur commun à plusieurs nombres les divise tous, et le plus grand commun diviseur est le plus grand d’entre eux. Les diviseurs de 18 sont 1, 2, 3, 6, 9 et 18 : les diviseurs communs à 12 et 18 sont donc 1, 2, 3 et 6, et le PGCD vaut 6.

Dresser la liste des diviseurs fonctionne pour de petits nombres, mais devient vite fastidieux. La décomposition en facteurs premiers et l’algorithme d’Euclide trouvent le PGCD sans liste, et les deux s’appliquent à autant de valeurs que l’on veut : le PGCD de trois nombres est le PGCD des deux premiers combiné avec le troisième.

Comment utiliser le calcul du PGCD

Saisissez de deux à dix nombres entiers séparés par des virgules ou des espaces.
Appuyez sur Calculer le PGCD.
Consultez la décomposition en facteurs premiers de chaque nombre, les facteurs premiers communs et les divisions de l’algorithme d’Euclide.

Formules

Algorithme d’Euclide

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

À partir de la décomposition en facteurs premiers

\gcd = \prod p^{\min(e_1, e_2, \ldots)}

On prend chaque facteur premier commun avec son plus petit exposant.

Lien avec le PPCM

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|

Exemple corrigé: 48, 180

L’exemple corrigé calcule le PGCD de 48 et 180. La décomposition en facteurs premiers donne $48 = 2^4 \times 3$ et $180 = 2^2 \times 3^2 \times 5$ . L’algorithme d’Euclide divise 180 par 48 (reste 36), puis 48 par 36 (reste 12), puis 36 par 12 (reste 0) : le PGCD vaut donc 12. Prendre les facteurs premiers communs avec leur plus petit exposant, $2^2 \times 3 = 12$ , le confirme, et les vérifications montrent que 48 et 180 divisés par 12 donnent 4 et 15.

La solution ci-dessous est produite par le même moteur que la calculatrice ci-dessus.

Réponse finale

12

Comment nous avons lu votre problème

Calculer le plus grand commun diviseur (PGCD) des nombres.

Solution étape par étape

Décomposition en facteurs premiers de chaque nombre
$48 = 2^{4} \times 3,\quad 180 = 2^{2} \times 3^{2} \times 5$
Algorithme d’Euclide pour GCF(48, 180)
180 = 3 × 48 + 36; 48 = 1 × 36 + 12; 36 = 3 × 12 + 0
$180 = 3 \times 48 + 36 \\ 48 = 1 \times 36 + 12 \\ 36 = 3 \times 12 + 0$
Le dernier reste non nul est le PGCD
$\gcd(48, 180) = 12$
Vérifier avec les facteurs premiers communs
Multiplier les facteurs premiers communs à tous les nombres, chacun avec son plus petit exposant.
$2^{2} \times 3 = 12$

Formules utilisées

Algorithme d’Euclide
$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$

12 est le plus grand nombre entier qui divise exactement chacun des nombres.

Vérification

48 ÷ 12 = 4
180 ÷ 12 = 15

Explication détaillée

Pourquoi l’algorithme d’Euclide fonctionne

Tout nombre qui divise $a$ et $b$ divise aussi $a - b$ , et donc aussi le reste de la division de $a$ par $b$ . Ainsi, le couple $(a, b)$ et le couple $(b, a \bmod b)$ ont exactement les mêmes diviseurs communs. Chaque étape fait diminuer les nombres, et quand le reste atteint 0, le nombre restant se divise lui-même et divise 0 : c’est donc le plus grand commun diviseur. La méthode ne demande que quelques divisions, même avec de très grands nombres, et c’est pourquoi on l’utilise en arithmétique informatique et en cryptographie.

À quoi sert le PGCD

Diviser le numérateur et le dénominateur par leur PGCD rend une fraction irréductible en une seule fois : $\frac{48}{180} = \frac{4}{15}$ . En algèbre, la première étape consiste à mettre en facteur le PGCD des coefficients, comme dans $12x + 18 = 6(2x + 3)$ . Dans les problèmes concrets, il répond à des questions comme le plus grand nombre de groupes identiques que l’on peut former : 24 crayons, 36 gommes et 60 autocollants peuvent être répartis en 12 lots identiques au maximum, car $\gcd(24, 36, 60) = 12$ .

Décomposition en facteurs premiers ou algorithme d’Euclide

La décomposition en facteurs premiers montre la structure : on voit exactement quels facteurs premiers les nombres partagent et pourquoi le résultat est ce qu’il est, ce qui est utile quand on apprend ou quand on a aussi besoin du PPCM. Son point faible : factoriser de grands nombres est lent. L’algorithme d’Euclide ne factorise rien ; il se contente de diviser et de garder les restes, si bien qu’il reste rapide avec des nombres de plusieurs dizaines de chiffres. La calculatrice présente les deux pour que chacun confirme l’autre.

Erreurs fréquentes

Multiplier tous les facteurs premiers qui apparaissent au lieu des seuls facteurs communs.
Prendre le plus grand exposant d’un facteur premier commun ; le PGCD utilise le plus petit.
Conclure qu’il n’y a pas de PGCD quand les nombres sont premiers entre eux ; dans ce cas, le PGCD vaut 1.
Arrêter l’algorithme d’Euclide une étape trop tôt et donner le dernier quotient au lieu du dernier reste non nul.

Conseils

Si un nombre divise tous les autres, c’est lui le PGCD.
Le PGCD de deux entiers consécutifs vaut toujours 1.
Utilisez le PGCD du numérateur et du dénominateur pour simplifier une fraction en une seule fois.
Vérifiez le résultat en divisant chaque nombre par celui-ci ; les quotients ne doivent avoir aucun diviseur commun autre que 1.
Avec trois nombres ou plus, calculez d’abord le PGCD de deux d’entre eux, puis combinez ce résultat avec le nombre suivant.

Questions fréquentes

Qu’est-ce que le plus grand commun diviseur ?

C’est le plus grand entier positif qui divise sans reste tous les nombres de l’ensemble. Pour 48 et 180, il vaut 12.

PGCD, GCD, GCF, HCF : est-ce la même chose ?

Oui. En français on parle de PGCD ; en anglais, GCD, GCF et HCF désignent ce même nombre.

Comment fonctionne l’algorithme d’Euclide ?

Divisez le plus grand nombre par le plus petit et gardez le reste. Remplacez le couple par (plus petit, reste) et recommencez jusqu’à obtenir un reste de 0 ; le dernier diviseur non nul est le PGCD.

Quel est le PGCD de nombres sans diviseur commun ?

Il vaut 1. On dit que ces nombres sont premiers entre eux, comme 8 et 15.

Peut-on calculer le PGCD de nombres négatifs ?

Oui. La divisibilité ne dépend pas du signe : le PGCD se calcule avec les valeurs absolues et il est toujours positif.

Quel est le PGCD d’un nombre et de 0 ?

Tout entier divise 0, donc $\gcd(a, 0) = |a|$ . Le PGCD de 0 et 0 n’est pas défini.

Comment calculer le PGCD de trois nombres ?

Calculez le PGCD de deux d’entre eux, puis le PGCD de ce résultat et du troisième. Pour 24, 36 et 60 : $\gcd(24, 36) = 12$ et $\gcd(12, 60) = 12$ .

Comment le PGCD aide-t-il à simplifier les fractions ?

Divisez le numérateur et le dénominateur par leur PGCD et la fraction devient aussitôt irréductible. Comme $\gcd(48, 180) = 12$ , on a $\frac{48}{180} = \frac{4}{15}$ .

Essayez le calcul du PGCD

Saisissez vos nombres et comparez la décomposition en facteurs premiers avec l’algorithme d’Euclide.

Utiliser la calculatrice Demander au solveur IA

À propos du calcul du PGCD

Qu’est-ce que le plus grand commun diviseur ?

Comment utiliser le calcul du PGCD

Formules

Algorithme d’Euclide

À partir de la décomposition en facteurs premiers

Lien avec le PPCM

Exemple corrigé: 48, 180

Réponse finale

Comment nous avons lu votre problème

Solution étape par étape

Formules utilisées

Vérification

Explication détaillée

Pourquoi l’algorithme d’Euclide fonctionne

À quoi sert le PGCD

Décomposition en facteurs premiers ou algorithme d’Euclide

Erreurs fréquentes

Conseils

Questions fréquentes

Qu’est-ce que le plus grand commun diviseur ?

PGCD, GCD, GCF, HCF : est-ce la même chose ?

Comment fonctionne l’algorithme d’Euclide ?

Quel est le PGCD de nombres sans diviseur commun ?

Peut-on calculer le PGCD de nombres négatifs ?

Quel est le PGCD d’un nombre et de 0 ?

Comment calculer le PGCD de trois nombres ?

Comment le PGCD aide-t-il à simplifier les fractions ?

Essayez le calcul du PGCD

Autres calculatrices de maths