Mathématiques du lycée · Grades 10–12

29Arithmétique

L’arithmétique étudie les entiers : divisibilité, nombres premiers, restes. Longtemps considérée comme la plus pure des mathématiques pures, elle protège désormais tout paiement en ligne : le cryptosystème RSA repose sur les théorèmes de Bézout, Gauss et Fermat prouvés dans ce chapitre.

29.1 Divisibilité et division euclidienne

Définition 29.1 (Divisibilité)

Soient $a, b \in \Z$ . On dit que $b$ divise $a$ , noté $b \mid a$ , s’il existe $k \in \Z$ avec $a = kb$ . On dit aussi que $a$ est un multiple de $b$ .

Proposition 29.2

Si $c \mid a$ et $c \mid b$ , alors $c$ divise toute combinaison entière $au + bv$ ( $u, v \in \Z$ ). Si $a \mid b$ et $b \mid a$ avec $a,b \in \N$ , alors $a = b$ . Si $a \mid b$ et $b \neq 0$ , alors $\abs a \leq \abs b$ .

Démonstration. Écrire $a = kc$ , $b = lc$ : alors $au + bv = (ku + lv)c$ . Les autres points suivent de $\abs{a} = \abs{k}\,\abs{b}$ avec $\abs k \geq 1$ lorsque $b = ka \neq 0$ . ∎

Théorème 29.3 (Division euclidienne)

Soient $a \in \Z$ et $b \in \N^*$ . Il existe un unique couple $(q, r) \in \Z \times \N$ tel que

a = bq + r \qquad\text{et}\qquad 0 \leq r < b .

$q$ est le quotient et $r$ le reste.

Démonstration. Existence. L’ensemble des multiples de $b$ ne dépassant pas $a$ a un plus grand élément $bq$ (il est non vide et majoré) ; poser $r = a - bq$ . Par maximalité, $b(q+1) > a$ , donc $0 \leq r < b$ . Unicité. Si $bq + r = bq' + r'$ avec $0 \leq r, r' < b$ , alors $b(q - q') = r' - r$ et $\abs{r' - r} < b$ : un multiple de $b$ de valeur absolue strictement inférieure à $b$ doit être $0$ , donc $r = r'$ et $q = q'$ . ∎

29.2 Congruences

Définition 29.4 (Congruence)

Soit $n \in \N^*$ . Deux entiers $a, b$ sont congrus modulo $n$ , noté $a \equiv b \pmod n$ , si $n \mid (a - b)$ — de façon équivalente, si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

Proposition 29.5 (Compatibilité avec les opérations)

Si $a \equiv b \pmod n$ et $c \equiv d \pmod n$ , alors

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

Démonstration. $n$ divise $(a-b) + (c-d) = (a+c) - (b+d)$ , et $ac - bd = a(c - d) + d(a - b)$ est aussi un multiple de $n$ . La règle des puissances suit par récurrence à partir de la règle du produit. ∎

Méthode 29.6 (Calculer des puissances modulo $n$ )

Pour calculer $a^k \bmod n$ , réduire la base modulo $n$ , puis chercher une petite puissance de $a$ congrue à $\pm1$ , et s’en servir pour simplifier l’exposant. Par exemple $2^{100} \bmod 7$ : comme $2^3 = 8 \equiv 1 \pmod 7$ et $100 = 3\times33 + 1$ ,

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 PGCD, Bézout et Gauss

Définition 29.7 (PGCD)

Soient $a, b$ des entiers non tous deux nuls. Le plus grand commun diviseur $\gcd(a, b)$ est le plus grand entier divisant à la fois $a$ et $b$ . Lorsque $\gcd(a,b) = 1$ , $a$ et $b$ sont dits premiers entre eux.

Proposition 29.8 (Algorithme d’Euclide)

Si $a = bq + r$ ( $b \neq 0$ ), alors $\gcd(a, b) = \gcd(b, r)$ . Itérer la division euclidienne calcule donc $\gcd(a,b)$ : le pgcd est le dernier reste non nul.

Démonstration. Tout diviseur commun de $a$ et $b$ divise $r = a - bq$ (Proposition 29.2), donc est un diviseur commun de $b$ et $r$ ; et réciproquement, puisque $a = bq + r$ . Les deux couples ont les mêmes diviseurs communs, donc le même pgcd. L’algorithme se termine car les restes forment une suite strictement décroissante d’entiers positifs ou nuls. ∎

