Terminale C · Leçon 19
Plus petit commun multiple et plus grand commun diviseur de deux entiers relatifs
Ce que dit le programme officiel (6 points)
- Multiple d’un entier relatif
- Ensemble des multiples d’un entiers relatif 𝑛 : 𝑛ℤ
- PPCM et PGCD
- Algorithme d’Euclide
- Théorème de Bézout
- Théorème de Gauss.
Source : Programme éducatif Terminale C, DPFC, version CND 0923
PGCD, PPCM et algorithme d'Euclide
Lorsqu'on veut simplifier une fraction ou savoir si deux entiers partagent un facteur commun, on cherche leur plus grand commun diviseur. L'algorithme d'Euclide est la méthode efficace pour le calculer, quel que soit l'ordre de grandeur des entiers.
Pour \(a, b \in \mathbb{Z}\) non tous nuls, le plus grand commun diviseur \(\text{pgcd}(a, b)\) est le plus grand entier naturel qui divise à la fois \(a\) et \(b\). Le plus petit commun multiple \(\text{ppcm}(a, b)\) est le plus petit entier naturel non nul qui est divisible à la fois par \(a\) et par \(b\).
On dit que \(a\) et \(b\) sont premiers entre eux (ou copremiers) si \(\text{pgcd}(a,b) = 1\). C'est la condition clé pour appliquer le théorème de Gauss et Bézout.
Si \(d = \text{pgcd}(a, b)\), alors \(a/d\) et \(b/d\) sont premiers entre eux. Par ailleurs, \(\text{pgcd}(ka, kb) = k \cdot \text{pgcd}(a, b)\) pour tout entier \(k > 0\).
Si \(a = bq + r\) est la division euclidienne de \(a\) par \(b\), alors :
\[\text{pgcd}(a, b) = \text{pgcd}(b, r).\]En répétant le procédé (on remplace \((a, b)\) par \((b, r)\) à chaque étape), la suite des restes est strictement décroissante et positive, donc elle atteint nécessairement \(0\). Le dernier reste non nul est le PGCD.
On présente les divisions successives en colonnes. À chaque ligne on écrit \(a_k = b_k q_k + r_k\) avec \(0 \le r_k < b_k\), puis on passe à \((a_{k+1}, b_{k+1}) = (b_k, r_k)\). On s'arrête quand \(r_k = 0\).
Calcul de \(\text{pgcd}(252, 198)\) :
\[ \begin{aligned} 252 &= 198 \times 1 + 54 \\ 198 &= 54 \times 3 + 36 \\ 54 &= 36 \times 1 + 18 \\ 36 &= 18 \times 2 + 0 \quad \leftarrow \text{reste nul} \end{aligned} \]Dernier reste non nul : \(\mathbf{18}\). Donc \(\text{pgcd}(252, 198) = 18\). Et \(\text{ppcm}(252, 198) = \dfrac{252 \times 198}{18} = 2772\).
Rapide. \(\text{pgcd}(48, 18)\) : \(48 = 18 \times 2 + 12\) ; \(18 = 12 \times 1 + 6\) ; \(12 = 6 \times 2 + 0\). Donc \(\text{pgcd}(48,18) = 6\).
Intermédiaire. \(\text{pgcd}(1071, 462)\) : \(1071 = 462 \times 2 + 147\) ; \(462 = 147 \times 3 + 21\) ; \(147 = 21 \times 7 + 0\). Donc \(\text{pgcd}(1071, 462) = 21\).
Astuce de vérification. On vérifie que le PGCD trouvé divise bien les deux nombres. Ici : \(252 / 18 = 14\) et \(198 / 18 = 11\). De plus, \(\text{pgcd}(14, 11) = 1\) : les quotients sont bien premiers entre eux.
Figure interactive — Algorithme d'Euclide pas à pas
Choisissez deux entiers et observez la suite des divisions euclidiennes. Chaque barre représente un reste successif. La convergence vers \(0\) révèle le PGCD.
Bézout, Gauss et équations diophantiennes
Pour tous \(a, b \in \mathbb{Z}\), il existe des entiers \(u, v \in \mathbb{Z}\) tels que \(au + bv = \text{pgcd}(a, b)\). En particulier :
\[ \text{pgcd}(a, b) = 1 \iff \exists\, u, v \in \mathbb{Z},\quad au + bv = 1. \]Ce couple \((u, v)\) n'est pas unique : si \((u_0, v_0)\) est une solution, toutes les solutions sont de la forme \(\left(u_0 + \tfrac{b}{d}k,\ v_0 - \tfrac{a}{d}k\right)\) avec \(d = \text{pgcd}(a,b)\) et \(k \in \mathbb{Z}\).
Pour trouver \(u, v\) tels que \(23u + 17v = 1\), on applique d'abord l'algorithme d'Euclide (en notant chaque étape), puis on remonte en sens inverse en exprimant les restes successifs comme combinaisons de \(23\) et \(17\).
Étape 1 — Descente :
\[ \begin{aligned} 23 &= 17 \times 1 + 6 \\ 17 &= 6 \times 2 + 5 \\ 6 &= 5 \times 1 + 1 \\ 5 &= 1 \times 5 + 0 \end{aligned} \]Étape 2 — Remontée :
\[ \begin{aligned} 1 &= 6 - 5 \times 1 \\ &= 6 - (17 - 6 \times 2) \times 1 = 3 \times 6 - 17 \\ &= 3 \times (23 - 17 \times 1) - 17 = 3 \times 23 - 4 \times 17. \end{aligned} \]Donc \(23 \times 3 + 17 \times (-4) = 1\) : un couple de Bézout est \((u, v) = (3, -4)\).
Toujours vérifier le résultat en recalculant \(au + bv\) : \(23 \times 3 + 17 \times (-4) = 69 - 68 = 1\). Cela prend dix secondes et évite les erreurs de signe dans la remontée.
Si \(a \mid bc\) et \(\text{pgcd}(a, b) = 1\), alors \(a \mid c\).
Corollaire : si \(a \mid n\), \(b \mid n\) et \(\text{pgcd}(a, b) = 1\), alors \(ab \mid n\).
Une équation diophantienne est une équation de la forme \(ax + by = c\) cherchée dans \(\mathbb{Z}^2\). Elle admet des solutions si et seulement si \(\text{pgcd}(a, b) \mid c\).
Exemple. Résoudre dans \(\mathbb{Z}^{2}\) : \(5x - 3y = 1\).
Étape 1 — Existence : \(\text{pgcd}(5, 3) = 1\), qui divise \(1\) : des solutions existent.
Étape 2 — Solution particulière : par inspection (ou Euclide), \(5 \times 2 - 3 \times 3 = 10 - 9 = 1\). Donc \((x_0, y_0) = (2, 3)\).
Étape 3 — Solution générale : si \((x, y)\) est solution, alors \(5(x - 2) = 3(y - 3)\). Donc \(3 \mid 5(x-2)\) ; comme \(\text{pgcd}(3,5) = 1\), Gauss donne \(3 \mid (x - 2)\), soit \(x = 2 + 3k\) pour \(k \in \mathbb{Z}\). On substitue : \(y = \dfrac{5x - 1}{3} = \dfrac{5(2+3k)-1}{3} = \dfrac{9+15k}{3} = 3 + 5k\).
\[ \mathcal{S} = \{(2 + 3k,\ 3 + 5k),\ k \in \mathbb{Z}\} \]Application de Gauss. Sachant que \(7 \mid 3n\) et \(\text{pgcd}(7,3)=1\), on conclut par Gauss que \(7 \mid n\). Simple mais puissant.
Équation sans solution. \(6x + 4y = 3\) : \(\text{pgcd}(6, 4) = 2\) et \(2 \nmid 3\), donc cette équation n'a aucune solution entière.
Équation avec second membre non unitaire. Résoudre \(7x + 5y = 11\). Bézout donne \(7 \times 3 + 5 \times (-4) = 1\), donc en multipliant par 11 : \(7 \times 33 + 5 \times (-44) = 11\). Solution particulière \((33, -44)\). Solution générale : \(x = 33 + 5k\), \(y = -44 - 7k\), \(k \in \mathbb{Z}\).