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.
Astuces
- 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.
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.