Dans cet article, nous allons vous présenter les notions de PGCD et PPCM, deux notions essentielles en arithmétique.
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 32 = 5 x 32 x 20
50 = 52 x 2 = 52 x 30 x 21
Le PGCD est donc 5 x 30 x 20 = 5
Le PPCM est 52 x 32 x 21 = 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 r1 est non nul, on fait la division euclidienne de b par r1. Si on obtient un reste r2 non nul, on effectue la division euclidienne de r1 par r2. On obtient un reste r3. 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
- 756 et 306
- 15489 et 156
- 154 et 39
- 168 et 204
- 788 et 504
Exercice 2
Calculer le pgcd des couples suivants à l’aide de la décomposition en facteurs premiers
- 360 et 144
- 3345 et 600
- 6209 et 4435
- 675 et 375
- 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 a2 – ab = 3456