Calculateur de PGCD et PPCM
Saisissez deux entiers positifs pour trouver leur plus grand commun diviseur (PGCD) grâce à l'algorithme d'Euclide, avec chaque étape du calcul affichée. Le plus petit commun multiple (PPCM) est calculé en même temps.
| Plus grand commun diviseur (PGCD) | |
|---|---|
| Plus petit commun multiple (PPCM) |
Étapes de l'algorithme d'Euclide
| Formule |
|---|
| = × + |
Qu'est-ce que l'algorithme d'Euclide ?
L'algorithme d'Euclide est une méthode classique pour trouver le plus grand commun diviseur de deux entiers. La procédure : on prend le reste de la division du plus grand nombre par le plus petit, puis on répète la même opération avec le diviseur et ce reste. Lorsque le reste atteint 0, le diviseur à cet instant est le plus grand commun diviseur. Cela permet de trouver le PGCD même de très grands nombres en relativement peu d'étapes. Il est consigné dans les « Éléments » d'Euclide, datant d'environ 300 av. J.-C., ce qui en fait l'un des plus anciens algorithmes encore utilisés aujourd'hui.
Ce qu'est le calcul du PGCD et du PPCM
Le plus grand commun diviseur (PGCD) est le plus grand entier qui divise deux entiers sans reste, et le plus petit commun multiple (PPCM) est le plus petit entier parmi les multiples communs à deux entiers. Saisissez deux entiers positifs et cet outil détermine instantanément les deux valeurs par l'algorithme d'Euclide, tout en affichant le détail du calcul étape par étape : dividende, diviseur, quotient et reste.
À la main, la voie habituelle consiste à décomposer en facteurs premiers puis à chercher les facteurs communs, mais plus les nombres grandissent, plus cette décomposition devient laborieuse. L'algorithme d'Euclide qu'emploie cet outil trouve le plus grand commun diviseur par de simples divisions répétées : des entiers comportant de nombreux chiffres suivent exactement la même marche. La saisie se limite aux entiers supérieurs ou égaux à 1 ; avec zéro, un nombre négatif ou un décimal, aucun résultat ne s'affiche.
Comment utiliser le calculateur de PGCD et PPCM
- Saisir le nombre A Tapez le premier entier positif dont vous cherchez le plus grand commun diviseur et le plus petit commun multiple.
- Saisir le nombre B Tapez le second entier positif. Lequel de A et B est le plus grand ne change rien au résultat.
- Consulter le résultat Le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) s'affichent automatiquement.
- Suivre le détail du calcul Chaque étape de l'algorithme d'Euclide (dividende = diviseur × quotient + reste) est présentée sous forme de tableau, ce qui vous permet de suivre la marche jusqu'à ce que le reste atteigne zéro.
Astuces pour en tirer le meilleur parti
- Le plus petit commun multiple (PPCM) peut se calculer avec la formule « A × B ÷ PGCD ». On l'utilise couramment pour trouver un dénominateur commun entre fractions, ou pour déterminer quand plusieurs événements de périodes différentes coïncideront.
- Si deux nombres sont premiers entre eux (leur PGCD vaut 1), leur PPCM est simplement A × B.
- Un avantage pratique de l'algorithme d'Euclide est qu'il peut calculer le PGCD de grands nombres plus rapidement qu'en passant par la décomposition en facteurs premiers.
- L'ordre dans lequel vous saisissez les deux nombres n'affecte pas le résultat : le calcul commence automatiquement par le plus grand des deux.
Quand le calcul du PGCD et du PPCM rend service
Préparer la simplification d'une fraction
Trouvez le plus grand commun diviseur du numérateur et du dénominateur : diviser les deux par ce nombre simplifie la fraction. Pour voir le résultat simplifié lui-même, un calculateur de fractions doté d'une fonction de simplification est commode.
Calculer quand plusieurs cycles coïncident
Si un événement revient tous les 3 jours et un autre tous les 5, ils retomberont le même jour 15 jours plus tard — le plus petit commun multiple de 3 et de 5. Cela s'applique à l'ajustement des cycles d'équipes et d'événements.
Vérifier devoirs de mathématiques et entraînement aux examens
Vous pouvez contrôler aussitôt si le plus grand commun diviseur ou le plus petit commun multiple obtenu à la main est juste, détail du calcul compris.
Préparer la recherche d'un dénominateur commun
Pour réduire au même dénominateur plusieurs fractions aux dénominateurs différents, le plus petit commun multiple de ces dénominateurs devient le nouveau dénominateur commun.
Saisir les bases de la cryptographie
Le calcul des plus grands communs diviseurs soutient la cryptographie moderne, notamment la génération des clés RSA : suivre le détail du calcul constitue donc un premier pas utile vers la compréhension de son fonctionnement.
Le vocabulaire employé ici
- Plus grand commun diviseur (PGCD)
- Le plus grand des entiers qui divisent sans reste deux entiers ou davantage, et qu'on appelle leurs diviseurs communs.
- Plus petit commun multiple (PPCM)
- Le plus petit des multiples que deux entiers ou davantage ont en commun, et qu'on appelle leurs multiples communs.
- Algorithme d'Euclide
- Une méthode qui considère le reste de la division du plus grand nombre par le plus petit, puis répète la même opération sur le couple diviseur-reste afin de trouver le plus grand commun diviseur. Son nom vient de l'ouvrage du mathématicien grec Euclide.
- Premiers entre eux
- Se dit de deux entiers dont le plus grand commun diviseur vaut 1. Le plus petit commun multiple de deux nombres premiers entre eux est simplement leur produit.
- Décomposition en facteurs premiers
- Le fait de ramener un entier à un produit de nombres premiers. On peut aussi obtenir le PGCD et le PPCM à partir de la combinaison des facteurs premiers communs, mais pour de grands nombres l'algorithme d'Euclide est plus rapide.
- Diviseur commun et multiple commun
- Un diviseur commun est un diviseur partagé par plusieurs entiers ; un multiple commun est un multiple qu'ils ont en commun. Le PGCD et le PPCM en sont respectivement le plus grand et le plus petit.
Questions fréquentes
Anecdote — pourquoi un algorithme vieux de 2000 ans est encore utilisé au quotidien
L'algorithme d'Euclide figure dans le livre VII des « Éléments » d'Euclide, rédigés par le mathématicien grec vers 300 av. J.-C. Il est considéré comme l'un des plus anciens algorithmes connus, et plus de deux mille ans plus tard, il reste l'un des premiers algorithmes présentés dans les manuels d'informatique.
S'il a perduré aussi longtemps, c'est grâce à son efficacité de calcul. Mathématiquement, il est démontré que le nombre d'étapes requises par l'algorithme d'Euclide est à peu près proportionnel au nombre de chiffres de l'entrée (le pire cas survenant avec des paires de nombres liées à la suite de Fibonacci), ce qui lui permet de trouver le PGCD même d'entiers énormes en un temps raisonnable.
La cryptographie moderne — le chiffrement RSA, par exemple — utilise encore le calcul du PGCD (ou sa forme étendue, l'algorithme d'Euclide étendu) lors de la génération des clés. C'est une illustration frappante de l'universalité des mathématiques qu'une découverte antique sous-tende une partie de la technologie qui sécurise aujourd'hui Internet.