Terminale S1-S3 · Leçon 6
Nombres premiers, PGCD, PPCM, théorèmes de Bézout et de Gauss
Ce que dit le programme officiel (4 points)
- Nombres premiers ; décomposition d’un entier naturel en produit de facteurs premiers
- PGCD, PPCM de plusieurs entiers ; algorithme d’Euclide
- Identité de Bézout ; théorème de Gauss (démonstrations possibles, non exigées)
- Résoudre dans ℤ des équations du type ax + by = c (a, b, c entiers naturels)
Source : Programme de mathématiques, Terminales S1 et S3 (Sénégal), octobre 2006
Nombres premiers et décomposition
Les nombres premiers sont les atomes de l'arithmétique : tout entier supérieur à \(1\) se décompose de façon unique en produit de nombres premiers. Cette décomposition éclaire d'un seul coup le PGCD, le PPCM et le nombre de diviseurs.
Un entier \(p \ge 2\) est dit premier s'il admet exactement deux diviseurs positifs : \(1\) et \(p\) lui-même. Un entier \(n \ge 2\) non premier est dit composé.
Pour tester si \(n\) est premier, il suffit de vérifier qu'aucun entier premier \(p \le \sqrt{n}\) ne divise \(n\). En effet, si \(n = ab\) avec \(a \le b\), alors \(a^2 \le ab = n\), donc \(a \le \sqrt{n}\).
Exemple. \(\sqrt{197} \approx 14{,}03\). On teste les premiers \(2, 3, 5, 7, 11, 13\) : aucun ne divise \(197\). Donc \(\mathbf{197}\) est premier.
Contre-exemple. \(221 = 13 \times 17\). \(\sqrt{221} \approx 14{,}9\), et \(13 \le 14{,}9\) divise \(221\) : \(221\) est composé.
On divise successivement par les premiers dans l'ordre croissant (\(2, 3, 5, 7, \ldots\)) jusqu'à ce que le quotient soit \(1\).
\(360 \div 2 = 180\) ; \(180 \div 2 = 90\) ; \(90 \div 2 = 45\) ; \(45 \div 3 = 15\) ; \(15 \div 3 = 5\) ; \(5 \div 5 = 1\). Donc \(360 = 2^3 \times 3^2 \times 5\).
Nombre de diviseurs positifs de \(360\) : \(\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = \mathbf{24}\).
Il existe une infinité de nombres premiers.
Esquisse de la démonstration d'Euclide. Supposons par l'absurde qu'il n'en existe qu'un nombre fini \(p_1, \ldots, p_k\). Considérons \(N = p_1 p_2 \cdots p_k + 1\). Alors \(N \ge 2\) admet un diviseur premier \(p\). Mais \(p\) ne peut être aucun des \(p_i\) car \(N \equiv 1\ [p_i]\) pour tout \(i\). Contradiction : l'ensemble des premiers ne peut être fini.
Tout entier \(n \ge 2\) s'écrit de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers :
\[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} \qquad (p_1 < p_2 < \cdots < p_r \text{ premiers},\ \alpha_i \ge 1). \]Pour \(a = \prod p_i^{\alpha_i}\) et \(b = \prod p_i^{\beta_i}\) (en complétant par des exposants nuls si nécessaire) :
\[ \text{pgcd}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)} \qquad \text{ppcm}(a,b) = \prod p_i^{\max(\alpha_i,\beta_i)}. \]Exemple : \(360 = 2^3 \times 3^2 \times 5\) et \(126 = 2 \times 3^2 \times 7\). Alors \(\text{pgcd}(360, 126) = 2^1 \times 3^2 = 18\) et \(\text{ppcm}(360, 126) = 2^3 \times 3^2 \times 5 \times 7 = 2520\).
Crible d'Ératosthène (manuel). Pour lister les premiers jusqu'à 30 : on barre les multiples de \(2, 3, 5\) (car \(\sqrt{30} < 6\)). Il reste : \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29\) — dix nombres premiers.
Nombre de diviseurs. \(n = 2^4 \times 3 \times 5^2\) a \((4+1)(1+1)(2+1) = 30\) diviseurs positifs.
Condition de divisibilité par \(p\) premier. Si \(p\) est premier et \(p \mid ab\), alors \(p \mid a\) ou \(p \mid b\) : c'est une version forte de Gauss, spécifique aux nombres premiers.
Figure interactive — Crible d'Ératosthène
Le crible filtre les nombres composés un premier à la fois. Sélectionnez un premier pour voir ses multiples barrés. Les cases restantes non barrées sont des nombres premiers.
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}\).
Résumé
\(a = bq + r\) avec \(0 \le r < |b|\). Le reste est toujours positif ou nul, y compris quand \(a < 0\).
Compatibles avec \(+\), \(-\), \(\times\) et les puissances. Pour les grands exposants : chercher la période du cycle des restes. La division ne se simplifie que si \(\text{pgcd}(k, n) = 1\).
\(\text{pgcd}(a,b) = \text{pgcd}(b, r)\). Répéter jusqu'au reste nul. \(\text{pgcd} \times \text{ppcm} = |ab|\).
\(\text{pgcd}(a,b) = 1 \iff \exists\, u, v,\ au + bv = 1\). Si \(a \mid bc\) et \(\text{pgcd}(a,b)=1\), alors \(a \mid c\). Clés des équations diophantiennes.
Tester les premiers jusqu'à \(\sqrt{n}\). Décomposition unique. \(\tau(n) = \prod (\alpha_i + 1)\) diviseurs. \(\text{pgcd}\) et \(\text{ppcm}\) via \(\min\)/\(\max\) des exposants.
Sujet type Bac
On considère les entiers \(a = 357\) et \(b = 231\). Les cinq questions suivantes sont progressives : chaque résultat sert à la suivante.
Question 1 — Division euclidienne. Effectuer la division euclidienne de \(a\) par \(b\). Vérifier le résultat.
On cherche \(q\) et \(r\) tels que \(357 = 231q + r\) avec \(0 \le r < 231\). Le quotient est \(q = 1\) (car \(231 \times 1 = 231 \le 357 < 231 \times 2 = 462\)). Donc \(r = 357 - 231 = 126\).
\[357 = 231 \times 1 + 126 \quad (0 \le 126 < 231)\]Vérification : \(231 + 126 = 357\). Correct.
Question 2 — Algorithme d'Euclide. Calculer \(\text{pgcd}(357, 231)\) par l'algorithme d'Euclide. En déduire \(\text{ppcm}(357, 231)\).
On reprend le reste de la question 1 et on continue :
\[ \begin{aligned} 357 &= 231 \times 1 + 126 \\ 231 &= 126 \times 1 + 105 \\ 126 &= 105 \times 1 + 21 \\ 105 &= 21 \times 5 + 0 \end{aligned} \]Le dernier reste non nul est \(21\), donc \(\text{pgcd}(357, 231) = \mathbf{21}\).
On en déduit :
\[ \text{ppcm}(357, 231) = \frac{357 \times 231}{21} = \frac{82467}{21} = \mathbf{3927}. \]Question 3 — Identité de Bézout. Trouver des entiers \(u, v\) tels que \(357u + 231v = 21\).
Puisque \(\text{pgcd}(357, 231) = 21\), Bézout assure l'existence de \(u, v\). On remonte l'algorithme. On commence par exprimer chaque reste en fonction des précédents :
\[ \begin{aligned} 21 &= 126 - 105 \times 1 \\ &= 126 - (231 - 126) = 2 \times 126 - 231 \\ &= 2(357 - 231) - 231 = 2 \times 357 - 3 \times 231. \end{aligned} \]Donc \(357 \times 2 + 231 \times (-3) = 21\) : un couple de Bézout est \((u, v) = (2, -3)\).
Vérification : \(357 \times 2 - 231 \times 3 = 714 - 693 = 21\). Correct.
Question 4 — Équation diophantienne. Résoudre dans \(\mathbb{Z}^{2}\) l'équation \(357x + 231y = 42\).
Le membre de droite est \(42 = 2 \times 21\). Comme \(\text{pgcd}(357, 231) = 21\) divise \(42\), l'équation admet des solutions.
En multipliant par \(2\) la relation de Bézout \(357 \times 2 + 231 \times (-3) = 21\) : \(357 \times 4 + 231 \times (-6) = 42\). Une solution particulière est \((x_0, y_0) = (4, -6)\).
Solution générale : si \((x, y)\) est solution, \(357(x - 4) + 231(y + 6) = 0\), soit \(357(x-4) = -231(y+6)\). En divisant par \(\text{pgcd}(357,231) = 21\) : \(17(x-4) = -11(y+6)\). Comme \(\text{pgcd}(17, 11) = 1\), Gauss donne \(11 \mid (x-4)\), soit \(x - 4 = 11k\), d'où \(x = 4 + 11k\). Alors \(y + 6 = -17k\), soit \(y = -6 - 17k\).
\[ \mathcal{S} = \{(4 + 11k,\ -6 - 17k),\ k \in \mathbb{Z}\} \]Question 5 — Congruences et grand exposant. Calculer le reste de \(231^{50}\) dans la division par \(17\).
Étape 1 — On réduit \(231\) modulo \(17\) : \(231 = 17 \times 13 + 10\), donc \(231 \equiv 10\ [17]\). Ainsi \(231^{50} \equiv 10^{50}\ [17]\).
Étape 2 — On note que \(10 \equiv -7\ [17]\), donc \(10^{50} \equiv (-7)^{50} = 7^{50}\ [17]\) (l'exposant est pair).
Étape 3 — Cycle de \(7^k\) modulo \(17\) (le théorème de Fermat donne la période divisant \(16\)) : \(7^1 \equiv 7\), \(7^2 \equiv 49 \equiv 15 \equiv -2\), \(7^4 \equiv (-2)^2 = 4\), \(7^8 \equiv 16 \equiv -1\), \(7^{16} \equiv 1\ [17]\). La période est \(16\).
Étape 4 — Décomposition : \(50 = 16 \times 3 + 2\), donc \(7^{50} = (7^{16})^3 \times 7^2 \equiv 1^3 \times (-2) = -2 \equiv 15\ [17]\).
Conclusion : le reste de \(231^{50}\) dans la division par \(17\) est \(\mathbf{15}\).