Aller au contenu principal
CalcMax

Calculatrice de PGCD

Résultat

12

Plus grand commun diviseur

Diviseurs communs
1, 2, 3, 4, 6, 12

Le plus grand commun diviseur d’une liste de nombres est le plus grand entier qui divise chacun d’eux sans laisser de reste. Pour 24, 36 et 60, c’est 12 : rien de plus grand ne divise les trois, et tous les nombres qui divisent les trois — 1, 2, 3, 4, 6 et 12 — sont des diviseurs communs. Cette page affiche les deux moitiés de la réponse, parce que le plus grand pris seul est facile à énoncer et difficile à vérifier, alors que la liste complète des diviseurs communs montre d’où il vient. Trois méthodes mènent au résultat, et les trois valent la peine d’être connues. La première consiste à écrire les diviseurs de chaque nombre et à garder le plus grand qu’ils ont en commun : c’est ce que fait le tableau plus bas pour 24, 36 et 60. La deuxième est de décomposer chaque nombre en facteurs premiers et de ne garder que les nombres premiers sur lesquels ils tombent d’accord, répétés autant de fois qu’ils sont d’accord : 24 vaut 2³ × 3, 36 vaut 2² × 3² et 60 vaut 2² × 3 × 5, donc les trois partagent 2² et un 3, et 2² × 3 font 12. La décomposition en facteurs premiers est la méthode à préférer quand les nombres sont grands mais factorisables, parce qu’elle explique pourquoi la réponse est celle-là. La troisième est l’algorithme d’Euclide, qui remplace répétitivement le plus grand des deux nombres par le reste de sa division par le plus petit : pour 1 071 et 462 cela donne 1 071 → 147 → 21, et le dernier reste non nul est la réponse, 21. Il ne demande aucune factorisation, et c’est pourquoi c’est la méthode qui tient sur des nombres qu’on ne peut pas casser à l’œil. Deux nombres dont le seul diviseur commun est 1 sont dits premiers entre eux, et leur plus grand commun diviseur vaut 1 — 9 et 20 sont premiers entre eux, et deux entiers consécutifs le sont toujours. Le diviseur sert à mettre une fraction sous forme irréductible : en divisant le numérateur et le dénominateur de 24/36 par 12 on obtient 2/3, le même nombre écrit avec le plus petit dénominateur possible.

Les diviseurs et les décompositions en facteurs premiers de 24, 36 et 60, la saisie par défaut

NombreDécomposition en facteurs premiersDiviseurs
242^3 * 31, 2, 3, 4, 6, 8, 12, 24
362^2 * 3^21, 2, 3, 4, 6, 9, 12, 18, 36
602^2 * 3 * 51, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Lisez la colonne des diviseurs de haut en bas : les trois nombres partagés sont ceux qui apparaissent dans les trois lignes, soit 1, 2, 3, 4, 6 et 12. Le plus grand d’entre eux est la réponse. La colonne des décompositions dit la même chose d’une seconde façon, et c’est la seconde qui passe à l’échelle : les nombres premiers partagés sont 2² et 3, et 2² × 3 font 12. Remarquez que la partie partagée est la plus petite puissance de chaque nombre premier partagé, et non la plus grande — 36 possède 3² mais 24 n’a que 3¹, et le diviseur doit aussi diviser 24, il n’emporte donc qu’un seul 3. Remarquez aussi que 60 apporte un nombre premier que les autres n’ont pas du tout, 5, et qu’il disparaît simplement de la réponse : un diviseur doit diviser chaque nombre de la liste, donc un nombre premier absent de l’un d’eux est absent de la réponse. Le tableau ne suit pas les nombres que vous avez tapés — le panneau au-dessus répond à ceux-là, celui-ci montre les trois méthodes se rejoignant sur un même exemple.

Formule

24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 ⇒ pgcd(24, 36, 60) = 2² × 3 = 12, et les diviseurs communs aux trois sont 1, 2, 3, 4, 6, 12

