PGCD et PPCM : des calculs alternatifs et rapides

Pour trouver le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM), il n’est pas toujours nécessaire de décomposer tous les nombres en facteurs premiers. Les divisions successives d’Euclide donnent rapidement le PGCD ; le PPCM s’en déduit aussitôt. Les mêmes outils fonctionnent avec trois nombres ou davantage. Nous considérons ici des entiers positifs.

Que cherche-t-on ?

Le PGCD est le plus grand entier positif qui divise tous les nombres donnés. Le PPCM est le plus petit entier positif qui est un multiple de chacun d’eux. Par exemple, si deux événements se répètent toutes les 24 et 36 minutes, le premier instant positif où ils coïncident à nouveau est leur PPCM. Le PGCD indique plutôt la plus grande unité permettant de découper les deux durées en parts entières sans reste.

Un PGCD rapide : divisions successives

Calculons PGCD(84,132). Divisons le plus grand nombre par le plus petit, puis remplaçons la paire par le diviseur et le reste, jusqu’à obtenir un reste nul :

132 = 84 × 1 + 48
84 = 48 × 1 + 36
48 = 36 × 1 + 12
36 = 12 × 3 + 0

Le dernier reste non nul est 12 : PGCD(84,132) = 12. En effet, les diviseurs communs de deux nombres sont exactement ceux du diviseur et du reste : PGCD(A,B) = PGCD(B,A mod B).

Trois formules à retenir

Pour les entiers positifs A, B et C :

PPCM(A,B) = A × B / PGCD(A,B)
PGCD(A,B,C) = PGCD(C,PGCD(A,B))
PPCM(A,B,C) = PPCM(C,PPCM(A,B))

On travaille deux nombres à la fois ; leur ordre ne change pas le résultat.

Du PGCD au PPCM sans nouvelle décomposition

Avec la première formule, PPCM(84,132) = 84 × 132 / 12 = 84 × 11 = 924. Diviser avant de multiplier permet de garder des résultats intermédiaires plus petits. Vérification : 924 / 84 = 11 et 924 / 132 = 7.

Pourquoi cette formule est-elle juste ? Dans une décomposition en facteurs premiers, le PGCD prend le plus petit exposant de chaque facteur et le PPCM prend le plus grand. La somme du minimum et du maximum est celle des deux exposants initiaux ; donc PGCD(A,B) × PPCM(A,B) = A × B.

Un exemple complet avec trois nombres

Prenons 24, 36 et 50. Pour le PGCD, procédons par paires : PGCD(24,36) = 12, puis PGCD(50,12) = 2. Ainsi, PGCD(24,36,50) = 2.

Pour le PPCM, calculons d’abord PPCM(24,36) = 24 × 36 / 12 = 72. Ensuite, PGCD(72,50) = 2 et PPCM(50,72) = 50 × 72 / 2 = 1800. Donc PPCM(24,36,50) = 1800 : en effet, 1800 / 24 = 75, 1800 / 36 = 50 et 1800 / 50 = 36.

Raccourcis utiles et erreur à éviter

• Si un nombre est un multiple de l’autre, le PGCD est le plus petit et le PPCM le plus grand : PGCD(18,72) = 18 et PPCM(18,72) = 72.
• Si le PGCD vaut 1, les nombres sont premiers entre eux et leur PPCM est leur produit : PPCM(35,64) = 35 × 64 = 2240.
• La formule pour deux nombres ne devient pas A × B × C / PGCD(A,B,C) pour trois nombres. Dans notre exemple, cela donnerait 21600 au lieu de 1800. Il faut appliquer la formule par paires.

À vous de jouer

Trouvez le PGCD et le PPCM de 18, 30 et 42 en utilisant seulement des paires successives.

La stratégie reste la même : trouver rapidement le PGCD grâce aux restes, utiliser le produit divisé par le PGCD, puis recommencer par paires pour trois nombres ou davantage.