Guide : plus grand commun diviseur (PGCD)
What is GCD?
Le plus grand commun diviseur (PGCD) est le plus grand entier qui divise sans reste deux entiers ou plus. Par exemple, PGCD(48, 18) = 6, car 6 est le plus grand nombre divisant à la fois 48 et 18 sans reste. Le PGCD est une notion fondamentale en théorie des nombres et en cryptographie.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
PGCD(a, b) * PPCM(a, b) = a * b (le produit du PGCD et du PPCM est égal au produit des nombres). Si PGCD(a, b) = 1, alors a et b sont premiers entre eux. Le PGCD est toujours inférieur ou égal au plus petit des deux nombres. PGCD(0, a) = |a| pour tout nombre a non nul.
Practical Applications
Le PGCD sert à simplifier les fractions : on divise numérateur et dénominateur par le PGCD pour obtenir une fraction irréductible. En cryptographie RSA, il intervient dans la génération des clés de chiffrement. En informatique, il détermine le plus grand découpage commun des ressources mémoire ou processeur. En musique, il permet de déterminer des intervalles communs pour les rythmes.
Euclide trouve le diviseur de deux nombres à neuf chiffres en trois étapes
Trouver ce que deux nombres ont en commun semble exiger de les factoriser, et factoriser est lent. L'algorithme d'Euclide contourne entièrement le problème : PGCD(123456789, 987654321) = 9, atteint en trois divisions. La division d'essai sur le plus petit aurait pu demander 11 111 vérifications. L'algorithme a plus de deux mille ans et reste celui qu'emploie tout ordinateur.
Comment ça marche
- Trouve le plus grand commun diviseur de deux nombres ou plus par l'algorithme d'Euclide.
- Réduit les fractions à leur forme irréductible, ce qui est la même opération sous un autre habit.
- Indique le nombre d'étapes, puisque la vitesse est tout l'enjeu.
PGCD(a, b) = PGCD(b, a mod b), répété jusqu'à b = 0 le a restant est la réponse forme irréductible : a/b divisé par PGCD(a, b) des deux côtés premiers entre eux signifie PGCD = 1 — aucun facteur commun
Exemple chiffré
Euclide sur des entrées de plus en plus méchantes.
- PGCD(1071, 462) = 21 en 3 étapes
- PGCD(123456789, 987654321) = 9 en 3 étapes
- PGCD(2⁴⁰, 3²⁰) = 1 en 15 étapes
- PGCD(832040, 514229) = 1 en 28 étapes
- cette dernière paire est faite de nombres de Fibonacci consécutifs — le pire cas qui existe
Deux nombres à neuf chiffres se résolvent en trois divisions. Même l'entrée délibérément la pire, une paire de Fibonacci consécutifs, prend 28 étapes. Le compte croît avec le nombre de chiffres, non avec la taille des nombres, ce qui explique que l'algorithme monte jusqu'à des valeurs de centaines de chiffres.
Lire le résultat
- Les nombres de Fibonacci consécutifs sont le pire cas démontré, et ils le sont précisément parce que chaque division retire le moins possible. PGCD(987, 610) prend 14 étapes et PGCD(75025, 46368) en prend 23 : le compte grimpe lentement pendant que les nombres explosent.
- Réduire une fraction est un PGCD déguisé. 84/126 partage un diviseur 42 et tombe à 2/3 en une étape ; le PGCD est exactement la limite de simplification d'une fraction, et diviser par plus petit laisse du travail en plan.
- Le plus grand commun diviseur et le plus petit commun multiple sont deux moitiés d'un même outil, liées par PGCD(a,b) × PPCM(a,b) = a × b. Disposer de l'un donne l'autre au prix d'une multiplication et d'une division.
- L'algorithme d'Euclide soutient la cryptographie moderne par sa forme étendue, qui fournit aussi les coefficients des inverses modulaires. La génération de clés RSA en dépend, ce qui fait une longue postérité pour un procédé écrit vers 300 av. J.-C.
Questions fréquentes
- Pourquoi ne pas simplement factoriser les deux nombres ?
- Parce que factoriser est difficile et Euclide non. Décomposer 123456789 en facteurs premiers est un vrai travail ; prendre trois restes ne l'est pas. La sécurité de RSA repose exactement sur cette asymétrie : multiplication et PGCD sont bon marché, la factorisation ne l'est pas.
- Que signifie un PGCD de 1 ?
- Les nombres sont premiers entre eux : ils ne partagent aucun facteur supérieur à 1. Cela ne veut pas dire que l'un est premier — 8 et 9 sont premiers entre eux et aucun n'est premier. Cela veut dire que la fraction 8/9 est déjà irréductible.