PGCD et PPCM : Cours et exercices

Le PGCD et le PPCM : Définitions, propriétés, méthodes et exemples sont au rendez-vous pour aider à bien comprendre la notion

parValentin Strach

4 février 2022

14,3K vues

4 minutes de lecture

1 commentaire

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

Table des matières

Prérequis

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

Retrouvez notre article sur la division euclidienne