Terminale C · Leçon 18
Divisibilité dans ℤ
Ce que dit le programme officiel (17 points)
- la définition d’un diviseur d’un entier relatif
- la définition de la congruence modulo 𝑛
- la définition d’un nombre premier
- les propriétés relatives aux diviseurs d’un entier relatif
- la définition du quotient et du reste de la division euclidienne d’un entier relatif par un entier naturel non nul
- les propriétés relatives à la division euclidienne dans ℕ
- les propriétés relatives à la division euclidienne dans ℤ
- les propriétés relatives aux nombres premiers
- le théorème fondamental de la décomposition d’un entier naturel en produit de facteurs premiers
- la propriété relative à l’existence et à l’unicité de la décomposition d’un nombre en produit de facteurs premiers
- 𝑎 divise 𝑏 : 𝑎 l 𝑏
- Décomposer un entier en produit de facteurs premiers
- Reconnaître un nombre premier
- Déterminer le quotient et le reste de la division euclidienne d’un entier relatif par un entier naturel non nul
- l’ensemble des diviseurs d’un entier naturel non nul
- Démontrer qu’un entier est divisible par un entier non nul donné
- qu’un entier est divisible par un entier non nul donné en utilisant les caractères de divisibilité par 2 ; 3 ; 5 ; 9 ; 10 et 11
Source : Programme éducatif Terminale C, DPFC, version CND 0923
Divisibilité et division euclidienne dans ℤ
Avant d'étudier les nombres premiers ou les congruences, il faut solidifier la notion la plus élémentaire : celle de diviseur. Toute l'arithmétique en découle.
Soit \(a, b \in \mathbb{Z}\). On dit que \(b\) divise \(a\), noté \(b \mid a\), s'il existe un entier \(k \in \mathbb{Z}\) tel que \(a = k b\). On dit alors que \(a\) est un multiple de \(b\).
Si \(b \mid a\) et \(b \mid a'\), alors pour tous entiers \(u, v\), on a \(b \mid (ua + va')\) : la divisibilité se conserve par combinaison linéaire à coefficients entiers. En particulier, elle se conserve par addition et soustraction.
Quelques cas particuliers à mémoriser : \(1\) divise tout entier ; tout entier divise \(0\) ; si \(b \mid a\) et \(a \ne 0\), alors \(|b| \le |a|\). L'ensemble des multiples de \(b\) dans \(\mathbb{Z}\) se note \(b\mathbb{Z}\).
Facile. On a \(3 \mid 12\) car \(12 = 3 \times 4\). On a aussi \(3 \mid (-12)\) car \(-12 = 3 \times (-4)\). En revanche, \(3 \nmid 10\) car il n'existe pas d'entier \(k\) tel que \(10 = 3k\).
Intermédiaire. Montrons que si \(5 \mid a\) et \(5 \mid b\), alors \(5 \mid (2a - 3b)\). On écrit \(a = 5k\) et \(b = 5m\), donc \(2a - 3b = 10k - 15m = 5(2k - 3m)\). C'est bien un multiple de \(5\).
Plus avancé. Montrons que si \(7 \mid (a + 2b)\) et \(7 \mid (3a - b)\), alors \(7 \mid a\) et \(7 \mid b\). On calcule \((a+2b) + 2(3a-b) = 7a\), donc \(7 \mid 7a\), ce qui donne \(7 \mid a\). De même, \(3(a+2b)-(3a-b)=7b\), donc \(7 \mid b\).
Pour tous \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}^{*}\), il existe un unique couple \((q, r) \in \mathbb{Z} \times \mathbb{N}\) tel que :
\[ a = bq + r \quad \text{avec} \quad 0 \le r < |b|. \]\(q\) est le quotient euclidien et \(r\) le reste euclidien de la division de \(a\) par \(b\).
Le piège classique concerne les entiers négatifs. La règle est simple : on cherche le plus grand multiple de \(b\) qui reste inférieur ou égal à \(a\), de sorte que le reste soit dans \(\{0, 1, \ldots, |b|-1\}\).
Pour diviser \(-37\) par \(5\), on cherche \(q\) tel que \(5q \le -37\) et \(-37 - 5q < 5\). On trouve \(q = -8\) (car \(5 \times (-8) = -40 \le -37\) et \(5 \times (-7) = -35 > -37\)). Alors \(r = -37 - 5\times(-8) = 3\).
\[ -37 = 5 \times (-8) + 3 \quad (0 \le 3 < 5). \]\(127 = 9 \times 14 + 1\) : quotient \(14\), reste \(1\).
\(-100 = 7 \times (-15) + 5\), car \(7 \times (-15) = -105\) et \(-105 + 5 = -100\), avec \(0 \le 5 < 7\). Le quotient est \(-15\), le reste \(5\).
\(28 = 4 \times 7 + 0\) : le reste est \(0\), donc \(4 \mid 28\).
Ne jamais écrire \(-37 = 5 \times (-7) + (-2)\), même si le calcul est juste arithmétiquement. La condition \(r \ge 0\) est violée : \(-2 < 0\). Ce couple \((q, r)\) n'est pas le résultat de la division euclidienne.
Figure interactive — Division euclidienne
La droite des entiers montre graphiquement comment le dividende \(a\) se positionne entre deux multiples consécutifs de \(b\). Le reste \(r\) est la distance entre \(a\) et le multiple inférieur \(bq\).
Congruences et restes
Les congruences sont une façon de travailler dans un « monde circulaire » : modulo \(n\), on identifie tous les entiers qui ont le même reste par \(n\). C'est le langage naturel des cycles, des calendriers et des codes.
Soit \(n \in \mathbb{N}^{*}\). On dit que \(a\) et \(b\) sont congrus modulo \(n\), noté \(a \equiv b\ [n]\), si \(n \mid (a - b)\). De façon équivalente, \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Si \(a \equiv a'\ [n]\) et \(b \equiv b'\ [n]\), alors on peut additionner, soustraire et multiplier membre à membre :
\[ a + b \equiv a' + b'\ [n] \qquad a - b \equiv a' - b'\ [n] \qquad a \times b \equiv a' \times b'\ [n]. \]Par récurrence sur la propriété multiplicative, on obtient aussi la compatibilité avec les puissances entières :
\[ a \equiv a'\ [n] \implies a^k \equiv a'^k\ [n] \quad \text{pour tout } k \in \mathbb{N}. \]La division n'est pas compatible avec les congruences en général. Contre-exemple : \(4 \equiv 10\ [6]\) (car \(6 \mid -6\)), mais si on divise par \(2\), on obtiendrait \(2 \equiv 5\ [3]\), qui est faux (\(3 \nmid -3\)). On peut diviser une congruence par \(k\) uniquement si \(\text{pgcd}(k, n) = 1\), c'est-à-dire si \(k\) est premier avec le module.
Pour trouver le reste de \(a^n\) modulo \(m\), on cherche la période du cycle des restes de \(a^1, a^2, a^3, \ldots\) modulo \(m\). Le procédé : on réduit d'abord \(a\) modulo \(m\), on calcule les puissances successives jusqu'à retrouver \(1\) (ou la valeur de départ), puis on exprime \(n\) en fonction de cette période.
Exemple type Bac. Calculer le reste de \(7^{100}\) dans la division par \(5\).
Étape 1 — Réduction : \(7 \equiv 2\ [5]\), donc \(7^{100} \equiv 2^{100}\ [5]\).
Étape 2 — Cycle des restes de \(2^k\) modulo \(5\) :
\[ 2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 3,\quad 2^4 \equiv 1,\quad 2^5 \equiv 2,\ldots\ [5]. \]La période est \(4\). Étape 3 — Décomposition de l'exposant : \(100 = 4 \times 25\), donc \(2^{100} = (2^4)^{25} \equiv 1^{25} = 1\ [5]\).
Conclusion : le reste de \(7^{100}\) dans la division par \(5\) est \(\mathbf{1}\).
Critère de divisibilité par 9. Puisque \(10 \equiv 1\ [9]\), on a \(10^j \equiv 1\ [9]\) pour tout \(j \ge 0\). Tout entier \(N = a_k \cdot 10^k + \cdots + a_1 \cdot 10 + a_0\) vérifie donc \(N \equiv a_k + \cdots + a_1 + a_0\ [9]\). Ainsi \(9 \mid N\) si et seulement si la somme de ses chiffres est divisible par 9. Application : \(N = 2\,016\), somme des chiffres \(= 9\), donc \(9 \mid 2016\). Vérifié : \(2016 = 9 \times 224\).
Reste de \(3^{2025}\) modulo \(7\). Cycle de \(3^k\) mod 7 : \(3, 2, 6, 4, 5, 1\) (période 6). \(2025 = 6 \times 337 + 3\), donc \(3^{2025} \equiv 3^3 = 27 \equiv 6\ [7]\). Le reste est \(\mathbf{6}\).
Parité de \(n^2 + n\). Quel que soit \(n\), soit \(n \equiv 0\ [2]\) soit \(n \equiv 1\ [2]\). Dans les deux cas, \(n^2 + n = n(n+1)\) est le produit de deux entiers consécutifs, donc \(n^2 + n \equiv 0\ [2]\) : \(n^2 + n\) est toujours pair.
Figure interactive — Horloge modulaire
La roue montre les classes de congruence modulo \(n\). Chaque entier est placé sur la roue selon son reste par \(n\). Deux entiers se trouvent sur la même case si et seulement si ils sont congrus modulo \(n\).
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.
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}\).