PGCD et PPCM : Cours et exercices

Dans cet article, nous allons vous présenter les notions de PGCD et PPCM, deux notions essentielles en arithmétique.

Prérequis

• Les nombres premiers
• La valeur absolue

Définition

PGCD

PGCD signifie plus grand commun diviseur. La définition du PGCD est donc la suivante. Soient a et b deux entiers. Le PGCD de a et b est le plus grand nombre qui divise à la fois a et b. On le note a ∧ b ou pgcd(a,b).
Si pgcd(a,b) = 1, on dit que a et b sont premiers entre eux.

Exemple :
Prenons 12 et 18. pgcd(12,18) = 6. 6 est le plus grand diviseur commun à 12 et 18.

PPCM

PPCM signifie plus petit commun multiple. La définition du PPCM est donc la suivante. Soient a et b deux entiers. Le PPCM de a et b est le plus petit entier n > 0 tel que a | n et b | n. Il est noté a ∨ b ou ppcm(a,b)

Exemple : On prend encore 12 et 18. ppcm(12,18) = 36. Simple justification : Le premier multiple de 18 est 18. 12 ne divise pas 18. On va donc chercher le multiple suivant, 36. Comme 12 divise aussi 36, 36 est bien le PPCM entre 12 et 18.

Propriétés

On a diverses propriétés autour des PGCD :

\begin{array}{l}\forall a,b \in \mathbb{Z}, \forall  c \in \mathbb{Z}, \text{pgcd}\left(a,b\right) = \text{pgcd}\left(b,a\right)\\
\forall a,b \in \mathbb{Z}, \text{pgcd}\left(a,b\right)= \text{pgcd}\left(a-bc,b\right)\\
\forall a,b,c \in \Z, \text{pgcd}\left(ca,cb\right) = \left|c\right|\text{pgcd}(a,b)\\
\forall a,b,c \in \mathbb{Z},\text{pgcd}\left(a,b,c\right) = \text{pgcd}\left(a,pgcd \left(b,c\right)\right) = pgcd \left(\text{pgcd}\left(a,b\right),c\right)\\
\forall a,b \in \Z, \text{pgcd}(a,b) = a \Leftrightarrow  a |b\ \\
\forall a \in \Z,  \text{pgcd}(a,0) = a
\end{array}

On a des propriétés similaires autour du PPCM :

\begin{array}{l}\forall a,b\ \in\mathbb{Z}, \forall c \in\mathbb{Z},\ \text{ppcm}\left(a,b\right) =\text{ppcm}\left(b,a\right)\\
\forall a,b,c\ \in \Z,\text{ppcm}\left(ca,cb\right) = \left|c\right|\text{ppcm}\left(a,b\right)\\
\forall a,b,c\ \in\mathbb{Z},\text{ppcm}\left(a,b,c\right)=\text{ppcm}\left(a,\text{ppcm}\left(b,c\right)\right) = \text{ppcm}\left(\text{ppcm}\left(a,b\right),c\right)\\
\forall a,b\in\mathbb{Z},\text{ppcm}(a,b)=a\ \Leftrightarrow\ b|a\end{array}

Et d’autres qui mêlent PGCD et PPCM

\begin{array}{l}\forall a,b\in \mathbb{Z}, \text{pgcd}\left(a,b\right)\ \times \text{ppcm}\left(a,b\right) = \left|ab\right| \text{(celle-ci est à retenir)}\\
\forall a,b,c \in\mathbb{Z}, \text{pgcd}\left(a,\text{ppcm}\left(b,c\right)\right) =\text{ppcm}(\text{pgcd}\left(a,b),\text{pgcd}\left(a,c\right)\right)\\
\forall a,b,c \in \mathbb{Z},\ \text{ppcm}\left(a,\text{pgcd}\left(a,b\right)\right) =\text{pgcd}\left(\text{ppcm}\left(a,b\right),\text{ppcm}\left(a,c\right)\right)\\
\forall a,b,c \in \Z,\\ \text{pgcd}(\text{ppcm}(a,b),\text{ppcm}(a,c),\text{ppcm}(b,c))=\text{ppcm}(\text{pgcd}(a,b),\text{pgcd}(a,c),\text{pgcd}(b,c))
\end{array}

Méthodes de calcul

De manière générale, pour calculer le PPCM, on calcule d’abord le PGCD et on applique la formule vue au-dessus :

 \text{ppcm}\left(a,b\right)\ =\ \frac{\left|ab\right|}{\text{pgcd}\left(a,b\right)}

Par les diviseurs

Cette méthode est la plus basique mais fonctionne très bien. On fait la liste des diviseurs de chaque nombre et on prend le plus grand en commun dans la liste.

