---
title: "Arithmétique"
book: "Mathématiques du lycée"
subject: math
language: fr
chapter: 29
exercises: 10
source: https://one-course.com/books/math/2/fr/chapter/29-arithmetique
---

# Chapitre 29 — Arithmétique

L’arithmétique étudie les entiers : [divisibilité](#def-g12-arith-divides), [nombres premiers](#def-g12-arith-prime), 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](https://one-course.com/books/math/2/fr/chapter/1-nombres-et-ensembles-de-nombres#def-g10-numbers-abs) 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](#thm-g12-arith-euclid) 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 nnn).**

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](#thm-g12-arith-euclid) calcule donc $\gcd(a,b)$ : le [pgcd](#def-g12-arith-gcd) est le dernier reste non nul.

**Démonstration.** Tout diviseur commun de $a$ et $b$ divise $r = a - bq$ ([Proposition 29.2](#prop-g12-arith-divprops)), 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](#def-g12-arith-gcd). L’algorithme se termine car les restes forment une [suite](https://one-course.com/books/math/2/fr/chapter/20-suites#def-g12-seq-sequence) strictement [décroissante](https://one-course.com/books/math/2/fr/chapter/3-fonctions#def-g10-functions-variations) 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](#def-g12-arith-gcd) si et seulement s’il existe des entiers $u, v$ avec $au + bv = 1$.

**Démonstration.** Remonter l’[algorithme d’Euclide](#prop-g12-arith-euclidalgo) : 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](#ex-g12-arith-euclidalgo) : $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](#def-g12-arith-prime) ; si $n$ n’est pas [premier](#def-g12-arith-prime), il a un diviseur [premier](#def-g12-arith-prime) $\leq \sqrt n$. Si un [premier](#def-g12-arith-prime) $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](#def-g12-arith-prime) (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](#def-g12-arith-prime).

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

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

Tout entier $n \geq 2$ est un produit de [premiers](#def-g12-arith-prime), 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](#def-g12-arith-prime) 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](#def-g12-arith-prime), avec répétitions autorisées). Par le lemme d’Euclide, $p_1$ divise un certain $q_j$, et étant [premier](#def-g12-arith-prime), $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](#def-g12-arith-prime) 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](#def-g12-arith-congruence) :

$$
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](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/fr/chapter/2-algebre-equations-et-inequations#def-g10-algebra-expand) 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](#thm-g12-arith-euclid) de $2026$ par $17$, et de $-2026$ par $17$.

**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 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](#prop-g12-arith-euclidalgo), calculer $\gcd(1071, 462)$, et trouver des entiers $u, v$ avec $1071u + 462v = \gcd(1071, 462)$.

**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 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 de Exercice 29.5.**

[Divisibilité](#def-g12-arith-divides) par $2$ : parmi $n$ et $n + 1$, l’un est pair. [Divisibilité](#def-g12-arith-divides) 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](#cor-g12-arith-coprimeprod) 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](https://one-course.com/books/math/2/fr/chapter/20-suites#exo-g12-seq-1), est un entier.)

**Exercice 29.6 ★★.**

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

**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](#def-g12-arith-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](https://one-course.com/books/math/2/fr/chapter/2-algebre-equations-et-inequations#def-g10-algebra-equation) diophantienne

$$
17x - 40y = 1,
$$

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

**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](#def-g12-arith-prime) (comparer l’exposant de $2$ des deux côtés de $a^2 = 2b^2$).

**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](#thm-g12-arith-fta). Donc aucune telle fraction n’existe : $\sqrt2 \notin \Q$.

**Exercice 29.9 ★★★.**

Soit $p$ un [nombre premier](#def-g12-arith-prime).

1. 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](https://one-course.com/books/math/2/fr/chapter/27-combinatoire-et-denombrement#exo-g12-comb-7) , et le lemme de Gauss.)
2. 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 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](#def-g12-arith-prime) 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 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](#def-g12-arith-congruence) ([Proposition 29.5](#prop-g12-arith-congops)), les inverses de Bézout ([Théorème 29.10](#thm-g12-arith-bezout)) et le petit théorème de Fermat ([Exercice 29.9](#exo-g12-arith-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](#def-g12-arith-congruence).**

1. Calculer $2026 \bmod 7$ ; puis le chiffre des unités de $7^{100}$ (trouver le cycle des puissances de $7$ modulo $10$ ).
2. Exponentiation rapide ( [Méthode 29.6](#met-g12-arith-powers) ) : calculer $5^{117} \bmod 13$ (partir de $5^2 \equiv -1$ ).
3. Résoudre $3x \equiv 5 \pmod 7$ .
4. Dérouler l’ [algorithme d’Euclide](#prop-g12-arith-euclidalgo) 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$ .
5. É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.**

6. 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$ .
7. 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](#thm-g12-arith-gauss) ) ?
8. 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](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) $10$ ?
9. 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}$ ?)
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$ .
11. En une phrase : qu’est-ce que le [module](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) [premier](#def-g12-arith-prime) a offert à l’ISBN et que l’EAN et Luhn, enchaînés à $10$ , ne peuvent pas avoir ?

**Partie III — La serrure de Fermat.**

12. Un piège avant le trésor : calculer $2^{10} \bmod 341$ , en déduire $2^{340} \bmod 341$ — puis [factoriser](https://one-course.com/books/math/2/fr/chapter/2-algebre-equations-et-inequations#def-g10-algebra-expand) $341$ . Que dit cet exemple (un *[pseudo-premier](#def-g12-arith-prime) de Fermat* ) sur l’emploi du petit théorème de Fermat comme test de primalité ?
13. 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).
14. Chiffrer le message $m = 4$ : calculer $c = m^3 \bmod 33$ .
15. Déchiffrer : calculer $c^d \bmod 33$ (en utilisant $c \equiv -2 \pmod{33}$ ) et retrouver le message.
16. 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](#thm-g12-arith-gauss) recolle les deux [congruences](#def-g12-arith-congruence) ). Où la forme particulière $21 = ed = 1 + 20k$ est-elle intervenue ?
17. 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](https://one-course.com/books/math/2/fr/chapter/2-algebre-equations-et-inequations#def-g10-algebra-expand) .)

**Partie IV — Classiques.**

18. Le vieux dénombrement chinois des soldats (à comparer avec l’ [Exercice 29.10](#exo-g12-arith-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$ .
19. 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.)
20. Pour finir — Hardy face au code-barres : récapituler la trousse du chapitre (arithmétique des [congruences](#def-g12-arith-congruence) , inverses de Bézout, petit théorème de Fermat, recollement de [modules](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) [premiers entre eux](#def-g12-arith-gcd) ) et l’endroit où chacun s’est enclenché dans ce problème ; puis rendre le verdict moderne sur la « non-souillure ».

**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](#def-g12-arith-gcd) à 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](#def-g12-arith-prime) et ne divise aucun des deux facteurs, il ne peut pas diviser le produit ([Théorème 29.11](#thm-g12-arith-gauss) et [Proposition 29.14](#prop-g12-arith-primedivides)) : 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](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) $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](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) [premier](#def-g12-arith-prime), 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](#def-g12-arith-prime). Morale : la [congruence](#def-g12-arith-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](#def-g12-arith-gcd), 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](#def-g12-arith-prime) 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](#def-g12-arith-gcd), 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](#def-g12-arith-congruence) ont fait des restes une arithmétique (partie I) ; Bézout a frappé les inverses qui résolvent les [congruences](#def-g12-arith-congruence) 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](https://one-course.com/books/math/2/fr/chapter/28-nombres-complexes#def-g12-complex-modulus) [premiers entre eux](#def-g12-arith-gcd) 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.