Comment calculer le PGCD et le PPCM de deux nombres ?

Définition du PGCD et du PPCM

Le PGCD de deux nombres est leur plus grand diviseur commun. Le PPCM est leur plus petit multiple commun strictement positif.

Exemple avec 12 et 18 :

• Diviseurs communs : 1, 2, 3 et 6. Donc PGCD(12 ; 18) = 6.
• Leurs premiers multiples communs positifs sont 36, 72, 108… Donc PPCM(12 ; 18) = 36.

Calculer le PGCD avec l’algorithme d’Euclide

L’algorithme d’Euclide consiste à effectuer des divisions euclidiennes successives. Le PGCD est le dernier reste non nul.

Pour calculer le PGCD de 84 et 30 :

84 = 30 × 2 + 24
30 = 24 × 1 + 6
24 = 6 × 4 + 0

Le dernier reste non nul est 6. Ainsi, PGCD(84 ; 30) = 6.

Pourquoi cette méthode fonctionne-t-elle ?

Si a = b × q + r, alors PGCD(a ; b) = PGCD(b ; r). On remplace donc progressivement les deux nombres par le diviseur et le reste jusqu’à obtenir un reste nul.

Calculer le PGCD avec les facteurs premiers

On décompose chaque nombre en facteurs premiers, puis on conserve uniquement les facteurs communs avec leur plus petit exposant.

Pour 84 et 30 :

84 = 2² × 3 × 7
30 = 2 × 3 × 5

Les facteurs communs sont 2 et 3. On retient les plus petits exposants :

PGCD(84 ; 30) = 2 × 3 = 6.

Calculer le PPCM avec les facteurs premiers

Pour calculer le PPCM, on conserve tous les facteurs premiers présents dans les deux décompositions, en prenant à chaque fois le plus grand exposant.

Avec 84 et 30 :

PPCM(84 ; 30) = 2² × 3 × 5 × 7

Donc :

PPCM(84 ; 30) = 420.

Calculer le PPCM à partir du PGCD

Pour deux entiers positifs a et b, on utilise la relation :

PGCD(a ; b) × PPCM(a ; b) = a × b

Donc :

PPCM(a ; b) = (a × b) ÷ PGCD(a ; b)

Pour 84 et 30, comme leur PGCD vaut 6 :

PPCM(84 ; 30) = (84 × 30) ÷ 6 = 2520 ÷ 6 = 420

Quelle méthode choisir ?

• Pour de petits nombres, vous pouvez lister les diviseurs ou les multiples.
• Pour calculer rapidement un PGCD, privilégiez l’algorithme d’Euclide.
• Pour calculer simultanément le PGCD et le PPCM, utilisez la décomposition en facteurs premiers.
• Après avoir trouvé le PGCD, calculez le PPCM avec la formule PPCM(a ; b) = (a × b) ÷ PGCD(a ; b).