Exemples :
1) Calculons le PGCD de 50 et 45.
Liste des diviseurs de 50 : 1, 2, 5, 10, 25, 50
Liste des diviseurs de 45 : 1, 3, 5, 9, 15, 45
Le PGCD est donc 5 puisqu’il s’agit du plus grand diviseurs que ces deux nombres ont en commun.
2) Calculons le PGCD de 210 et 330
Liste des diviseurs de 210 : 1, 2, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 105, 210
Liste des diviseurs de 330 : 1, 10, 11, 30, 33, 330
Le PGCD est donc 30.

Par le théorème des nombres premiers

On décompose en produits de nombres premiers (voir article sur les nombres premiers) les nombres dont on veut calculer PGCD. On prend ensuite la plus petite puissance commune à chacun pour calculer le PGCD. Si on veut calculer le PPCM, il faut alors prendre la plus grande puissance commune à chacun.

\begin{array}{l}\text{Soit } a\in\mathbb{N}, a =\displaystyle \prod_{i=1}^np_i^{\alpha_i}\\\
\text{Soit } b \in\mathbb{N}, b =\displaystyle\prod_{i=1}^np_i^{\beta_i}\\ 
\text{(avec potentiellement }\alpha_i = 0 \text{ ou } \beta_{i}=0)\end{array}

Alors,

\begin{array}{l}
\text{pgcd}\left(a,b\right) =\displaystyle \prod_{i=1}^np_i^{\min\left(\alpha_i,\beta_i\right)}\\ 
\text{ppcm}\left(a,b\right) =\displaystyle  \prod_{i=1}^np_i^{\max\left(\alpha_i,\beta_i\right)}
\end{array}

Exemple :
Calculons le PGCD et le PPCM de 45 et 50
45 = 5 x 3² = 5 x 3² x 2⁰
50 = 5² x 2 = 5² x 3⁰ x 2¹
Le PGCD est donc 5 x 3⁰ x 2⁰ = 5
Le PPCM est 5² x 3² x 2¹ = 450

Par l’algorithme d’Euclide

Division euclidienne

Soient a et b deux entiers, b > 0. La division euclidienne de a par b consiste à trouver les uniques q et r tels que :

\begin{array}{l}a\ =\ bq\ +\ r\\
0\ \le\ r\ <\ b\end{array}

Application au PGCD

On utilise la formule suivante : pgcd(a,b) = pgcd(a-bq,b) = pgcd(b,r)
Voici l’algorithme d’Euclide :
On fait la division euclidienne de a par b. Si le reste r₁ est non nul, on fait la division euclidienne de b par r₁. Si on obtient un reste r₂ non nul, on effectue la division euclidienne de r₁ par r₂. On obtient un reste r₃. Et on continue jusqu’à obtenir un reste nul.
Le PGCD est le dernier reste non nul.

Exemple 1
Calculer par division euclidienne le PGCD de 50 et 45.
50 = 45 x 1 + 5
45 = 5 x 9 + 0
Le dernier reste non nul est 5. C’est donc le PGCD entre 45 et 50.

Exemple 2
Calculer le PGCD entre 210 et 330 par division euclidienne.
330 = 210 x 1 + 120
210 = 120 x 1 + 90
120 = 90 x 1 + 30
90 = 30 x 3 + 0
Le PGCD de 210 et 330 est donc 30.

Exemple 3
Montrer que n et n + 1 sont premiers entre eux, c’est à dire que pgcd(n,n+1) = 1
Avec la division euclidienne c’est tout simple :
n + 1 = n x 1 +1
n = 1 x n + 0
Le dernier reste non nul est donc 1. n et n+1 sont donc premiers entre eux

Calculateur de PGCD et PPCM

Calculateur de PGCD

Besoin de vérifier vos calculs ? Utilisez notre calculateur pour trouver le bon résultat !

Calculateur de PPCM

Exercices

Exercice 1
Calculer le pgcd des couples suivants à l’aide de l’algorithme d’Euclide

1. 756 et 306
2. 15489 et 156
3. 154 et 39
4. 168 et 204
5. 788 et 504

Exercice 2
Calculer le pgcd des couples suivants à l’aide de la décomposition en facteurs premiers

1. 360 et 144
2. 3345 et 600
3. 6209 et 4435
4. 675 et 375
5. 682 et 352

Exercice 3
Soient m et n tels que m +n soit un nombre premier. Montrer que m et n sont premiers entre eux.

Exercice 4
Déterminer le PGCD entre 9n +6 et 2n +1 à l’aide de 2 méthodes de votre choix

Exercice 5
Résoudre les équation suivantes :

\left\{\begin{matrix}xy\ &=&3456\\
pgcd\left(x,y\right)&=&12\end{matrix}\right. 

\left\{\begin{matrix}xy\ &=&864\\
pgcd\left(x,y\right)&=&12\end{matrix}\right.

Exercice 6
Trouver tous les entiers positifs a et b tels que pgcd(a,b) = 5 et ppcm(a,b) = 306

Exercice 7
Trouver tous les entiers positifs a et b tels que pgcd(a,b) = 7 et a² – ab = 3456