Le plus grand commun diviseur et le plus petit commun multiple

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.

Comment trouver le plus grand commun diviseur

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.

224 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.

224 60
212 30
36  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.


Comment trouver le plus petit commun multiple

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.

224 60
 12 30

On continue les étapes jusqu'à avoir tous les nombres premiers du côté gauche et en bas.

224 60
212 30
36  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.