Exemple 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Donc $\gcd(252,198) = 18$ .

Théorème 29.10 (Identité de Bézout)

Soient $a, b$ des entiers non tous deux nuls, et $d = \gcd(a,b)$ . Il existe $u, v \in \Z$ tels que

au + bv = d .

En particulier, $a$ et $b$ sont premiers entre eux si et seulement s’il existe des entiers $u, v$ avec $au + bv = 1$ .

Démonstration. Remonter l’algorithme d’Euclide : chaque reste est une combinaison entière des deux précédents, et les données initiales $a, b$ sont des combinaisons d’elles-mêmes ; par substitutions descendantes, le dernier reste non nul $d$ est une combinaison entière de $a$ et $b$ . (Dans Exemple 29.9 : $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

Pour l’équivalence : si $\gcd(a,b) = 1$ , Bézout fournit $u, v$ ; réciproquement, tout diviseur commun de $a$ et $b$ divise $au + bv = 1$ , ce qui force $\gcd(a,b) = 1$ . ∎

Théorème 29.11 (Lemme de Gauss)

Soient $a, b, c \in \Z$ . Si $a \mid bc$ et $\gcd(a, b) = 1$ , alors $a \mid c$ .

Démonstration. Bézout donne $au + bv = 1$ ; multiplier par $c$ : $acu + bcv = c$ . Les deux termes du membre de gauche sont des multiples de $a$ (le second car $a \mid bc$ ), donc $c$ l’est aussi. ∎

Corollaire 29.12

Si $a \mid c$ , $b \mid c$ et $\gcd(a,b) = 1$ , alors $ab \mid c$ .

Démonstration. Écrire $c = ak$ . De $b \mid ak$ et $\gcd(a,b)=1$ , Gauss donne $b \mid k$ , disons $k = bl$ ; alors $c = abl$ . ∎

29.4 Nombres premiers

Définition 29.13 (Premier)

Un entier $p \geq 2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$ .

Proposition 29.14

Tout entier $n \geq 2$ a un diviseur premier ; si $n$ n’est pas premier, il a un diviseur premier $\leq \sqrt n$ . Si un premier $p$ divise un produit $ab$ , alors $p \mid a$ ou $p \mid b$ (lemme d’Euclide).

Démonstration. Le plus petit diviseur $d \geq 2$ de $n$ est premier (tout diviseur propre de $d$ serait un plus petit diviseur de $n$ ). Si $n = de$ est composé avec $2 \leq d \leq e$ , alors $d^2 \leq de = n$ , donc $d \leq \sqrt n$ . Pour le lemme d’Euclide : si $p \nmid a$ , alors $\gcd(p, a) = 1$ (les seuls diviseurs de $p$ sont $1$ et $p$ ), et le lemme de Gauss donne $p \mid b$ . ∎

Théorème 29.15 (Euclide)

Il existe une infinité de nombres premiers.

Démonstration. Étant donnée une liste finie $p_1, \dots, p_k$ de premiers, considérer $N = p_1 p_2 \cdots p_k + 1$ . Un certain premier $p$ divise $N$ ; mais aucun $p_i$ ne divise $N$ (le reste est $1$ ), donc $p$ est un premier hors de la liste. Aucune liste finie n’épuise les premiers. ∎

Théorème 29.16 (Théorème fondamental de l’arithmétique)

Tout entier $n \geq 2$ est un produit de premiers, et cette factorisation est unique à l’ordre des facteurs près :

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ premiers},\ \alpha_i \geq 1 .

Démonstration. Existence, par récurrence forte : $n$ premier est sa propre factorisation ; sinon $n = de$ avec $2 \leq d, e < n$ , et les deux se factorisent par l’hypothèse de récurrence. Unicité : supposer $p_1\cdots p_s = q_1 \cdots q_t$ (premiers, avec répétitions autorisées). Par le lemme d’Euclide, $p_1$ divise un certain $q_j$ , et étant premier, $p_1 = q_j$ ; annuler et recommencer. Les deux factorisations coïncident terme à terme. ∎

Théorème 29.17 (Petit théorème de Fermat)

Soit $p$ premier et $a \in \Z$ avec $p \nmid a$ . Alors

