Maths
Calculer un PGCD et un PPCM
Un PGCD ? Un PPCM ?
Le calcul d’un PGCD (plus grand diviseur commun) ou d’un PPCM (plus petit multiple commun) de deux nombres peut être utile pour :
- simplifier des fractions,
- réduire deux fractions au même dénominateur ou bien
- résoudre des problèmes de « partage équitable ».
Cette fiche explique comment faire.
Calculer un PGCD
Algorithme des soustractions successives
La méthode est la suivante pour calculer le PGCD de deux nombres :
- on calcule la différence entre le plus grand et le plus petit nombre,
- puis on calcule la différence entre la différence trouvée précédemment et le plus petit nombre précédent,
- et ainsi de suite… jusqu’à ce qu’on trouve deux fois le même nombre. Le PGCD est alors ce nombre.
Le mieux est de voir des exemples :
Enoncé
Calculer le PGCD de 108 et de 378.
Réponse
On applique l’algorithme des soustractions successives (les soustractions sont écrites en vert) :
PGCD(378 ; 108) 378 – 108 = 270
= PGCD(270 ; 108) 270 – 108 = 162
= PGCD(162 ; 108) 162 – 108 = 54
= PGCD(108 ; 54) 108 – 54 = 54
= PGCD(54 ; 54) 54 – 54 = 0
= 54
Le PGCD de 108 et de 378 est donc 54.
Enoncé
Calculer PGCD(76 ; 21)
Réponse
On applique l’algorithme des soustractions successives :
PGCD(76 ; 21) 76 – 21 = 55
= PGCD(55 ; 21) 55 – 21 = 34
= PGCD(34 ; 21) 34 – 21 = 13
= PGCD(21 ; 13) 21 – 13 = 8
= PGCD(13 ; 8) 13 – 8 = 5
= PGCD(8 ; 5) 8 – 5 = 3
= PGCD(5 ; 3) 5 – 3 = 2
= PGCD(3 ; 2) 3 – 2 = 1
= PGCD(2 ; 1) 2 – 1 = 1
= PGCD(1 ; 1) 1 – 1 = 0
= 1
Le PGCD de 76 et de 21 est donc 1.
Dans ce cas précis, on dit que 76 et 21 sont « premiers entre eux » : ils n’ont pas de diviseur commun autre que 1.