A.

PGCD – PPCM
1. Définitions
Soient a et b deux entiers relatifs différents de 0. L’ensemble des diviseurs à a et
b admet un plus grand élément « d » appelé : PGCD (Plus Grand Commun
Diviseur) de a et b noté PGCD(a, b) ou a  b .
Soient a et b deux entiers relatifs différents de 0. L’ensemble des multiples
strictement supérieurs à a et b admet un plus petit élément « m » appelé : PPCM
(Plus Petit Commun Multiple) de a et b noté PPCM(a, b) ou a  b.

2. Méthode de calcul du PGCD

Pour déterminer le PGCD de deux nombres a et b, on peut faire recours à deux
méthodes à savoir, la méthode de décomposition en facteurs premiers et la
méthode de l’algorithme d’Euclide.

a. Décomposition en facteurs premiers

Utilisons la méthode de décomposition pour déterminer le PGCD(945, 882).

945 3 882 2
315 3 441 3
105 3 147 3
35 5 49 7
7 7 7 7
1 1 1

On a donc : 945 = 3² × 3 × 5 × 7 882 = 2 × 3² × 7²

Pour déterminer le pgcd, il suffit de prendre les facteurs en commun, donc :
PGCD(945, 882) = 3² × 7 = 63
 b. L’algorithme d’Euclide
Théorème1 : Soit deux entiers a et b, pour connaître le PGCD(a, b), on effectue
les divisions euclidiennes successives suivantes :
 a = b q₀ + r₀
 b = r₀ q₁ + r₁ division de b par r₀
 r₀ = r₁ q₂ + r₂ division de r₀ par r₁
 r₁ = r₂ q₃ + r₃ division de r₁ par r₂ …

Le dernier reste non nul correspond au PGCD(a, b)

Exemples :
• Déterminons le PGCD(945,882) On effectue les divisions suivantes :
945 = 882 × 1 + 63
882 = 63 × 14 + 0
Donc PGCD(945, 882) = 63
• Déterminons le PGCD(935, 561)
On effectue les divisions suivantes :
935 = 561 × 1 + 374
561 = 374 × 1 + 187
374 = 187 × 2 + 0
Donc PGCD(935, 561) = 187
Remarque : Le PGCD de deux nombres est le dernier reste non nul que l'on
obtient par la méthode de divisions successives. On s’aperçoit sur ces deux
exemples de l’efficacité de cet algorithme. Il sera donc à préférer à la méthode
par décomposition en facteurs premiers.

3. Propriété du PGCD

• PGCD (a, b) = PGCD (b, a)

