PGCD, PPCM et décomposition en facteurs premiers
- Auteur :
- Vincent Everaert
PGCD : le plus grand commun diviseur
Le PGCD de deux entiers est leur Plus Grand Commun Diviseur.
Lorsque le problème à résoudre ne nécessite que la connaissance du PGCD (et non de tous les diviseurs communs), il est plus efficace de déterminer celui-ci à partir de la décomposition des entiers en facteurs premiers.
Par exemple :
120 = 23 x 3 x 5 et 3920 = 24 x 5 x 72
Ces décompositions ont en commun : 23 et 5
Donc le PGCD de 120 et 3920 est 23 x 5, soit 40.
Que l'on peut noter : PGCD(120;3920) = 40.
On a alors : 120 = 3 x 40 et 3920 = 98 x 40
Remarque :
Une autre méthode, l'algorithme d'Euclide, est encore plus efficace... Si vous êtes curieux, étudiez-là !
PPCM : le plus petit commun multiple
Le PPCM de deux entiers est leur Plus Petit Commun Multiple.
Certains problèmes nécessitent la connaissance du plus petit multiple commun à deux entiers (attention à ne pas confondre multiple et diviseur !).
Pour cela, les décompositions en facteurs premiers sont bien utiles également.
Par exemple :
120 = 23 x 3 x 5 et 3920 = 24 x 5 x 72
Pour être un multiple de 120 et de 3920, il faut donc avoir pour facteurs : 24, 3, 5 et 72.
24 x 3 x 5 x 72 = 11760
Donc le PPCM de 120 et 3920 est 11760.
Que l'on peut noter PPCM(120;11760) = 11760.
On a alors : 120 x 98 = 11760 et 3920 x 3 = 11760