a^{p-1} \equiv 1 \pmod p .

Pour tout $a \in \Z$ (sans hypothèse de primalité relative), $a^p \equiv a \pmod p$ .

Démonstration. Considérer les $p - 1$ entiers $a, 2a, 3a, \dots, (p-1)a$ modulo $p$ . Aucun n’est $\equiv 0$ (si $p \mid ka$ avec $1 \leq k \leq p-1$ , le lemme d’Euclide force $p \mid k$ , impossible), et ils sont deux à deux distincts modulo $p$ (si $ka \equiv la$ , alors $p \mid (k - l)a$ , donc $p \mid k - l$ , donc $k = l$ ). D’où, modulo $p$ , ce sont les nombres $1, 2, \dots, p-1$ dans un certain ordre. En multipliant toutes les congruences :

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

Comme $p$ ne divise aucun de $1, \dots, p-1$ , l’usage répété du lemme d’Euclide permet d’annuler $(p-1)!$ , d’où $a^{p-1} \equiv 1$ . La seconde forme suit en multipliant par $a$ (et est triviale lorsque $p \mid a$ ). ∎

Exemple 29.18 (Application à la cryptographie)

Le théorème de Fermat rend l’exponentiation modulo $n$ réversible lorsque les exposants sont bien choisis — le cœur du cryptosystème RSA. Avec $p, q$ grands premiers et $n = pq$ , on publie $n$ et un exposant $e$ ; le chiffrement est $x \mapsto x^e \bmod n$ . Déchiffrer requiert un exposant $d$ avec $ed \equiv 1 \pmod{(p-1)(q-1)}$ , que seul celui qui connaît $p$ et $q$ peut calculer — et retrouver $p, q$ à partir de $n$ signifie factoriser un nombre de centaines de chiffres, ce qu’aucun algorithme connu ne fait en temps raisonnable.

29.5 Exercices

Exercice 29.1 ★

Calculer le quotient et le reste de la division euclidienne de $2026$ par $17$ , et de $-2026$ par $17$ .

Solution

Solution de Exercice 29.1.

$17 \times 119 = 2023$ , donc $2026 = 17 \times 119 + 3$ : quotient $119$ , reste $3$ . Pour $-2026$ : $-2026 = 17\times(-120) + 14$ (en effet $17 \times 120 = 2040$ et $2040 - 2026 = 14$ ) : quotient $-120$ , reste $14$ (le reste doit être dans $\intco{0}{17}$ , donc ce n’est pas $-3$ ).

Exercice 29.2 ★

Quel est le reste de $7^{100}$ modulo $10$ ? (Quel est le dernier chiffre de $7^{100}$ ?)

Solution

Solution de Exercice 29.2.

Modulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . D’où $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : le dernier chiffre de $7^{100}$ est $1$ .

Exercice 29.3 ★

À l’aide de l’algorithme d’Euclide, calculer $\gcd(1071, 462)$ , et trouver des entiers $u, v$ avec $1071u + 462v = \gcd(1071, 462)$ .

Solution

Solution de Exercice 29.3.

Euclide : $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ . Donc $\gcd = 21$ .

Remontée : $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . Ainsi $u = -3$ , $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

Exercice 29.4 ★

Montrer que pour tout $n \in \Z$ , $n^2$ est congru à $0$ ou $1$ modulo $4$ . En déduire qu’un entier $\equiv 3 \pmod 4$ n’est jamais somme de deux carrés.

Solution

Solution de Exercice 29.4.

Tout entier est $\equiv 0, 1, 2$ ou $3 \pmod 4$ , et en élevant au carré : $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . Donc $n^2 \equiv 0$ ou $1 \pmod 4$ . Une somme de deux carrés est alors congrue à $0 + 0$ , $0 + 1$ ou $1 + 1$ , c.-à-d. à $0$ , $1$ ou $2 \pmod 4$ — jamais à $3$ .

Exercice 29.5 ★★

Montrer que pour tout $n \in \N$ , $n(n+1)(2n+1)$ est divisible par $6$ .

Solution

Solution de Exercice 29.5.