24, 36, 60
Les nombres à comparer, de deux à dix, chacun un entier de 1 à 1 000 000. Ils se séparent par des espaces, des virgules ou des points-virgules, donc 24 36 60 et 24, 36, 60 sont la même saisie. Un séparateur décimal ou une barre de fraction est refusé plutôt qu’arrondi, et 0 l’est aussi : il n’existe pas de convention unique pour pgcd(0, 0), et cette page ne va pas en choisir une à votre place
2³ × 3
La décomposition en facteurs premiers de 24 : trois facteurs deux et un facteur trois. Tout entier supérieur à 1 en a exactement une comme celle-ci, et c’est ce qui fait fonctionner la deuxième méthode
2² × 3
La partie sur laquelle les trois décompositions tombent d’accord : deux deux et un trois, donc 4 × 3 = 12. La règle est de prendre la plus petite puissance de chaque nombre premier partagé, et non la plus grande — le diviseur doit diviser tous les nombres de la liste, il ne peut donc jamais dépasser ce que le plus pingre autorise
1, 2, 3, 4, 6, 12
Tous les diviseurs communs, par ordre croissant. Le dernier est le plus grand commun diviseur, et la liste est la vérification : 12 divise 24, 36 et 60 sans reste, tandis que le diviseur suivant au-dessus, 18, ne divise que 36
pgcd(a, b, c) = pgcd(pgcd(a, b), c)
La façon dont plus de deux nombres sont traités : deux à la fois, en repliant la réponse courante dans le nombre suivant. Ce n’est pas une méthode à part, c’est la méthode à deux nombres appliquée plusieurs fois, et c’est pourquoi la page donne le même résultat pour trois nombres que pour n’importe quelle paire par laquelle vous commenceriez
premiers entre eux
Le nom donné à un couple dont le seul diviseur commun est 1, donc dont le plus grand commun diviseur vaut 1. 9 et 20 sont premiers entre eux sans qu’aucun des deux ne soit premier, et deux entiers consécutifs le sont toujours

Mettre une fraction sous forme irréductible est l’usage de tous les jours : 24/36 devient 2/3 dès qu’on divise les deux membres par 12, et c’est la première chose que fait chaque page de fractions de ce site. Réduire une recette ou un plan à son plus petit rapport entier est la même opération sous d’autres habits — un mélange écrit 24 : 36 : 60 est le même mélange que 2 : 3 : 5, et c’est la seconde version qui tient sur une étiquette. Dans un cours d’arithmétique le diviseur est demandé directement, et la liste imprimée des diviseurs communs tient lieu de brouillon : elle montre que la réponse a été trouvée en comparant des diviseurs et non devinée. Deux autres endroits où la question se pose. Carreler un rectangle avec les plus grands carreaux possibles est un problème de plus grand commun diviseur déguisé, et la réponse est la taille du carreau. Et en arithmétique, le fait que deux nombres soient premiers entre eux est la condition dont dépendent plusieurs résultats, dont celui qui porte le chiffrement RSA — un module n’est sûr que s’il est premier avec l’exposant utilisé avec lui. Quand les nombres sont rébarbatifs, 1 071 et 462 par exemple, les factoriser à la main cesse d’être praticable et l’algorithme d’Euclide prend le relais ; les exemples de la page montrent les deux chemins aboutissant au même 21. Quand vous ne voulez que la réponse sans la liste, la calculatrice d’algorithme d’Euclide déroule la boucle division par division, et la calculatrice de PPCM repose la même question à l’envers, celle du plus petit nombre que tous divisent.