• Si on multiplie (ou si l'on divise) plusieurs nombres par un même nombre,

le PGCD est multiplié (ou divisé) par ce nombre.
Exemple : PGCD (300, 216) = 12 alors PGCD (1800, 1296) = 6 x PGCD (300,
216) = 72
• PGCD (ka, kb) = [Link] (a, b)

• Les diviseurs communs à plusieurs nombres divisent leur PGCD.

• Si c | a et c | b alors c | PGCD (a, b).

• Pour qu'un diviseur commun à plusieurs nombres soit le PGCD de ces

nombres, il faut et il suffit que leurs quotients par le diviseur commun
considéré soient premiers entre eux.

• Soient a, b de IN* et d de IN* tel que il existe a' et b' de IN* a = da', b =
db' alors d = PGCD (a, b) si et seulement si PGCD (a',b') = 1.

• L'ensemble des diviseurs communs à plusieurs entiers est le même quand

on remplace deux de ces nombres par leur PGCD.

• Pour déterminer le PGCD de plusieurs entiers on peut remplacer deux

entiers par leur PGCD.

• Si c divise ab et PGCD (a ; c) = 1 alors c divise b. (Théorème de Gauss)

• Il résulte de la propriété multiplicative du PGCD et du théorème de Gauss

que si a et b sont premiers entre eux, alors an et bp (n et p dans IN) le sont
aussi.

• Si PGCD (a ; b) =1 et PGCD ( a ; c) = 1 alors PGCD ( a ; bc ) =1

• Si PGCD (a ; b) = d alors il existe des entiers u et v tels que d = au + bv

• PGCD (a, b) =1 si et seulement si, il existe u, v Є Z tels que au + bv = 1.

(Identité de Bézout).

• Deux entiers a et b sont premiers entre eux si, et seulement si,

PGCD (a, b) = 1

Exemples :
 • PGCD(9, 16) ; 9 et 16 sont premiers entre eux. (9, 16) = 1 car 9 = 32 et 16
= 42.
• Déterminons le PGCD (1 600, 229) par l’algorithme d’Euclide :
1 600 = 229 × 6 + 226
229 = 226 × 1 + 3
226 = 3 × 75 + 1
3=1×3+0
Donc PGCD (1 600, 229) = 1,
Les nombres 1 600 et 229 sont donc premiers entre eux.

4. Méthode de calcul du PPCM

Soient a et b deux entiers relatifs, pour trouver le PPCM(a, b) on procède
comme suit :
- Trouver les multiples communs à a et b,
- Parmi ces multiples, il en existe un, inférieur à tous les autres ; c’est le
PPCM(a, b).
Pour cela, on peut utiliser les deux méthodes qui suivent.

a. Méthode 1 : lister tous les multiples

Cette méthode consiste à lister tous les multiples des nombres et trouver le plus
petit multiple commun.
Exemple : Calculer le PPCM(10, 12)
- 10 a pour multiples 0,10,20,30,40,50,60,70,etc.
- 12 a pour multiples 0,12,24,36,48,60,72,etc.
Le plus petit commun multiple est 60.

b. Méthode 2 : décomposition en facteurs premiers

Cette méthode consiste à décomposer chaque nombre en facteurs
premiers. Le PPCM est la multiplication des facteurs communs par les
facteurs non communs.
Exemple : 10 = 2 × 5 et 12 = 2 × 2 × 3
Le facteur commun est : 2 et les facteurs non communs : 2,3,5
Donc PPCM(10, 12) = 2 × 2 × 3 × 5 = 60

5. Propriétés du PPCM

• Si a et b sont deux entiers relatifs, PPCM(a, b) = PPCM(b, a)

• Si a est un multiple de b, alors PPCM(a ; b) =a.

Exemple : PPCM(187;17) = 187 Car 187 est multiple de 17.
• Si PPCM ( a; b ) = m alors il existe u et v tels que m = au = bv.

• PPCM (ka ; kb) = [Link] (a ; b)

• PGCD (a ; b) = 1 si et seulement si PPCM ( a ; b ) = ab.

• Pour déterminer le PPCM de plusieurs entiers on peut remplacer deux

entiers par leur PPCM.

6. Relation entre le PGCD et le PPCM

Soient deux entiers positifs a et b, M = PPCM(a, b) et d = PGCD(a, b).Alors
on a la relation : ab = Md.
Entre le PGCD(a, b) et PPCM(a, b), on a la relation suivante :
a×b
PPCM(a, b) ¿ PGCD (a , b)

Exemples:

• PGCD(28, 77) = 7 et PPCM

• PGCD(18, 42) = 6 et PPCM

Dans ces deux exemples, le PGCD est immédiat car les nombres ne sont pas
trop grands. Lorsque cela n’est plus aussi immédiat, deux méthodes sont
possibles : l’algorithme d’Euclide ou la décomposition en nombres premiers.

7. PGCD et PPCM appliqué aux polynômes

a. PGCD et PPCM de deux polynômes
 PGCD
Pour déterminer le PGCD de deux polynômes on applique l'algorithme
d'Euclide, utilisant les divisions euclidiennes successives des polynômes et les
résultats suivants : dans la division euclidienne de a par b, si a = bq + r,
alors PGCD(a, b) = PGCD(b, r) = PGCD(b, λr) où λ est un scalaire non nul.
Exemple :
Trouver le PGCD dans K[X] (K étant R ou C) des
polynômes A et B suivants :

A(X) = X⁵ − 2X⁴ + X³ − X² + 2X−1

B(X)=X³ − X² + 2X – 2

Solution :

On détermine le PGCD des polynômes A et B par le théorème moteur de

l'algorithme d'Euclide, utilisant les divisions euclidiennes des polynômes.

On fait la division de A par B :

On a obtenu A(X) = (X² − X −2) (B(X) + X² + 4X −5).

Donc le PGCD des polynômes A(X) et B(X) est égal au PGCD des
polynômes B(X)

et X² + 4X −5.

On fait la division de B(X) par X² + 4X −5:

On a obtenu B(X)=(X−5)(X² + 4X −5) + 27X − 27.

Comme 27X – 27 = 27(X−1) = 27(X−1), il est préférable de faire ensuite la

division euclidienne

de X² + 4X −5par X−1, puisque PGCD(P,Q) = PGCD(P, λQ) si λ est un scalaire

non nul.

Le PGCD des polynômes B(X) et X² + 4X −5 est égal au PGCD des polynômes

X² + 4X −5 et X−1.

On fait la division de X² + 4X −5 par X−1.

On remarque que le polynôme X² + 4X − 5 est un multiple du polynôme X − 1.

Donc le polynôme X−1 est le PGCD de X² + 4X − 5 et X − 1,

donc aussi celui de B(X) et X² + 4X − 5, donc aussi celui de A(X) et B(X).

PGCD(A(X), B(X)) = X – 1.

 PPCM
Pour déterminer le PGCD de deux polynômes on applique l'algorithme
d'Euclide, utilisant les divisions euclidiennes successives des polynômes et les
résultats suivants : dans la division euclidienne de F par G, si F=GQ+R,
alors PGCD(F, G) = PGCD(G, R) = PGCD(G, λR) où λ est un scalaire non nul.

Exemple :
Soit A et B deux polynômes.
A(X)=X⁵ − 2X⁴ + X³ − X² + 2X − 1
B(X)=X³ − X² + 2X − 2
Quel est le PPCM de A et B ?

Solution :
Pour calculer le PPCM de A et B, on se sert de la formule (les polynômes A et B
étant unitaires) : AB = PGCD(A, B) × PPCM(A, B).
On peut calculer explicitement le produit AB, puis diviser le résultat par le
PGCD de A et B, mais il est préférable de se servir de la question 2. :
A = DA′ et B = DB′ où A′(X) = X⁴ − X³ − X + 1 et B′(X) = X² + 2.
Comme AB = DA′ DB′ = D × PPCM(A, B),
on en déduit que PPCM(A, B) = DA′ B′, c'est à dire :
PPCM(A(X), B(X)) = (X − 1) (X⁴ − X³ − X + 1) (X² + 2)
= X⁷ − 2X⁶ + 3X⁵ − 5X⁴ + 4X³ − 3X² + 4X − 2
On pouvait remarquer que : PPCM(A, B) = AB′ = A′B, puisque A = DA′ et
B = DB′, et l'on pouvait alors calculer un de ces deux produits.

b. PGCD de trois polynômes

Par définition, le PGCD, noté D, des polynômes P1, P2,…, Pn non tous nuls
est le seul polynôme unitaire satisfaisant aux conditions a. et b. suivantes :
 a. Le polynôme D divise tous les polynômes Pi,
b. Tout polynôme divisant chacun des Pi divise D.
Le PGCD de plusieurs polynômes divise le PGCD de deux d'entre eux.
Exemple :
On considère dans K[X] (K étant R ou C), les trois
polynômes A, B et C suivants :
A(X) = X³ + 6X² + 11X + 6
B(X) = X³ + 4X² + X − 6
C(X) = X³ + X² − X − 1
Calculer PGCD(A, B), PGCD(A, C), PGCD(B, C), PGCD(A, B, C).
Solution :
Pour déterminer PGCD(A, B), PGCD(A, C), PGCD(B, C), on devrait se servir
de l'algorithme d'Euclide.
Pour déterminer PGCD(A,B,C), on devrait revenir à la définition du PGCD :

1. On détermine le PGCD des polynômes A et B par l'algorithme d'Euclide,

utilisant les divisions euclidiennes des polynômes.

Ce PGCD est le dernier reste non nul à une constante multiplicative près, car le
PGCD est un polynôme unitaire (si le reste est unitaire, c'est le PGCD, sinon on
divise le dernier reste non nul par le coefficient du terme dominant pour obtenir
le PGCD).

A(X) = X³ + 6X² + 11X + 6

B(X) = X³ + 4X² + X − 6

Comme les polynômes A et B ont le même degré, on a immédiatement :

A(X) = B(X) + 2X² + 10X + 12

On divise B(X) par 2X² + 10X + 12
Donc le dernier reste non nul est le polynôme 2X2+10X+12. Ce polynôme
n'étant pas unitaire, on le divise par le coefficient du terme dominant.
PGCD(A(X), B(X)) = X² + 5X + 6

2. On détermine de même le PGCD de A et C

A(X) = X³ + 6X² + 11X + 6

C(X) = X³ + X² − X − 1

Comme les polynômes A et C ont le même degré, on a immédiatement :

A(X) = C(X) + 5X² + 12X + 7

Donc on divise C(X) par 5X + 12X + 7

Au lieu de continuer les divisions pour trouver le dernier reste non nul, vu la
24 24
forme du diviseur suivant qui est le polynôme 25 X + 25 , il vaut mieux utiliser le
fait que le PGCD des polynômes A(X) et C(X) est égal au PGCD des
polynômes C(X) et 5X² + 12X + 7 et que le PGCD des polynômes C(X) et
5X² + 12X + 7 est égal au PGCD des polynômes
24 24
5X² + 12X + 7 et 25 X + 25 .

24 24 24
Or 25 X + 25 . = 25 (X+1)

Donc le PGCD des polynômes C(X) et 5X² + 12X + 7 est égal au PGCD des
polynômes 5X² + 12X + 7 et X + 1.

Comme le polynôme X + 1 divise 5X² + 12X + 7, il est le PGCD des polynômes

5X² + 12X + 7 et X + 1, donc celui de C(X) et 5X² + 12X + 7,
donc celui de A(X) et C(X).
PGCD(A(X), C(X)) = X + 1

3. On détermine le PGCD de B et C.

B(X) = X³ + 4X² + X − 6
C(X) = X³ + X² − X − 1

Comme les polynômes B et C ont le même degré, on a immédiatement :

B(X) = C(X) + 3X² + 2X − 5

On divise C(X) par 3X² + 2X − 5.
Ici aussi, vu la forme du reste, il vaut mieux utiliser la méthode qui consiste à
dire que le PGCD des polynômes B(X) et C(X) est égal au PGCD des
polynômes C(X).
et 3X² + 2X − 5, qui lui est égal au PGCD des polynômes 3X² + 2X – 5 et
49X − 49.
Or 49X – 49 = 49 (X−1)
Donc le PGCD des polynômes 3X² + 2X − 5 et 49X − 49 est égal au PGCD des
polynômes 3X² + 2X − 5 et X − 1.
On divise 3X² + 2X − 5 par X − 1:

Le PGCD des polynômes 3X² + 2X − 5 et X − 1 est donc X − 1, et comme

précédemment on en déduit que :
PGCD(B(X), C(X)) = X − 1
4. Il reste à calculer le PGCD de A, B et C.
L'algorithme d'Euclide ne concerne que la recherche du PGCD de deux
polynômes, donc on utilise ici la définition du PGCD de plusieurs polynômes.

Par définition, le PGCD, noté D, des polynômes P1,P2,…,Pn non tous nuls est le
seul polynôme unitaire satisfaisant aux conditions a. et b. suivantes :
a. Le polynôme D divise tous les polynômes Pi,
b. Tout polynôme divisant chacun des Pi divise D.
On déduit de la condition a. que le PGCD de A, B et C divise A et C.
Ceci entraîne d'après la condition b. que le PGCD de A, B et C divise le PGCD
de A et C.
De même le PGCD de A, B et C divise B et C donc il divise le PGCD de B et C.
Or PGCD(A(X), C(X)) = X + 1 et PGCD(B(X), C(X)) = X − 1.
Donc le PGCD de A(X), B(X) et C(X) divise les deux polynômes X + 1 et X −1.
Il est immédiat que les polynômes X+1 et X−1 sont premiers entre eux
(par exemple ces deux polynômes vérifient l'identité de Bézout 12(X + 1) −
12(X − 1) = 1. D'où
PGCD(A(X), B(X),C(X)) = 1

Remarque :

Les polynômes A, B et C ne sont pas premiers deux à deux, mais ils n'ont pas de
diviseur commun : ils sont premiers dans leur ensemble.