Terminale S1-S3 · Leçon 5
Divisibilité, division euclidienne, congruences, numération
Ce que dit le programme officiel (5 points)
- Diviseurs d’un entier ; multiples d’un entier relatif
- Division euclidienne dans ℕ et dans ℤ
- Congruence modulo n ; utiliser les congruences pour résoudre des problèmes d’arithmétique
- Petit théorème de Fermat (utilisable) : si p est premier, pour tout entier naturel non nul x, xp ≡ x [p]
- Systèmes de numération à base dix, deux, cinq, seize : écrire un nombre dans une base donnée
Source : Programme de mathématiques, Terminales S1 et S3 (Sénégal), octobre 2006
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\).
Numération décimale et binaire
Nous écrivons les nombres avec dix chiffres parce que nous comptons par paquets de dix. Un ordinateur, lui, ne distingue que deux états et compte par paquets de deux : il écrit tous les entiers avec les seuls chiffres 0 et 1. Les deux écritures reposent sur le même principe, et l'on passe de l'une à l'autre par des divisions euclidiennes.
Base dix (système décimal). Tout entier naturel non nul \(n\) s'écrit d'une seule façon sous la forme
\[n=a_p\times 10^p+a_{p-1}\times 10^{p-1}+\cdots+a_1\times 10+a_0,\]où \(a_0,a_1,\ldots,a_p\) sont des entiers compris entre 0 et 9, avec \(a_p\neq 0\). Ce sont les chiffres de \(n\) : \(a_0\) est le chiffre des unités, \(a_1\) celui des dizaines, etc. Par exemple \(2037=2\times 10^3+0\times 10^2+3\times 10+7\).
Base deux (système binaire). De même, tout entier naturel non nul \(n\) s'écrit d'une seule façon sous la forme
\[n=b_q\times 2^q+b_{q-1}\times 2^{q-1}+\cdots+b_1\times 2+b_0,\]où chaque \(b_i\) vaut 0 ou 1, avec \(b_q=1\). On note alors \(n=\overline{b_q b_{q-1}\ldots b_1 b_0}^{\,2}\). Par exemple \(\overline{1101}^{\,2}=1\times 8+1\times 4+0\times 2+1=13\).
Puissances de 2 à connaître. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. En base deux, elles s'écrivent 1, 10, 100, 1000… : un 1 suivi de zéros.
Pourquoi l'écriture est unique. Le dernier chiffre \(b_0\) est le reste de la division euclidienne de \(n\) par 2, et les chiffres précédents forment l'écriture du quotient. Le reste et le quotient étant uniques, tous les chiffres le sont.
De la base dix à la base deux : divisions successives par 2. On divise \(n\) par 2 et l'on note le reste (0 ou 1) ; on divise le quotient par 2, et ainsi de suite, jusqu'à obtenir un quotient nul. L'écriture binaire de \(n\) est la suite des restes lus du dernier au premier.
Variante : soustraire des puissances de 2. On retire de \(n\) la plus grande puissance de 2 possible, puis on recommence avec ce qui reste. Les puissances utilisées donnent les chiffres 1, les autres les chiffres 0.
De la base deux à la base dix. On additionne les puissances de 2 qui correspondent aux chiffres 1, le chiffre de droite ayant le rang 0. On peut aussi lire les chiffres de gauche à droite en partant de 0 et en répétant « multiplier par 2, puis ajouter le chiffre ».
Contrôle. Un entier qui s'écrit avec \(k\) chiffres en base deux est compris entre \(2^{k-1}\) et \(2^k-1\).
Figure — Les divisions successives de 45 par 2
À gauche, la suite des quotients : 45, 22, 11, 5, 2, 1, puis 0, où l'on s'arrête. À droite, en or, le reste de chaque division. La flèche bleue indique le sens de lecture : du dernier reste au premier. On lit 1, 0, 1, 1, 0, 1, donc 45 s'écrit 101101 en base deux.
Énoncé. Écrire en base deux les entiers 45 et 100.
Solution : Pour 45, on effectue les divisions successives par 2 : \(45=2\times 22+1\) ; \(22=2\times 11+0\) ; \(11=2\times 5+1\) ; \(5=2\times 2+1\) ; \(2=2\times 1+0\) ; \(1=2\times 0+1\). Les restes, lus du dernier au premier, sont 1, 0, 1, 1, 0, 1 : \(45=\overline{101101}^{\,2}\). Vérification : \(32+8+4+1=45\).
Pour 100, on utilise les puissances de 2 : la plus grande qui ne dépasse pas 100 est 64, et \(100-64=36\) ; puis 32, et \(36-32=4\) ; puis 4, et il ne reste rien. Donc \(100=64+32+4=2^6+2^5+2^2\). Les rangs 6, 5 et 2 portent un 1, les rangs 4, 3, 1 et 0 un 0 : \(100=\overline{1100100}^{\,2}\).
Énoncé. Écrire en base dix les entiers \(\overline{110111}^{\,2}\) et \(\overline{11111111}^{\,2}\).
Solution : \(\overline{110111}^{\,2}=2^5+2^4+0+2^2+2+1=32+16+4+2+1=55\). Autre calcul, de gauche à droite, en multipliant par 2 puis en ajoutant le chiffre suivant : on obtient successivement 1, 3, 6, 13, 27, 55.
\(\overline{11111111}^{\,2}\) est la somme \(1+2+4+\cdots+2^7\) des huit premiers termes d'une suite géométrique de raison 2 : elle vaut \(2^8-1=255\). On peut aussi remarquer que l'entier suivant est \(\overline{100000000}^{\,2}=2^8=256\).
En base deux. Soit \(n\) un entier naturel non nul.
- \(n\) est pair si et seulement si son écriture binaire se termine par 0 ; il est multiple de 4 si elle se termine par 00, multiple de \(2^k\) si elle se termine par \(k\) zéros.
- Multiplier par 2 revient à écrire un 0 à droite ; le quotient de la division euclidienne par 2 s'obtient en effaçant le dernier chiffre.
- L'écriture binaire de \(n\) compte \(k\) chiffres si et seulement si \(2^{k-1}\leq n\lt 2^k\).
En base dix, par les congruences. Comme \(10\equiv 1\;[9]\), on a \(10^k\equiv 1\;[9]\) pour tout \(k\), donc
\[n\equiv a_p+a_{p-1}+\cdots+a_1+a_0\;[9].\]Un entier est congru modulo 9 (et donc modulo 3) à la somme de ses chiffres : il est divisible par 9, ou par 3, si et seulement si cette somme l'est. De même \(10\equiv -1\;[11]\), donc \(10^k\equiv(-1)^k\;[11]\) et
\[n\equiv a_0-a_1+a_2-a_3+\cdots\;[11].\]Un entier est divisible par 11 si et seulement si la somme alternée de ses chiffres, en partant des unités, l'est.
Énoncé. a) Calculer en base deux la somme \(\overline{1011}^{\,2}+\overline{110}^{\,2}\), puis le double de \(\overline{1011}^{\,2}\). b) Combien de chiffres l'écriture binaire de 1000 comporte-t-elle ? L'écrire. c) Sans effectuer de division, donner le reste de 4725 dans la division par 9, puis celui de 2918 dans la division par 11.
Solution : a) On pose l'addition comme en base dix, avec la règle \(1+1=\overline{10}^{\,2}\) (on écrit 0 et l'on retient 1). On trouve \(\overline{1011}^{\,2}+\overline{110}^{\,2}=\overline{10001}^{\,2}\). Vérification en base dix : \(11+6=17\). Le double de \(\overline{1011}^{\,2}\) s'obtient en écrivant un 0 à droite : \(\overline{10110}^{\,2}\), soit 22.
b) \(2^9=512\leq 1000\lt 1024=2^{10}\) : l'écriture binaire de 1000 a 10 chiffres. Comme \(1000=512+256+128+64+32+8\), on obtient \(1000=\overline{1111101000}^{\,2}\). Elle se termine par trois zéros : 1000 est multiple de 8 (et pas de 16).
c) \(4+7+2+5=18\equiv 0\;[9]\) : le reste de 4725 dans la division par 9 est 0, ce nombre est divisible par 9. Pour 2918, la somme alternée à partir des unités est \(8-1+9-2=14\equiv 3\;[11]\) : le reste dans la division par 11 est 3.
Lire les restes dans le mauvais sens. Le premier reste obtenu est le chiffre des unités, donc le chiffre de droite. Pour 45, écrire les restes dans l'ordre où on les trouve donnerait 101101 par hasard (cette écriture se lit de la même façon dans les deux sens) ; pour 100, on obtiendrait 0010011, qui est faux.
Oublier la base. L'écriture « 10 » désigne dix en base dix et deux en base deux ; « 101 » désigne cent un ou cinq. On indique toujours la base lorsqu'elle n'est pas dix.
Utiliser un chiffre interdit. En base deux, les seuls chiffres sont 0 et 1. Une écriture comme \(1021\) ne peut pas être une écriture binaire.
Numération en bases cinq et seize ; petit théorème de Fermat
Nous écrivons les nombres en base dix, les ordinateurs en base deux, et les informaticiens les relisent en base seize, plus compacte. Changer de base repose sur la division euclidienne. Le petit théorème de Fermat, de son côté, permet de calculer très vite le reste d'une grande puissance dans une division par un nombre premier.
Soit \(b\ge 2\) un entier. Tout entier naturel \(N\) non nul s'écrit de façon unique
\[N=a_kb^k+a_{k-1}b^{k-1}+\dots+a_1b+a_0,\]où les chiffres \(a_i\) sont des entiers tels que \(0\le a_i\le b-1\) et \(a_k\neq 0\). On note \(N=\overline{a_ka_{k-1}\dots a_1a_0}^{\,b}\), ou plus simplement \((a_k\dots a_0)_b\).
- En base deux, les chiffres sont 0 et 1.
- En base cinq, les chiffres sont 0, 1, 2, 3, 4.
- En base seize, on utilise 0 à 9 puis A, B, C, D, E, F pour les valeurs 10 à 15.
Le chiffre des unités \(a_0\) est le reste de la division de \(N\) par \(b\) : \(N\equiv a_0\ [b]\).
De la base dix vers la base \(b\). On divise \(N\) par \(b\), puis le quotient par \(b\), et ainsi de suite jusqu'à un quotient nul. Les restes successifs sont les chiffres, du chiffre des unités au chiffre de plus haut rang : on les lit du dernier au premier.
De la base \(b\) vers la base dix. On calcule \(a_kb^k+\dots+a_0\), de préférence par la méthode de Horner : \(\big((a_kb+a_{k-1})b+a_{k-2}\big)b+\dots\).
Entre les bases deux et seize. Comme \(16=2^4\), chaque chiffre de base seize correspond à un bloc de quatre chiffres binaires : on regroupe les chiffres binaires par quatre à partir de la droite, ou on remplace chaque chiffre hexadécimal par son écriture binaire sur quatre chiffres.
Soit \(p\) un nombre premier. Pour tout entier naturel \(x\),
\[x^p\equiv x\ [p].\]Si de plus \(p\) ne divise pas \(x\), alors \(x^{p-1}\equiv 1\ [p]\) (on peut simplifier par \(x\), qui est premier avec \(p\), d'après le théorème de Gauss).
Usage. Pour calculer le reste de \(x^n\) modulo \(p\), avec \(p\) premier ne divisant pas \(x\), on écrit la division euclidienne \(n=(p-1)q+r\) ; alors \(x^n=\left(x^{p-1}\right)^q x^r\equiv x^r\ [p]\).
La réciproque est fausse : \(2^{340}\equiv 1\ [341]\) alors que \(341=11\times31\) n'est pas premier.
Énoncé. Écrire le nombre 2026 en base cinq, puis en base seize et en base deux.
Solution : Divisions successives par 5 : \(2026=5\times405+1\), \(405=5\times81+0\), \(81=5\times16+1\), \(16=5\times3+1\), \(3=5\times0+3\). En lisant les restes du dernier au premier : \(2026=(31101)_5\). Contrôle : \(3\times625+1\times125+1\times25+0\times5+1=2026\).
Par 16 : \(2026=16\times126+10\), \(126=16\times7+14\), \(7=16\times0+7\). Donc \(2026=(7\mathrm{EA})_{16}\). Contrôle : \(7\times256+14\times16+10=2026\). En binaire, chaque chiffre donne quatre bits : \(7=0111\), \(\mathrm E=1110\), \(\mathrm A=1010\), d'où \(2026=(11111101010)_2\).
Figure — Les divisions successives par 5
Les divisions successives de 2026 par 5. À chaque ligne, le quotient devient le nombre à diviser à la ligne suivante. On lit les restes de bas en haut, dans le sens de la flèche : 3, 1, 1, 0, 1, ce qui donne l'écriture (31101) en base cinq.
Énoncé. Écrire en base dix les nombres \((4302)_5\) et \((\mathrm B3)_{16}\). Écrire \((10110111)_2\) en base seize.
Solution : Par la méthode de Horner : \((4302)_5=((4\times5+3)\times5+0)\times5+2=(23\times5)\times5+2=577\). Puis \((\mathrm B3)_{16}=11\times16+3=179\).
On regroupe les chiffres binaires par quatre à partir de la droite : \(1011\ 0111\). Or \((1011)_2=11=\mathrm B\) et \((0111)_2=7\). Donc \((10110111)_2=(\mathrm B7)_{16}=11\times16+7=183\).
Énoncé. a) Déterminer le reste de \(3^{100}\) dans la division par 7. b) Déterminer le reste de \(2^{2026}\) dans la division par 11. c) Montrer que, pour tout entier naturel \(n\), \(n^5-n\) est divisible par 5.
Solution : a) 7 est premier et ne divise pas 3, donc \(3^6\equiv 1\ [7]\). Or \(100=6\times16+4\), d'où \(3^{100}=\left(3^6\right)^{16}\times3^4\equiv 3^4=81\ [7]\), et \(81=7\times11+4\). Le reste est 4.
b) 11 est premier : \(2^{10}\equiv 1\ [11]\). Comme \(2026=10\times202+6\), \(2^{2026}\equiv 2^6=64\ [11]\), et \(64=11\times5+9\). Le reste est 9.
c) 5 est premier : d'après le petit théorème de Fermat, \(n^5\equiv n\ [5]\), donc 5 divise \(n^5-n\), pour tout entier naturel \(n\).
Lire les restes dans le mauvais sens. Le premier reste obtenu est le chiffre des unités : il s'écrit à droite. Lire de haut en bas donnerait \((10113)_5\), qui vaut 658.
Utiliser un chiffre trop grand. En base cinq, le chiffre 5 n'existe pas ; en base seize, « 14 » s'écrit E, d'un seul chiffre.
Appliquer le théorème de Fermat sans vérifier ses hypothèses. Il faut que le module soit premier : modulo 4, \(3^4=81\equiv 1\), et non 3. Pour \(x^{p-1}\equiv1\ [p]\), il faut en plus que \(p\) ne divise pas \(x\).
Résumé
En base dix, on décompose suivant les puissances de 10 avec des chiffres de 0 à 9 ; en base deux, suivant les puissances de 2 avec les chiffres 0 et 1.
Divisions successives par 2 ; on lit les restes du dernier au premier.
On additionne les puissances de 2 placées sous les chiffres 1 (rang 0 à droite).
\(k\) chiffres en base deux si et seulement si \(2^{k-1}\leq n\lt 2^k\).
\(n\) est congru à la somme de ses chiffres modulo 9 et modulo 3, et à leur somme alternée modulo 11.
Divisions successives par \(b\) ; on lit les restes du dernier au premier.
Un chiffre de base seize correspond à quatre chiffres binaires, car \(16=2^4\).
\(p\) premier : \(x^p\equiv x\ [p]\) ; si \(p\) ne divise pas \(x\), \(x^{p-1}\equiv1\ [p]\).