Exemples détaillés

  1. Le plus grand commun diviseur de 24, 36 et 60

    1. Diviseurs de 24 : 1, 2, 3, 4, 6, 8, 12, 24
    2. Diviseurs de 36 : 1, 2, 3, 4, 6, 9, 12, 18, 36
    3. Diviseurs de 60 : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
    4. On garde ceux que les trois listes contiennent : 1, 2, 3, 4, 6, 12
    5. Le plus grand d’entre eux est 12, donc le plus grand commun diviseur vaut 12

    La saisie par défaut, et celle que le tableau plus bas déroule intégralement. Par décomposition en facteurs premiers : 24 vaut 2³ × 3, 36 vaut 2² × 3², 60 vaut 2² × 3 × 5, les trois partagent 2² et un 3, et 2² × 3 font 12. La liste des diviseurs communs est la partie à retenir — c’est la seule sortie qui montre que la réponse est le plus grand et pas seulement un diviseur partagé, puisque 8 et 9 divisent chacun deux des trois nombres mais pas les trois.

  2. Des nombres rébarbatifs : 1 071 et 462

    1. 1 071 ÷ 462 = 2 reste 147
    2. 462 ÷ 147 = 3 reste 21
    3. 147 ÷ 21 = 7 reste 0 — le reste a atteint zéro, on s’arrête
    4. Le dernier reste non nul est 21, donc le plus grand commun diviseur vaut 21
    5. Vérification par factorisation des deux : 1 071 = 3 × 7 × 51 et 462 = 2 × 3 × 7 × 11, la partie partagée est donc 3 × 7

    C’est ce couple qui justifie la présence de l’algorithme d’Euclide sur la page : aucun des deux nombres n’est factorisable au premier coup d’œil, et lister les diviseurs à la main serait long et source d’erreurs. Quatre divisions suffisent. La réponse 21 est aussi le plus grand nombre qui divise les deux, et la liste partagée est courte — 1, 3, 7, 21 — ce qui est en général le signe que deux nombres ont peu en commun.

  3. Des nombres premiers entre eux : 9 et 20

    1. Diviseurs de 9 : 1, 3, 9
    2. Diviseurs de 20 : 1, 2, 4, 5, 10, 20
    3. Le seul diviseur que les deux listes partagent est 1
    4. Le plus grand commun diviseur vaut donc 1

    Une réponse de 1 est une vraie réponse, pas un échec — les deux nombres sont premiers entre eux. Cela arrive chaque fois qu’ils ne partagent aucun nombre premier, et c’est fréquent : deux entiers consécutifs sont toujours premiers entre eux, et un nombre premier associé à un nombre dont il n’est pas un multiple l’est aussi. Sur cette page un couple premier entre eux revient avec la plus courte liste de diviseurs communs possible, un seul 1.

  4. Un nombre associé à lui-même : 36 et 36

    1. Diviseurs de 36 : 1, 2, 3, 4, 6, 9, 12, 18, 36
    2. Les deux entrées de la liste sont le même nombre, donc les deux listes de diviseurs sont identiques
    3. Le plus grand diviseur partagé est 36 lui-même

    Le haut de ce que la réponse peut atteindre : le plus grand commun diviseur d’une liste ne peut jamais dépasser le plus petit nombre de cette liste, et il touche exactement ce plafond quand le plus petit nombre divise tous les autres. Répéter un nombre dans la saisie ne change rien — le diviseur de 36 et 36 est 36, comme celui d’une liste à un seul élément.

Limites

Chaque nombre doit être un entier de 1 à 1 000 000, et il doit y en avoir entre deux et dix. Zéro est refusé, et c’est une décision et non un oubli : pgcd(0, 5) vaut 5 dans une convention courante et n’est pas défini dans d’autres, et pgcd(0, 0) vaut 0 dans certains manuels et n’est défini nulle part ailleurs. Imprimer l’une de ces réponses serait faux pour un lecteur qui suit une autre convention, donc la page demande des nombres positifs. Les nombres négatifs sont refusés pour une raison du même genre — le diviseur de −24 et 36 vaut 12 dans la plupart des présentations, mais les règles de signe forment une convention à part que cette page n’énonce pas. Les nombres décimaux et les fractions sont refusés plutôt qu’arrondis : un plus grand commun diviseur est un énoncé sur des entiers qui en divisent d’autres, et 2,5 ÷ 1,25 n’a pas de reste, ce qui rendrait la réponse vide de sens. Les séparateurs peuvent être des espaces, des virgules ou des points-virgules, mélangés ou non ; tout le reste est considéré comme faisant partie d’un nombre et rend la saisie illisible. Le tableau de référence plus bas est figé sur 24, 36 et 60 et ne suit pas ce que vous avez tapé — le panneau répond à vos nombres, le tableau montre la méthode. Les entrées répétées sont acceptées et ne changent rien. La réponse est exacte, jamais arrondie : toutes les valeurs de cette page sont des entiers bien à l’intérieur de la plage qu’une machine représente exactement.

