Le plus grand commun diviseur (PGCD) de deux entiers naturels a et b est le plus grand entier naturel qui divise simultanément ces deux entiers. On le note PGCD (a,b) ou pgcd (a,b) ou encore a ∧ b.
Par exemple le PGCD de 42 et 56
est 14. En effet, 42 = 14×3, 56 = 14×4, et 3 et 4 sont premiers entre eux (ils
n'ont comme diviseur entier commun que 1).
Le plus petit commun multiple (PPCM) de deux entiers non
nuls a et b est le plus petit entier strictement positif
qui soit à la fois multiple de ces deux nombres. On le note a ∨ b1 ou PPCM(a, b).
On peut calculer le PGCD et le PPCM de deux entiers grâce aux méthodes énoncées plus bas.
Il existe plusieurs méthodes. En voici quelques-unes.
Tentons de trouver le PGCD de 24 et 60.
Méthode de la décomposition en facteurs premiers
Using this method, first find the prime factorization of each number.
24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5
On trouve les facteurs premiers communs aux deux nombres.
24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5
Ces facteurs communs sont 2, 2 et 3. Le plus grand commun diviseur de 24 et 60 est le produit de ces facteurs à savoir 2 × 2 × 3 = 12.
Division par des nombres premiers
On divise d'abord tous les nombres par les plus petits nombres premiers qui puissent les diviser tous.Le plus petit nombre premier qui divise 24 ou 60 est 2.
2 | 24 60 |
12 30 |
On répète la manipulation jusqu'à ne plus pouvoir trouver de nombre premier qui divise tous les nombres situés du côté droit.
2 | 24 60 |
2 | 12 30 |
3 | 6 15 |
2 5 |
Le PGCD est 2 × 2 × 3 = 12.
Algorithme d'Euclide
Soient deux entiers naturels a et b, dont on cherche le PGCD. Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut. Une suite d'entiers (an)n est définie par récurrence de pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par a0 = a, a1 =b, puis propagée par la règle de récurrence : tant que an+1 est non nul, an+2 est défini comme le reste de la division euclidienne de an par an+1.
On commence donc par calculer
le reste de la division de a par b, qu'on note r ;
puis on remplace apar b, puis b par r, et on
réapplique le procédé depuis le début.
On obtient ainsi une suite, qui
vaut 0 à un certain rang ; le PGCD cherché est le terme précédent de la
suite.
Par exemple, pour 24 et 60, voici les étapes de l'algorithme d'Euclide :
Autre exemple, trouvons le PGCD de 40 et 64.
Parmi les méthodes permettant de trouver le PPCM se trouvent :
Trouvons le PPCM de 24 et 60.
Méthode de la décomposition en facteurs premiers
En utilisant cette méthode, on trouve d'abord la factorisation première de chaque nombre et on l'écrit sous cette forme :
24 = 23 × 3
60 = 22 × 3 × 5
Le plus petit commum multiple est le produit de chaque facteur premier ayant le plus grand exposant. Donc pour l'exemple précédent, le PPCM est 23 × 3 × 5 = 120.
Division par des nombres premiers
On divise d'abord tous les nombres par le plus petit nombre premier qui puisse les diviser tous. Dans le cas de 24 et 60, c'est 2.
2 | 24 60 |
12 30 |
On continue les étapes jusqu'à avoir tous les nombres premiers du côté gauche et en bas.
2 | 24 60 |
2 | 12 30 |
3 | 6 15 |
2 5 |
Le PPCM est 2 × 2 × 3 × 2 × 5 = 120.
Formule
Si on connaît le PGCD des entiers a et b, on peut calculer le PPCM en utilisant la formule suivante :
PPCM(a,b) = | a × b |
PGCD(a,b) |
En utilisant l'exemple ci-dessus, voici comment on trouve le PPCM de 24 et 60 :
PPCM(24,60) = | 24 × 60 | = 120 |
12 |
A l'inverse, si l'on connaît déjà le PPCM, on peut utiliser cette forume pour calculer le PGCD.