Divisibilité par $2$ : parmi $n$ et $n + 1$ , l’un est pair. Divisibilité par $3$ : si $n \equiv 0$ , alors $3 \mid n$ ; si $n \equiv 1 \pmod 3$ , alors $2n + 1 \equiv 3 \equiv 0$ ; si $n \equiv 2$ , alors $n + 1 \equiv 0$ . Dans tous les cas $3$ divise le produit. Comme $\gcd(2,3) = 1$ , le Corollaire 29.12 donne $6 \mid n(n+1)(2n+1)$ . (Cela reprouve aussi que $\frac{n(n+1)(2n+1)}{6}$ , la somme des carrés de l’Exercice 20.1, est un entier.)

Exercice 29.6 ★★

Résoudre dans $\Z$ la congruence $5x \equiv 3 \pmod{11}$ . (Indication : trouver l’inverse de $5$ modulo $11$ .)

Solution

Solution de Exercice 29.6.

On cherche l’inverse de $5$ modulo $11$ : en testant (ou Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . En multipliant la congruence par $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

Les solutions sont les entiers $x = 5 + 11k$ , $k \in \Z$ . (Vérification : $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Exercice 29.7 ★★

Résoudre dans $\Z \times \Z$ l’équation diophantienne

17x - 40y = 1,

puis décrire toutes les solutions de $17x - 40y = 6$ .

Solution

Solution de Exercice 29.7.

$\gcd(17, 40) = 1$ , donc des solutions existent. Euclide : $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . En remontant : $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . D’où $17\times(-7) - 40\times(-3) = 1$ : la solution particulière $(x_0, y_0) = (-7, -3)$ .

Solution générale de $17x - 40y = 1$ : en soustrayant la relation particulière, $17(x + 7) = 40(y + 3)$ ; comme $\gcd(17, 40) = 1$ , Gauss donne $40 \mid x + 7$ , donc $x = -7 + 40k$ puis $y = -3 + 17k$ , $k \in \Z$ (qui toutes vérifient).

Pour $17x - 40y = 6$ , multiplier la solution particulière par $6$ : $(x_1, y_1) = (-42, -18)$ , et le même raisonnement donne

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(Par ex. $k = 2$ : $x = 38$ , $y = 16$ ; en effet $17\times38 - 40\times16 = 646 - 640 = 6$ .)

Exercice 29.8 ★★

Montrer que $\sqrt2$ est irrationnel, en utilisant l’unicité de la factorisation en premiers (comparer l’exposant de $2$ des deux côtés de $a^2 = 2b^2$ ).

Solution

Solution de Exercice 29.8.

Supposer $\sqrt2 = \frac ab$ avec $a, b \in \N^*$ ; alors $a^2 = 2b^2$ . Dans la factorisation d’un carré, tout exposant est pair ; donc l’exposant de $2$ dans $a^2$ est pair, tandis que dans $2b^2$ il est impair (un de plus qu’un nombre pair). Deux factorisations du même entier avec des exposants de $2$ différents contredisent l’unicité du Théorème 29.16. Donc aucune telle fraction n’existe : $\sqrt2 \notin \Q$ .

Exercice 29.9 ★★★

Soit $p$ un nombre premier.

Montrer que pour $1 \leq k \leq p - 1$ , $p$ divise $\dbinom{p}{k}$ . (Indication : utiliser $k\binom pk = p\binom{p-1}{k-1}$ , Exercice 27.7, et le lemme de Gauss.)
En déduire, par récurrence sur $a \geq 0$ , une autre preuve du petit théorème de Fermat sous la forme $a^p \equiv a \pmod p$ .

Solution

Solution de Exercice 29.9.

1. De $k\binom pk = p \binom{p-1}{k-1}$ , $p$ divise $k\binom pk$ . Pour $1 \leq k \leq p-1$ , $p \nmid k$ et $p$ premier donnent $\gcd(p, k) = 1$ , donc le lemme de Gauss fournit $p \mid \binom pk$ .

2. Récurrence sur $a$ . Pour $a = 0$ : $0^p \equiv 0$ . Supposer $a^p \equiv a \pmod p$ . Par la formule du binôme,

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

tous les termes du milieu s’annulant modulo $p$ par le point 1. Par l’hypothèse de récurrence, $(a+1)^p \equiv a + 1 \pmod p$ . Cela prouve $a^p \equiv a$ pour tout $a \in \N$ , et le cas $a < 0$ suit en écrivant $a \equiv a + kp$ pour un représentant positif convenable.

Exercice 29.10 ★★★

(Problème chinois des restes.) Trouver tous les entiers $n$ tels que

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(Indication : résoudre les deux premières conditions, puis incorporer la troisième ; les coefficients de Bézout aident.)

Solution

Solution de Exercice 29.10.

$n \equiv 2 \pmod 3$ et $n \equiv 3 \pmod 5$ : écrire $n = 2 + 3s$ ; alors $2 + 3s \equiv 3 \pmod 5$ , c.-à-d. $3s \equiv 1 \pmod 5$ . L’inverse de $3$ modulo $5$ est $2$ ( $3\times2 = 6 \equiv 1$ ), donc $s \equiv 2 \pmod 5$ , disons $s = 2 + 5t$ , et $n = 8 + 15t$ : les deux premières conditions signifient $n \equiv 8 \pmod{15}$ .

En ajoutant $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ , et $15 \equiv 1 \pmod 7$ , donc $t \equiv -6 \equiv 1 \pmod 7$ , disons $t = 1 + 7u$ . D’où $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(Vérification : $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 Problème : codes secrets et clés de contrôle

Problème 29.1

Devoir du week-end — les congruences gardent tous les codes-barres et toutes les cartes bancaires, et le petit théorème de Fermat fait tourner la serrure des secrets du monde

G. H. Hardy se vantait en 1940 de ce que la théorie des nombres fût « non souillée » par les applications. Quatre-vingts ans plus tard, chaque bip de code-barres, chaque paiement par carte et chaque message chiffré le contredisent — et précisément avec les outils de ce chapitre : les congruences (Proposition 29.5), les inverses de Bézout (Théorème 29.10) et le petit théorème de Fermat (Exercice 29.9). Ce problème contrôle les codes, force une version jouet de la serrure, et apprend pourquoi la vraie serrure tient bon.

Partie I — Aisance avec les congruences.

Calculer $2026 \bmod 7$ ; puis le chiffre des unités de $7^{100}$ (trouver le cycle des puissances de $7$ modulo $10$ ).
Exponentiation rapide (Méthode 29.6) : calculer $5^{117} \bmod 13$ (partir de $5^2 \equiv -1$ ).
Résoudre $3x \equiv 5 \pmod 7$ .
Dérouler l’algorithme d’Euclide sur $(97, 35)$ , remonter les calculs pour trouver des entiers $u, v$ tels que $97u + 35v = 1$ , et en déduire l’inverse de $35$ modulo $97$ .
Énoncer précisément quand $a$ est inversible modulo $n$ , et quel théorème fournit l’inverse.

Partie II — Clés de contrôle.

ISBN à dix chiffres : les dix chiffres $d_1 \dots d_{10}$ d’un code de livre doivent vérifier $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Vérifier l’ISBN réel $0\,306\,40615\,2$ .
Démontrer que ce dispositif détecte toute erreur sur un seul chiffre : si un chiffre change de $d \not\equiv 0$ , la somme pondérée change de $w d$ avec $1 \leq w \leq 10$ — pourquoi cela ne peut-il jamais être $\equiv 0 \pmod{11}$ (Théorème 29.11) ?
Démontrer qu’il détecte aussi toute transposition de deux chiffres adjacents distincts. Puis expliquer le secret de conception : quelle propriété de $11$ a fait fonctionner les deux démonstrations, et qu’est-ce qui pourrait mal tourner avec le module $10$ ?
Les codes-barres EAN à treize chiffres pondèrent les chiffres par $1, 3, 1, 3, \dots$ modulo $10$ . Calculer la clé de contrôle qui complète $978\,2940199\,05$ . Quelles transpositions adjacentes l’EAN échoue-t-il à détecter ? (Quand a-t-on $2(a - b) \equiv 0 \pmod{10}$ ?)
Les cartes bancaires emploient la formule de Luhn : en partant de la droite, doubler un chiffre sur deux (en retranchant $9$ si le double dépasse $9$ ), tout sommer, et exiger un multiple de $10$ . Vérifier le numéro de test $4539\,1488\,0343\,6467$ .
En une phrase : qu’est-ce que le module premier a offert à l’ISBN et que l’EAN et Luhn, enchaînés à $10$ , ne peuvent pas avoir ?

Partie III — La serrure de Fermat.

Un piège avant le trésor : calculer $2^{10} \bmod 341$ , en déduire $2^{340} \bmod 341$ — puis factoriser $341$ . Que dit cet exemple (un pseudo-premier de Fermat) sur l’emploi du petit théorème de Fermat comme test de primalité ?
RSA en miniature : prenons $p = 3$ , $q = 11$ , de sorte que $n = 33$ et $(p-1)(q-1) = 20$ ; l’exposant public est $e = 3$ . Déterminer l’exposant privé $d$ tel que $3d \equiv 1 \pmod{20}$ (méthode de la question 4).
Chiffrer le message $m = 4$ : calculer $c = m^3 \bmod 33$ .
Déchiffrer : calculer $c^d \bmod 33$ (en utilisant $c \equiv -2 \pmod{33}$ ) et retrouver le message.
Pourquoi le déchiffrement fonctionne toujours : montrer que $m^{21} \equiv m$ à la fois modulo $3$ et modulo $11$ (le petit théorème de Fermat dans chacun des deux mondes), et conclure modulo $33$ (le Théorème 29.11 recolle les deux congruences). Où la forme particulière $21 = ed = 1 + 20k$ est-elle intervenue ?
La sûreté de la serrure : tout le monde connaît $n$ et $e$ ; retrouver $d$ exige $(p-1)(q-1)$ , donc les facteurs de $n$ . Notre $33$ se factorise à vue — pourquoi le même dispositif, avec un $n$ de six cents chiffres, protège-t-il les banques du monde entier ? (Une phrase sur l’asymétrie entre multiplier et factoriser.)

Partie IV — Classiques.

Le vieux dénombrement chinois des soldats (à comparer avec l’Exercice 29.10) : un effectif de soldats laisse un reste de $2$ lorsqu’on les range par $3$ et un reste de $3$ lorsqu’on les range par $5$ . Déterminer tous les effectifs possibles, et expliquer pourquoi la réponse est unique modulo $15$ .
Enfin des démonstrations d’une ligne : à partir de $10 \equiv 1 \pmod 9$ , démontrer que tout nombre est congru à la somme de ses chiffres modulo $9$ ; à partir de $10 \equiv -1 \pmod{11}$ , établir la règle de la somme alternée pour $11$ . (Le volume précédent les démontrait par de l’algèbre explicite — admirer la compression.)
Pour finir — Hardy face au code-barres : récapituler la trousse du chapitre (arithmétique des congruences, inverses de Bézout, petit théorème de Fermat, recollement de modules premiers entre eux) et l’endroit où chacun s’est enclenché dans ce problème ; puis rendre le verdict moderne sur la « non-souillure ».

Solution

Solution de Problème 29.1.

1. $2026 = 289 \times 7 + 3$ , donc $2026 \equiv 3 \pmod 7$ . Puissances de $7$ modulo $10$ : $7, 9, 3, 1$ , cycle de longueur $4$ ; comme $100 \equiv 0 \pmod 4$ , le chiffre des unités de $7^{100}$ est $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ , donc $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ et $5^{117} \equiv 5 \pmod{13}$ .

3. L’inverse de $3$ modulo $7$ est $5$ (car $15 \equiv 1$ ) : $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ . En remontant : $1 = 97 \times 13 + 35 \times (-36)$ . Donc $35 \times (-36) \equiv 1 \pmod{97}$ : l’inverse de $35$ est $-36 \equiv 61 \pmod{97}$ .

5. $a$ est inversible modulo $n$ exactement lorsque $\gcd(a, n) = 1$ : Bézout fournit $au + nv = 1$ , c’est-à-dire $au \equiv 1$ ; réciproquement, l’existence d’un inverse force le pgcd à diviser $1$ .

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : le code est valide.

7. La somme change de $wd$ avec $1 \leq w \leq 10$ et $1 \leq \abs d \leq 9$ : comme $11$ est premier et ne divise aucun des deux facteurs, il ne peut pas diviser le produit (Théorème 29.11 et Proposition 29.14) : la somme modifiée n’est jamais de nouveau $\equiv 0$ , et toute erreur sur un seul chiffre déclenche l’alarme.

8. Échanger deux chiffres adjacents $a$ et $b$ (de poids $w + 1$ et $w$ ) change la somme de $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ dès que $a \neq b$ : c’est détecté. Le secret est la primalité de $11$ : modulo $10$ , des produits comme $5 \times 2$ s’annulent sans qu’aucun facteur ne soit nul, si bien qu’une erreur de $\pm 2$ sur un poids $5$ (ou une transposition malchanceuse) pourrait passer.

9. Somme pondérée des douze chiffres : $119$ ; la clé doit la compléter jusqu’à un multiple de $10$ , c’est donc $1$ (code complet $978\,2940199\,051$ ). L’EAN rate les transpositions adjacentes vérifiant $2(a - b) \equiv 0 \pmod{10}$ , c’est-à-dire $\abs{a - b} = 5$ : échanger un $2$ et un $7$ , par exemple, passe inaperçu — c’est le prix du sympathique module $10$ .

10. En doublant un chiffre sur deux à partir de la droite et en repliant ( $16 \to 7$ , etc.), la somme vaut $80 \equiv 0 \pmod{10}$ : la carte de test est validée.

11. Avec un module premier, tous les poids sont inversibles, si bien que toutes les erreurs simples et toutes les transpositions adjacentes sont attrapées — c’est le luxe de l’ISBN ; les dispositifs modulo $10$ conservent des chiffres commodes pour l’humain et acceptent un petit angle mort.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , donc $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . Et pourtant $341 = 11 \times 31$ est composé : il passe le test de Fermat en base $2$ sans être premier. Morale : la congruence de Fermat est nécessaire, non suffisante — tester la primalité réclame des outils plus fins (et en reçoit, dans les volumes universitaires).

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ (car $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : $(-2)^7 = -128$ , et $-128 + 4 \times 33 = 4$ : le chiffré se déchiffre en $m = 4$ . La serrure tourne.

16. Modulo $3$ : si $3 \nmid m$ , alors $m^2 \equiv 1$ (Fermat), donc $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; si $3 \mid m$ , les deux membres sont $\equiv 0$ . Modulo $11$ : $m^{10} \equiv 1$ ou bien $11 \mid m$ , et $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Ainsi $3$ et $11$ divisent tous deux $m^{21} - m$ , et comme ils sont premiers entre eux, leur produit $33$ le divise aussi (Gauss) : $m^{21} \equiv m \pmod{33}$ . L’exposant $ed = 21 = 1 + 20k$ a été bâti pour que les deux exposants de Fermat ( $2$ et $10$ , qui divisent $20$ ) disparaissent.

17. Multiplier deux nombres premiers de $300$ chiffres prend une microseconde ; les retrouver à partir de leur produit met en échec tout algorithme connu et tous les ordinateurs du monde — la serrure est une rue à sens unique. (Notre $n = 33$ est cette rue à l’échelle du jouet, parcourable dans les deux sens.)

18. En testant les restes (ou en construisant par Bézout) : $n \equiv 8 \pmod{15}$ , d’où les effectifs $8, 23, 38, 53, \dots$ Unicité modulo $15$ : deux solutions diffèrent d’un multiple de $3$ et d’un multiple de $5$ , donc de $15$ ( $3$ et $5$ étant premiers entre eux, Gauss). Le général qui commande à $1000$ soldats annonce « $8$ » après trois rassemblements rapides — l’antique astuce de comptage.

19. $10 \equiv 1 \pmod 9$ donne $10^k \equiv 1$ , donc $\sum d_k 10^k \equiv \sum d_k$ : un nombre et la somme de ses chiffres sont congrus modulo $9$ (et modulo $3$ ). Et $10 \equiv -1 \pmod{11}$ donne $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : c’est la règle alternée. Deux règles d’enfance, une ligne chacune.

20. Les congruences ont fait des restes une arithmétique (partie I) ; Bézout a frappé les inverses qui résolvent les congruences linéaires et fournissent le $d$ de RSA (questions 4 et 13) ; le petit théorème de Fermat a ouvert et refermé la serrure (questions 15 et 16) ; le recollement de modules premiers entre eux a compté les soldats et achevé la démonstration (questions 16 et 18). Verdict sur Hardy : le plus pur théorème qu’il connût garde aujourd’hui chacun de nos achats — la pureté, avec le temps, est la chose la plus applicable qui soit.

Termes définis dans ce chapitre

Voir les 395 termes du glossaire