Questions fréquentes

Comment trouver le plus grand commun diviseur à la main ?
Listez les diviseurs de chaque nombre et gardez le plus grand qu’ils partagent tous. Pour 24, 36 et 60 ces listes s’arrêtent à 12, donc le plus grand commun diviseur vaut 12. Le chemin plus rapide pour de grands nombres est l’algorithme d’Euclide : divisez le plus grand par le plus petit, remplacez le plus grand par le reste, et recommencez jusqu’à ce que le reste soit nul — pour 1 071 et 462 cela fait quatre divisions et la réponse est 21. Les deux chemins donnent le même nombre, et les deux sont déroulés dans les exemples plus haut.
Que signifie un PGCD égal à 1 ?
Que les nombres sont premiers entre eux, ce qui est une réponse normale et non le signe que quelque chose s’est mal passé. 9 et 20 ne partagent aucun nombre premier, donc 1 est le seul nombre qui divise les deux. Cela arrive souvent : deux entiers consécutifs sont premiers entre eux, et un nombre premier associé à tout ce qui n’est pas un de ses multiples l’est aussi. La liste des diviseurs communs revient alors réduite à un seul 1.
Pourquoi la page refuse-t-elle 0 et les nombres négatifs ?
Parce que la réponse dépendrait d’une convention que cette page n’énonce pas. pgcd(0, 5) vaut 5 dans beaucoup de manuels et n’est pas défini dans d’autres, et pgcd(0, 0) vaut 0 dans certains traitements et n’est pas défini du tout dans le reste. Les négatifs apportent un jeu de règles de signe qui leur est propre. Plutôt que de choisir une convention et de l’imprimer sans le dire, la page demande des entiers à partir de 1, là où toutes les sources sont d’accord.
Comment fonctionne la méthode par décomposition en facteurs premiers ?
Décomposez chaque nombre en nombres premiers, puis gardez ceux qui apparaissent dans tous les nombres, en prenant la plus petite puissance de chacun. Pour 24, 36 et 60 cela donne 2² et 3, donc la réponse est 12. La raison pour laquelle il faut la plus petite puissance est que le diviseur doit diviser chaque nombre de la liste : 36 possède 3² mais 24 n’a qu’un seul 3, donc un second 3 casserait la division de 24. La factorisation est plus lente que l’algorithme d’Euclide sur des nombres rébarbatifs, mais elle explique la réponse.
La réponse peut-elle être plus grande que le plus petit nombre de la liste ?
Non. Un diviseur commun à une liste doit diviser le plus petit nombre de cette liste, il ne peut donc jamais dépasser ce nombre, et il atteint exactement ce plafond quand le plus petit nombre divise tous les autres. Le diviseur de 36 et 36 est 36, et celui de 12, 24 et 36 est 12. Il n’est jamais plus petit que 1 non plus, puisque 1 divise tout entier.
À quoi sert le plus grand commun diviseur ?
Mettre une fraction sous forme irréductible en est l’usage le plus courant : en divisant les deux membres de 24/36 par 12 on obtient 2/3, la même valeur avec le plus petit dénominateur possible. Réduire un rapport est la même étape — 24 : 36 : 60 est le même mélange que 2 : 3 : 5. Et le fait que deux nombres soient premiers entre eux, ce qui revient à dire que leur diviseur vaut 1, est la condition dont plusieurs résultats d’arithmétique ont besoin, dont celui qui porte le chiffrement RSA.

Références

Calculatrices liées

Calculatrice de fractions simplifiéesRéduit une fraction au plus simple et donne le diviseur.Calculatrice de fractions équivalentesFractions égales à une fraction donnée, jusqu’à une limite.Calculatrice de PPCMLes quatre premiers multiples communs de deux à dix nombres.Calculatrice de fractionsAdditionne, soustrait, multiplie et divise des fractions.Calculatrice d’algorithme d’EuclidePGCD par l’algorithme d’Euclide, étape par étape.Calculatrice de facteurs premiersDécomposition en facteurs premiers, écrite avec exposants.