Calculer le PGCD et le PPCM de plusieurs nombres
Le PGCD (plus grand commun diviseur) et le PPCM (plus petit commun multiple) se calculent d'ordinaire pour deux nombres. Pour une liste de plusieurs nombres, le principe reste le même : on réduit la liste par paires successives, l'algorithme d'Euclide s'appliquant à chaque étape. Autant d'entiers que nécessaire, séparés par une virgule ou un espace.
La liste de nombres
Un astérisque en exposant renvoie au lexique, tout en bas de l'article.
Ce que mesurent le PGCD et le PPCM d'une liste
Deux entiers, trois, vingt : la question ne change pas. Quel est le plus grand entier qui les divise tous ? Quel est le plus petit entier positif dont ils sont tous des diviseurs ?
Le PGCD* de 24, 36 et 60, c'est 12. Douze coupe chacun des trois. Treize, non. Vingt-quatre ne divise que 24, ni 36 ni 60. Rien de plus grand que 12 ne traverse toute la liste. Le PPCM*, dans l'autre sens, vaut 360 : multiple de 24, de 36 et de 60, et aucun positif plus petit n'y arrive. 720 marcherait aussi — n'importe quel commun multiple marcherait — mais 360 est le plus économe.
La plupart des calculateurs s'arrêtent à une paire. Ici la liste tient jusqu'à vingt entiers, parce que le passage de deux à n n'invente aucune opération nouvelle : on enchaîne. C'est le sujet de cette page, et de toute une rubrique d'arithmétique autour des diviseurs, des multiples et des facteurs premiers.
L'algorithme d'Euclide : restes, quotients, et pourquoi ça s'arrête
Euclide, au livre VII des Éléments, ne factorise pas. Il divise, il garde le reste, il recommence. Quand le reste tombe à zéro, le dernier diviseur utilisé est le PGCD.
Chaque ligne s'écrit a = q·b + r, avec q le quotient entier et r le reste, 0 ≤ r < b. On pose ensuite a ← b et b ← r. Prenons 1071 et 462, un couple moins usé que 12 et 18 du formulaire.
- 1071 = 2·462 + 147
- 462 = 3·147 + 21
- 147 = 7·21 + 0
Le dernier reste non nul est 21. Donc PGCD(1071, 462) = 21. Trois divisions, et c'est fini. Le tableau de cette page retrace exactement ces lignes, paire après paire.
a = q·b + r (répété jusqu'à r = 0 ; le dernier reste non nul est le PGCD)
Pourquoi ça s'arrête toujours ? Parce que les restes forment une suite d'entiers strictement décroissante. r est plus petit que b, le prochain reste sera plus petit que r, et on ne descend pas indéfiniment dans les naturels. Une poignée d'étapes, pas des centaines, même pour des milliers. Reste que le nombre exact d'étapes dépend du couple : on y revient avec Fibonacci.
Réduire par paires successives : l'associativité suffit
Le PGCD de trois nombres n'est pas une troisième opération. C'est le plus grand entier qui divise les trois, et l'associativité suffit à le calculer.
PGCD(a, b, c) = PGCD(PGCD(a, b), c)
PPCM(a, b, c) = PPCM(PPCM(a, b), c)
On prend les deux premiers, on calcule, on enchaîne avec le suivant. L'ordre de la liste n'a pas d'importance : PGCD(PGCD(a, b), c) = PGCD(a, PGCD(b, c)). Pour le PPCM, même geste, avec la formule à deux arguments à chaque tour :
PPCM(a, b) = a · b / PGCD(a, b)
Sur 24, 36, 60 : PGCD(24, 36) = 12, puis PGCD(12, 60) = 12. Côté multiples, PPCM(24, 36) = 72, puis PPCM(72, 60) = 360. Douze divise les trois, aucun entier plus grand ne le fait, et 360 est bien le plus petit commun multiple. Une liste de vingt nombres ne demande rien de plus qu'une boucle de dix-neuf réductions — c'est ce que fait cette page, en affichant chaque a = q·b + r.
Au fond, il n'existe pas de « PGCD global » distinct du PGCD usuel. PGCD(a, b, c) est PGCD(PGCD(a, b), c). Point. Ce n'est pas non plus le minimum des PGCD deux à deux : pour 6, 10 et 15, les paires donnent 2, 3 et 5, alors que le PGCD des trois vaut 1.
Min et max d'exposants : la voie par les facteurs premiers
Autre méthode, plus parlante tant que les nombres restent petits : casser chaque entier en produit de nombres premiers, puis lire les exposants.
Le PGCD garde, pour chaque premier, le plus petit exposant rencontré. Le PPCM garde le plus grand. Un premier qui n'apparaît que d'un côté tombe du PGCD (exposant 0) et reste dans le PPCM.
Exemple, 180 et 48 :
- 180 = 22 × 32 × 5
- 48 = 24 × 3
- PGCD = 22 × 3 = 12
- PPCM = 24 × 32 × 5 = 720
Vérification : 180 × 48 = 8 640, et 12 × 720 = 8 640. La formule PPCM(a, b) = a·b / PGCD(a, b) n'est pas un raccourci empirique, c'est exactement cette lecture d'exposants, réécrite sans factoriser. Concrètement, c'est pédagogique tant que les nombres tiennent sur une ligne. Factoriser 999 983 n'a rien d'amusant, alors qu'Euclide en aura fini en quelques restes. Cette page suit Euclide, pas la factorisation — et c'est volontaire.
Premiers entre eux : PGCD égal à 1, ensemble ou deux à deux
Deux entiers sont premiers entre eux* lorsque leur seul diviseur commun positif est 1. On dit aussi qu'ils sont copremiers. Ça ne veut pas dire qu'ils sont premiers : 35 et 12 ne le sont ni l'un ni l'autre, et pourtant PGCD(35, 12) = 1.
La propriété se lit tout de suite sur les facteurs : aucun premier n'est partagé. Deux entiers consécutifs le sont toujours (14 et 15, 100 et 101). Un nombre et son successeur n'ont aucun facteur commun possible, puisque tout diviseur de n qui diviserait aussi n+1 diviserait leur différence, donc 1.
Pour une liste, « premiers entre eux dans leur ensemble » signifie PGCD(a, b, c, …) = 1. Ce n'est pas la même chose que « premiers entre eux deux à deux ». 8, 15 et 21 donnent PGCD(8, 15, 21) = 1, mais PGCD(15, 21) = 3. Le PGCD global à 1 n'interdit pas des paires qui partagent encore un facteur. Les critères de divisibilité aident à voir ces facteurs d'un coup d'œil, avant même de lancer Euclide.
Le PPCM comme date de rendez-vous (bus, feux, engrenages)
Le PPCM répond à une question très terre à terre : quand ces cycles retomberont-ils ensemble ?
Deux tramways, l'un toutes les 8 minutes, l'autre toutes les 12, partis ensemble à 7 h. Ils se recroisent au même arrêt après PPCM(8, 12) = 24 minutes, donc à 7 h 24. Trois feux de 15, 20 et 30 secondes reviennent au vert simultané toutes les PPCM(15, 20, 30) = 60 secondes. Deux pignons de 14 et 21 dents se réalignent après 42 dents — le même calcul, un autre vocabulaire.
Dès qu'il y a plus de deux périodes, on enchaîne les paires, exactement comme plus haut. Si les périodes ne sont pas entières (2,5 min et 4 min), on se ramène à des entiers (5 demi-minutes et 8) avant de calculer. Cette page, elle, ne prend que des entiers strictement positifs.
Simplifier une fraction par le PGCD du numérateur et du dénominateur
Pour rendre une fraction irréductible, on divise le numérateur et le dénominateur par leur PGCD. Rien d'autre. Le calculateur de fractions s'en sert ; ici on voit d'où vient le diviseur.
180/48, pour reprendre l'exemple factorisé plus haut : PGCD(180, 48) = 12, donc
180 / 48 = (180 ÷ 12) / (48 ÷ 12) = 15 / 4
15 et 4 sont premiers entre eux, la fraction ne bouge plus. Si le PGCD valait 1 dès le départ, la fraction était déjà irréductible — c'est un test, pas seulement une recette.
Diviser par un commun diviseur qui n'est pas le PGCD simplifie un peu, pas complètement. 48/18 divisé par 2 donne 24/9, encore simplifiable. Il faut pousser jusqu'au PGCD, ici 6, pour obtenir 8/3.
Identité de Bézout : retrouver le PGCD comme combinaison entière
Bézout affirme qu'il existe toujours des entiers relatifs u et v (positifs ou négatifs) tels que
a·u + b·v = PGCD(a, b)
Pour 1071 et 462, on remonte les restes déjà calculés. 21 = 462 − 3·147, et 147 = 1071 − 2·462, d'où 21 = 7·462 − 3·1071. Les coefficients u = −3 et v = 7 vérifient : 1071·(−3) + 462·7 = −3 213 + 3 234 = 21. C'est l'identité de Bézout*, lue sur l'algorithme d'Euclide* étendu.
Ces coefficients servent aux inverses modulaires, à un bout de cryptographie, et aux équations diophantiennes du type ax + by = c : il existe des solutions entières précisément lorsque le PGCD de a et b divise c. 12x + 18y = 6 a des solutions (PGCD = 6, et 6 divise 6). 12x + 18y = 5 n'en a aucune.
Cette page n'affiche pas u et v. Elle s'arrête au PGCD, au PPCM, et au détail a = q·b + r. Les coefficients de Bézout sont une lecture supplémentaire des mêmes restes, pas un résultat du formulaire.
Le pire des cas : Fibonacci et le théorème de Lamé
Euclide est rapide. Le nombre d'étapes croît comme le logarithme des nombres, pas comme les nombres eux-mêmes.
Le pire des cas, c'est un résultat de Lamé (1844) : il arrive lorsque a et b sont deux termes consécutifs de la suite de Fibonacci*. Chaque quotient vaut alors 1, et le reste recule le plus lentement possible. PGCD(89, 55) — F11 et F10 — enchaîne 55, 34, 21, 13, 8, 5, 3, 2, 1, 0. Neuf restes pour deux nombres à deux chiffres. Pour n'importe quel couple, le nombre de divisions ne dépasse pas cinq fois le nombre de chiffres (en base 10) du plus petit des deux.
Voilà pourquoi factoriser d'abord n'est presque jamais un bon plan machine : Euclide a fini avant qu'on ait trouvé le premier facteur. Les Fibonacci ne sont pas un piège du formulaire ; ce sont juste les couples qui font le plus de lignes dans le tableau.
PGCD(0, n) : une convention, et pourquoi zéro n'entre pas ici
Par convention, PGCD(0, n) = n pour n > 0. Zéro est multiple de tout entier, donc les diviseurs communs de 0 et n sont exactement les diviseurs de n, et le plus grand est n. PGCD(0, 0) n'a pas de définition raisonnable : tout entier divise 0.
Cette page refuse zéro, et les négatifs. Elle attend une liste de 2 à 20 entiers strictement positifs, chacun inférieur à 1 000 000. Ce n'est pas qu'Euclide casserait sur 0 — la convention ci-dessus marche — c'est que le PPCM avec un zéro n'a plus de sens utile ici. Tout multiple de 0 est 0 ; « plus petit commun multiple » devient un jeu de langage.
Trois nombres : la formule a·b / PGCD ne se généralise pas
La relation familière PGCD(a, b) × PPCM(a, b) = a × b, elle, ne survit pas telle quelle à trois arguments.
Pour 6, 10 et 15 : PGCD = 1, PPCM = 30, produit des trois = 900, et 1 × 30 = 30, qui n'a rien à voir avec 900. Autre couple, 2, 4 et 8 : PGCD = 2, PPCM = 8, produit = 64, et 2 × 8 = 16 ≠ 64. Cela dit, la formule à deux arguments reste exacte à chaque réduction de paire. C'est elle que le calculateur applique, en divisant d'abord par le PGCD avant de multiplier, pour ne pas faire exploser le produit intermédiaire.
PPCM(a, b) = a · b / PGCD(a, b) (deux arguments seulement)
On garde donc la formule pour les paires, et on n'essaie pas de la coller sur une liste. Changer l'ordre de la saisie ne change pas le résultat final — commutativité et associativité, encore.
Dénominateur commun : le PPCM avant d'additionner
Additionner 1/4 + 1/6 + 1/10, c'est d'abord se trouver un dénominateur commun. N'importe quel commun multiple ferait l'affaire (120, 60, 180…), mais le plus économique est le PPCM des dénominateurs.
PPCM(4, 6, 10) = 60. On écrit 15/60 + 10/60 + 6/60 = 31/60. Le calculateur de fractions réduit ensuite si besoin, via le PGCD du numérateur et du dénominateur — les deux outils se relaient. En résumé, le PPCM n'est pas réservé aux bus et aux engrenages : c'est aussi le plus petit dénominateur qui rend une somme lisible.
Même réflexe pour comparer deux fractions, ou pour une moyenne de durées exprimées en fractions d'heure. Toute la famille des calculateurs mathématiques s'appuie, tôt ou tard, sur ce couple PGCD / PPCM.
Lexique
- PGCD
- Plus grand commun diviseur : le plus grand entier positif qui divise chacun des nombres d'une liste. PGCD(24, 36, 60) = 12. On le calcule par l'algorithme d'Euclide, ou en prenant le minimum des exposants dans les décompositions en facteurs premiers.
- PPCM
- Plus petit commun multiple : le plus petit entier positif multiple de chacun des nombres de la liste. PPCM(24, 36, 60) = 360. Pour deux arguments, PPCM(a, b) = a·b / PGCD(a, b). Cette égalité ne se recopie pas telle quelle sur trois nombres ou plus.
- Algorithme d'Euclide
- Procédé qui remplace le plus grand des deux nombres par le reste de sa division par le plus petit, jusqu'à reste nul. Le dernier diviseur utilisé est le PGCD. Décrit dans les Éléments, livre VII. Il termine toujours, parce que les restes décroissent strictement.
- Premiers entre eux
- Deux entiers dont le seul diviseur commun positif est 1 (on dit aussi copremiers). 35 et 12 le sont, sans être premiers. Pour une liste, PGCD = 1 (« dans l'ensemble ») n'implique pas que chaque paire le soit.
- Identité de Bézout
- Il existe toujours des entiers relatifs u et v tels que a·u + b·v = PGCD(a, b). On les lit en remontant les restes d'Euclide (algorithme étendu). Une équation ax + by = c a des solutions entières précisément lorsque ce PGCD divise c.
- Suite de Fibonacci
- Suite d'entiers où chaque terme est la somme des deux précédents (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…). Deux termes consécutifs forment le pire des cas d'Euclide (théorème de Lamé, 1844) : chaque quotient vaut 1, le reste recule le plus lentement possible.