---
title: "Arithmétique des entiers"
book: "Mathématiques universitaires — Licence 1"
subject: math
language: fr
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/fr/chapter/6-arithmetique-des-entiers
---

# Chapitre 6 — Arithmétique des entiers

L’arithmétique — l’étude de la [divisibilité](#def-b1-arith-divides) dans $\Z$ — a été commencée dans le volume du secondaire. Ce chapitre la reconstruit entièrement à partir de la division euclidienne, avec des démonstrations complètes : [plus grand commun diviseur](#thm-b1-arith-gcd) et [algorithme d’Euclide](#met-b1-arith-euclid), théorème de Bézout et [lemme de Gauss](#thm-b1-arith-gauss), [décomposition en facteurs premiers](#thm-b1-arith-fta), et le calcul des [congruences](#def-b1-arith-congruence) jusqu’au [petit théorème de Fermat](#thm-b1-arith-fermat). Au-delà de son charme propre, ce matériau est le modèle que le [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly) imite pour les polynômes.

## 6.1 Divisibilité et division euclidienne

**Définition 6.1 (Divisibilité).**

Pour $a, b \in \Z$, $b$ *divise* $a$ (on note $b \mid
a$) lorsque $a = bq$ pour un certain $q \in \Z$. Conséquences immédiates : si $b \mid a$ et $b \mid a'$, alors $b \mid (ua + va')$ pour tous $u, v \in \Z$ ; si $b \mid a$ et $a \neq 0$, alors $\abs b \leq
\abs a$ ; et $a \mid b$ joint à $b \mid a$ impose $b = \pm a$.

**Théorème 6.2 (Division euclidienne).**

Pour tous $a \in \Z$ et $b \in \N^*$, il existe un unique couple $(q, r)
\in \Z \times \N$ tel que

$$
a = bq + r, \qquad 0 \leq r < b .
$$

**Démonstration.** *Existence.* L’[ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ est une partie non vide de $\N$ (prendre $k = -\abs a$ : $a + b\abs a \geq a +
\abs a \geq 0$). Soit $r = a - bq$ son plus petit élément. Si $r \geq b$, alors $r - b = a - b(q+1)$ serait un élément de $A$ plus petit : contradiction. 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$ : le multiple de $b$ du membre de gauche est nécessairement $0$, donc $q = q'$ et $r = r'$. ∎

**Exemple 6.3 (Numération de position par divisions successives).**

Écrivons $2026$ en base $7$. Divisons de façon répétée par $7$, en conservant les restes :

$$
2026 = 7 \times 289 + 3, \quad
289 = 7 \times 41 + 2, \quad
41 = 7 \times 5 + 6, \quad
5 = 7 \times 0 + 5 .
$$

En lisant les restes du dernier au premier : $2026 =
(5\,6\,2\,3)_7$. Vérification : $5 \times 343 + 6 \times 49 + 2 \times 7
+ 3 = 1715 + 294 + 14 + 3 = 2026$. L’unicité dans la division euclidienne est exactement ce qui rend chaque chiffre *forcé* : à chaque étape, le reste est le seul entier de $\intint06$ [congru](#def-b1-arith-congruence) à la valeur courante modulo $7$, de sorte que l’écriture en base $7$ est unique — fait utilisé silencieusement chaque fois que le devoir maison manipule « les chiffres de $n$ en base $p$ ».

## 6.2 Plus grand commun diviseur

**Théorème 6.4 (Sous-groupes de Z\ZZ ; existence du PGCD).**

1. Tout sous-groupe de $(\Z, +)$ est de la forme $n\Z = \{nk : k  \in \Z\}$ pour un unique $n \in \N$ .
2. Pour $a, b \in \Z$ non tous deux nuls, l’ [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) $a\Z + b\Z = \{au +  bv : u, v \in \Z\}$ est un sous-groupe de $\Z$ , donc égal à $d\,\Z$ pour un unique $d \in \N^*$ . Cet entier $d$ est le *plus grand commun diviseur* $\gcd(a, b)$ : il [divise](#def-b1-arith-divides) $a$ et $b$ , et tout diviseur commun de $a$ et $b$ [divise](#def-b1-arith-divides) $d$ .

**Démonstration.** (1) Soit $H \subseteq \Z$ un sous-groupe (non vide, stable par soustraction ; la définition formelle est au [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures), et seules ces deux propriétés servent). Si $H = \{0\}$, prendre $n = 0$. Sinon, $H$ contient un élément non nul et son opposé, donc un plus petit élément strictement positif $n$. Alors $n\Z \subseteq H$. Pour $x
\in H$, écrivons $x = nq + r$ avec $0 \leq r < n$ ([Théorème 6.2](#thm-b1-arith-division)) ; $r = x - nq \in H$, et la minimalité de $n$ impose $r = 0$ : $x \in n\Z$. Unicité : $n$ est le plus petit élément strictement positif de $n\Z$.

(2) $a\Z + b\Z$ contient $0$ et est stable par soustraction, donc c’est $d\Z$ avec $d \geq 1$ (il contient $a$ ou $b$, non nul). Comme $a, b
\in d\Z$, $d$ [divise](#def-b1-arith-divides) les deux. Et si $c$ [divise](#def-b1-arith-divides) $a$ et $b$, alors $c$ [divise](#def-b1-arith-divides) tout $au + bv$ — en particulier $c \mid d$, puisque $d \in a\Z
+ b\Z$. C’est la propriété annoncée (et elle entraîne $\abs c \leq
d$, de sorte que $d$ mérite le nom de *plus grand* diviseur commun). ∎

**Corollaire 6.5 (Théorème de Bézout).**

Pour $a, b$ non tous deux nuls, il existe $u, v \in \Z$ tels que

$$
au + bv = \gcd(a, b) .
$$

En particulier (cas $\gcd(a,b) = 1$, celui des entiers *premiers entre eux*) : $a$ et $b$ sont [premiers entre eux](#cor-b1-arith-bezout) si et seulement si $au + bv = 1$ admet une solution.

**Démonstration.** $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. Pour l’équivalence : si $\gcd(a,b) = 1$, Bézout fournit la solution ; réciproquement, $au + bv =
1$ oblige tout diviseur commun de $a$ et $b$ à diviser $1$. ∎

**Méthode 6.6 (Algorithme d’Euclide, version étendue).**

Pour calculer $\gcd(a, b)$ ($a > b > 0$) : on divise, $a = bq + r$ ; alors $\gcd(a, b) = \gcd(b, r)$ (les diviseurs communs de $(a,b)$ et de $(b,r)$ coïncident, puisque $r = a - bq$) ; on itère jusqu’à un reste nul ; le dernier reste non nul est le PGCD. En remontant les divisions (ou en maintenant les coefficients au fil de la descente), on obtient un couple de Bézout $(u, v)$.

**Exemple 6.7.**

$\gcd(120, 23)$ : $120 = 5 \times 23 + 5$ ; $23 = 4 \times 5 + 3$ ; $5 =
1\times 3 + 2$ ; $3 = 1 \times 2 + 1$ ; $2 = 2 \times 1 + 0$. Donc $\gcd = 1$. En remontant :

$$
\begin{align*}
1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\
&= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23)
= 47 \times 23 - 9 \times 120 .
\end{align*}
$$

Vérification : $47 \times 23 = 1081$, $9 \times 120 = 1080$.

**Théorème 6.8 (Lemme de Gauss et conséquences).**

Soient $a, b, c \in \Z$.

1. ( [Lemme de Gauss](#thm-b1-arith-gauss) ) Si $a \mid bc$ et $\gcd(a, b) = 1$ , alors $a \mid c$ .
2. Si $a \mid c$ , $b \mid c$ et $\gcd(a,b) = 1$ , alors $ab \mid  c$ .
3. Si $\gcd(a, b) = \gcd(a, c) = 1$ , alors $\gcd(a, bc) = 1$ .

**Démonstration.** (1) Bézout : $au + bv = 1$. Multiplions par $c$ : $acu + bcv = c$. Les deux termes sont divisibles par $a$ (le second parce que $a \mid bc$), donc $a
\mid c$.

(2) Écrivons $c = aq$ ; de $b \mid aq$ et $\gcd(a, b) = 1$, le point (1) donne $b \mid q$, donc $ab \mid aq = c$.

(3) $au + bv = 1$ et $au' + cv' = 1$. Multiplions les deux relations :

$$
1 = (au + bv)(au' + cv')
= a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,
$$

une relation de Bézout entre $a$ et $bc$ : d’après le [Corollaire 6.5](#cor-b1-arith-bezout), $\gcd(a, bc) = 1$. ∎

**Exemple 6.9 (Résolution d’une équation diophantienne linéaire).**

Cherchons tous les $(x, y) \in \Z^2$ tels que $6x + 10y = 4$. D’abord le *test d’existence* : $\gcd(6, 10) = 2$ [divise](#def-b1-arith-divides) $4$, donc il y a des solutions (si le PGCD ne divisait pas le second membre, le premier membre en serait toujours un multiple et il n’y en aurait aucune). Divisons tout par $2$ : $3x + 5y = 2$. Une solution particulière saute aux yeux : $(x_0, y_0) = (-1, 1)$. Pour la solution générale, soustrayons : $3(x + 1) = -5(y - 1)$, donc $3 \mid 5(y-1)$, et le [lemme de Gauss](#thm-b1-arith-gauss) ($\gcd(3,5) = 1$) donne $3 \mid y - 1$ : $y = 1 - 3k$, puis $x = -1 + 5k$. Réciproquement, tout couple de cette forme convient :

$$
(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .
$$

Le schéma est général : une solution particulière plus les multiples entiers de $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — la même structure « particulière plus homogène » qu’au [Chapitre 5](https://one-course.com/books/math/3/fr/chapter/5-equations-differentielles-lineaires#ch-b1-diffeq), le [lemme de Gauss](#thm-b1-arith-gauss) y jouant le rôle de l’unicité.

**Définition 6.10 (Plus petit commun multiple).**

$\operatorname{lcm}(a, b)$ est le générateur dans $\N$ du sous-groupe $a\Z \cap b\Z$ : c’est un multiple commun de $a$ et $b$ qui [divise](#def-b1-arith-divides) tout multiple commun, et pour $a, b \in \N^*$,

$$
\gcd(a,b) \times \operatorname{lcm}(a,b) = ab
\qquad (\text{démonstration à l'} \text{Exercice 6.5}).
$$

**Exemple 6.11 (Les problèmes de coïncidence sont des problèmes de PPCM).**

Deux engrenages en prise ont $84$ et $36$ dents. Au bout de combien de dents de mouvement commun reviennent-ils [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) à leur position initiale ? La configuration se répète lorsque le nombre de dents écoulées est un multiple commun de $84$ et de $36$ ; la première fois, c’est au bout de

$$
\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)}
= \frac{3024}{12} = 252
$$

dents — c’est-à-dire $3$ tours du grand engrenage et $7$ du petit ($252/84$ et $252/36$). Notons la voie pratique : *calculer d’abord le PGCD* (Euclide : $84 = 2\times36 + 12$, $36
= 3\times12$), puis diviser — jamais construire le PPCM en listant les multiples. Toute question de coïncidence périodique (engrenages, alignements planétaires, développements décimaux périodiques qui se rejoignent) se ramène à ce seul calcul.

## 6.3 Nombres premiers

**Définition 6.12.**

Un entier $p \geq 2$ est *premier* lorsque ses seuls diviseurs positifs sont $1$ et $p$. Pour $p$ premier et $a \in \Z$ : ou bien $p \mid a$, ou bien $\gcd(p, a) = 1$. Par conséquent ([Théorème 6.8](#thm-b1-arith-gauss)), le *lemme d’Euclide* est vrai : si $p \mid
ab$, alors $p \mid a$ ou $p \mid b$.

**Remarque 6.13 (Test de primalité par divisions successives).**

Si $n = ab$ avec $2 \leq a \leq b$, alors $a^2 \leq ab = n$, donc $a
\leq \sqrt n$ : un entier composé $n$ a toujours un diviseur [premier](#def-b1-arith-prime) $\leq
\sqrt n$. Ainsi, pour tester si $n$ est [premier](#def-b1-arith-prime), il suffit d’essayer les [nombres premiers](#def-b1-arith-prime) jusqu’à $\sqrt n$. Pour $n = 271$ : $\sqrt{271} < 17$, et $271$ n’est divisible par aucun de $2, 3, 5, 7, 11, 13$ (impair, somme des chiffres $10$, ne se termine ni par $0$ ni par $5$, $271 = 7\cdot38 + 5 =
11\cdot24 + 7 = 13\cdot20 + 11$) : [premier](#def-b1-arith-prime), après six divisions au lieu de deux cents. La barrière $\sqrt n$ est un seuil véritable : la franchir efficacement pour des nombres de cent chiffres exige les tests de primalité modernes issus du [Théorème 6.23](#thm-b1-arith-fermat).

**Théorème 6.14 (Euclide).**

Il existe une infinité de [nombres premiers](#def-b1-arith-prime).

**Démonstration.** Tout entier $n \geq 2$ possède un diviseur [premier](#def-b1-arith-prime) : son plus petit diviseur $\geq 2$ est [premier](#def-b1-arith-prime) (une factorisation propre de celui-ci produirait un diviseur de $n$ plus petit). Supposons maintenant que $p_1, \dots, p_k$ soient tous les [nombres premiers](#def-b1-arith-prime), et posons $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Un certain [premier](#def-b1-arith-prime) $p_i$ [divise](#def-b1-arith-divides) $N$ ; mais $p_i$ [divise](#def-b1-arith-divides) aussi $N - 1 = p_1\cdots p_k$, donc $p_i
\mid 1$ — absurde. ∎

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

Tout entier $n \geq 2$ est un produit de [nombres premiers](#def-b1-arith-prime), et la factorisation

$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\qquad (p_1 < p_2 < \dots < p_k \text{ premiers},\ \alpha_i \in \N^*)
$$

est unique.

**Démonstration.** *Existence* par récurrence forte ([Théorème 1.12](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#thm-b1-logic-induction)) : $n = 2$ est [premier](#def-b1-arith-prime) ; pour $n > 2$, ou bien $n$ est [premier](#def-b1-arith-prime), ou bien $n = ab$ avec $2 \leq a, b < n$, et l’hypothèse de récurrence factorise $a$ et $b$.

*Unicité.* Supposons $p_1 \cdots p_r = q_1 \cdots q_s$ ([nombres premiers](#def-b1-arith-prime) listés avec répétition, disons $r \leq s$), et raisonnons par récurrence sur $r$. Si $r = 0$, le membre de gauche vaut $1$, ce qui force $s = 0$ (un produit non vide de [nombres premiers](#def-b1-arith-prime) dépasse $1$). Pour $r \geq 1$ : le [premier](#def-b1-arith-prime) $p_1$ [divise](#def-b1-arith-divides) $q_1(q_2\cdots q_s)$, donc, par le lemme d’Euclide, ou bien $p_1
\mid q_1$, ou bien $p_1 \mid q_2\cdots q_s$ ; en itérant, $p_1$ [divise](#def-b1-arith-divides) un certain $q_j$. Mais $q_j$ est [premier](#def-b1-arith-prime) et $p_1 \geq 2$ : nécessairement $p_1
= q_j$. Simplifions par ce facteur commun (c’est légitime : $\Z$ est un anneau intègre) pour obtenir

$$
p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s
$$

(le chapeau marquant l’omission), une égalité de produits plus courts ; l’hypothèse de récurrence dit que les deux listes $p_2, \dots, p_r$ et $q_1, \dots, \widehat{q_j}, \dots, q_s$ coïncident à l’ordre près, donc les listes initiales aussi. L’écriture avec exposants regroupe les [premiers](#def-b1-arith-prime) égaux. ∎

**Proposition 6.16 (Valuations).**

Pour $p$ [premier](#def-b1-arith-prime) et $n \in \N^*$, notons $v_p(n)$ l’exposant de $p$ dans la factorisation de $n$ (avec $v_p(n) = 0$ si $p \nmid n$). Alors

$$
v_p(mn) = v_p(m) + v_p(n),
\qquad
m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),
$$

$$
v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr),
\qquad
v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m),
v_p(n)\bigr).
$$

**Démonstration.** La première identité vaut parce que les factorisations se multiplient et que la factorisation de $mn$ est unique. Si $m \mid n$, écrivons $n = mq$ et appliquons-la. Réciproquement, si tous les $v_p(m) \leq v_p(n)$, l’entier $q =
\prod_p p^{\,v_p(n) - v_p(m)}$ vérifie $mq = n$. Formule du PGCD : l’entier $d = \prod p^{\min}$ [divise](#def-b1-arith-divides) les deux d’après le critère, et tout diviseur commun $c$ vérifie $v_p(c) \leq \min$ pour tout $p$, donc $c
\mid d$ ; même raisonnement pour le PPCM avec le $\max$. ∎

**Exemple 6.17 (Carrés et cubes vus par les valuations).**

Un entier $n \geq 1$ est un carré parfait si et seulement si tous les $v_p(n)$ sont pairs (si $n = m^2$, alors $v_p(n) = 2v_p(m)$ ; réciproquement, on divise par deux chaque exposant). De même pour les cubes avec des multiples de $3$. Ainsi $21168 = 2^4 \times 3^3 \times 7^2$ n’est pas un carré ($v_3 = 3$ est impair) ni un cube ($v_2 = 4$) ; le plus petit entier $m > 0$ tel que $21168\,m$ *soit* un cube s’obtient en complétant chaque exposant jusqu’au multiple de $3$ suivant :

$$
m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28,
\qquad
21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3
= 84^3 .
$$

L’idée à retenir : les questions multiplicatives (carrés, cubes, diviseurs, PGCD, PPCM) deviennent des questions *coordonnée par coordonnée* sur les vecteurs d’exposants $(v_2, v_3, v_5, \dots)$ — l’unicité de la factorisation, c’est exactement l’[assertion](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-statement) que ces coordonnées existent et sont bien définies.

## 6.4 Congruences

**Définition 6.18.**

Pour $n \in \N^*$ : $a \equiv b \pmod n$ lorsque $n \mid
a - b$. C’est une [relation d’équivalence](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-equiv) compatible avec l’addition et la multiplication : si $a \equiv b$ et $a' \equiv b'$ (mod $n$), alors $a + a' \equiv b + b'$, $aa' \equiv bb'$, et $a^k \equiv b^k$ pour $k \in \N$.

**Exemple 6.19 (La preuve par neuf).**

La compatibilité avec $+$ et $\times$ est un procédé de vérification aussi vieux que le commerce. Comme $10 \equiv 1 \pmod 9$, tout entier est [congru](#def-b1-arith-congruence) modulo $9$ à la somme de ses chiffres (démontré à l’[Exercice 6.2](#exo-b1-arith-2)). Pour vérifier l’affirmation $1234 \times 567 =
699\,678$ : les sommes des chiffres donnent $1234 \equiv 1$ et $567 \equiv 18
\equiv 0 \pmod 9$, donc le produit doit être $\equiv 1 \times 0 =
0$ ; et en effet $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. La vérification passe (et le produit est en fait correct). Si quelqu’un avait annoncé $699\,478$, la somme des chiffres $43 \equiv 7 \not\equiv 0$ le confondrait aussitôt. Le test est unilatéral — il attrape une erreur sauf si l’erreur est elle-même un multiple de $9$ — ce qui est exactement, en miniature, la leçon des [pseudo-premiers](#def-b1-arith-prime) de l’[Exemple 6.24](#ex-b1-arith-pseudoprime) : les vérifications par [congruence](#def-b1-arith-congruence) réfutent, elles ne certifient pas.

**Proposition 6.20 (Inversibilité modulo nnn).**

$a$ est *inversible modulo $n$* (c’est-à-dire $ab \equiv 1 \pmod n$ pour un certain $b$) si et seulement si $\gcd(a, n) = 1$. L’inverse est alors unique modulo $n$ et se calcule par l’[algorithme d’Euclide](#met-b1-arith-euclid) étendu.

**Démonstration.** $ab \equiv 1 \pmod n$ signifie $ab + nk = 1$ pour un certain $k$ : une relation de Bézout, qui existe si et seulement si $\gcd(a,n) = 1$ ([Corollaire 6.5](#cor-b1-arith-bezout)). Unicité : si $ab \equiv ab' \equiv 1$, alors $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎

**Exemple 6.21 (Inverser 777 modulo 262626).**

Comme $\gcd(7, 26) = 1$, la classe de $7$ est inversible modulo $26$. Euclide étendu :

$$
26 = 3 \times 7 + 5, \qquad
7 = 1 \times 5 + 2, \qquad
5 = 2 \times 2 + 1 ,
$$

puis en remontant :

$$
1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7
= 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .
$$

Donc $7 \times (-11) \equiv 1 \pmod{26}$, c’est-à-dire $7^{-1} \equiv
-11 \equiv 15 \pmod{26}$ ; vérification : $7 \times 15 = 105 = 4 \times 26
+ 1$. Une fois l’inverse en main, toute [congruence](#def-b1-arith-congruence) $7x \equiv c
\pmod{26}$ se résout en une multiplication : $x \equiv 15c$. Cette inversion mécanique est le cheval de trait de l’arithmétique modulaire — et des protocoles à clé publique évoqués à la [Remarque 6.27](#rem-b1-arith-whereused), où les [modules](https://one-course.com/books/math/3/fr/chapter/3-nombres-complexes#def-b1-complex-field) ont des centaines de chiffres mais où l’algorithme est exactement celui-ci.

**Exemple 6.22 (Quand le coefficient n’est pas inversible).**

Résolvons $12x \equiv 8 \pmod{20}$. Ici $\gcd(12, 20) = 4$, donc $12$ n’est pas inversible modulo $20$ — mais l’équation reste traitable. La [congruence](#def-b1-arith-congruence) dit que $20 \mid 12x - 8$ ; en divisant toute la relation par $4$ (diviseur des trois ingrédients), elle est équivalente à $5 \mid 3x - 2$, c’est-à-dire

$$
3x \equiv 2 \pmod 5 .
$$

Or $\gcd(3, 5) = 1$ et $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 =
6 \equiv 1$), donc $x \equiv 4 \pmod 5$ : les solutions sont $x
\equiv 4, 9, 14, 19 \pmod{20}$ — *quatre* classes modulo $20$, en accord avec le PGCD. (Si le second membre n’avait pas été divisible par $4$, par exemple $12x \equiv 6 \pmod{20}$, il n’y aurait aucune solution : le premier membre est toujours $\equiv 0 \pmod 4$.) Forme générale : $ax
\equiv b \pmod n$ est résoluble si et seulement si $\gcd(a, n) \mid b$, et a alors exactement $\gcd(a, n)$ classes de solutions — on divise tout par le PGCD et on inverse.

**Théorème 6.23 (Petit théorème de Fermat).**

Soit $p$ un [nombre premier](#def-b1-arith-prime). Pour tout $a \in \Z$ :

$$
a^p \equiv a \pmod p,
$$

et si $p \nmid a$, alors $a^{p-1} \equiv 1 \pmod
p$.

**Démonstration.** D’abord, pour $1 \leq k \leq p - 1$, le [coefficient binomial](https://one-course.com/books/math/3/fr/chapter/2-denombrement#def-b1-counting-objects) $\binom pk
= \frac{p!}{k!(p-k)!}$ est divisible par $p$ : en effet $k!\,(p-k)!\,
\binom pk = p!$ et $p$ [divise](#def-b1-arith-divides) $p!$ tout en étant premier avec $k!(p-k)!$ (tous les facteurs sont $< p$), donc le [lemme de Gauss](#thm-b1-arith-gauss) donne $p \mid \binom pk$.

Démontrons maintenant $a^p \equiv a$ pour $a \in \N$ par récurrence. C’est vrai pour $a =
0$. Si $a^p \equiv a$, alors la formule du binôme donne

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

tous les termes intermédiaires s’annulant modulo $p$. Pour $a < 0$, on applique le résultat à $-a$ et on sépare $p = 2$ (où $x \equiv -x$) du cas $p$ impair (où $(-a)^p = -a^p$). Enfin, si $p \nmid a$, on multiplie $a^p \equiv a$ par un inverse de $a$ modulo $p$ ([Proposition 6.20](#prop-b1-arith-invmod)). ∎

**Exemple 6.24 (La réciproque de Fermat est fausse : 341341341).**

Le [petit théorème de Fermat](#thm-b1-arith-fermat) fournit un test de *non-primalité* bon marché : si $a^{n-1} \not\equiv 1 \pmod n$ pour un certain $a$ premier avec $n$, alors $n$ n’est pas [premier](#def-b1-arith-prime). Le test pourrait-il aussi certifier la primalité ? Non : prenons $n = 341 = 11 \times 31$, composé, et $a = 2$. Comme $2^{10} = 1024 = 3 \times 341 + 1$,

$$
2^{10} \equiv 1 \pmod{341}
\qquad\Longrightarrow\qquad
2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :
$$

le nombre composé $341$ passe le test de Fermat en base $2$ (c’est le plus petit *[pseudo-premier](#def-b1-arith-prime)* de ce genre). La base $3$ le démasque ($3^{340} \not\equiv 1$), et les tests de primalité pratiques exécutent donc le test sur plusieurs bases, avec des raffinements — les versions industrielles de cette idée sont celles qui certifient les grands [nombres premiers](#def-b1-arith-prime) de la [Remarque 6.27](#rem-b1-arith-whereused). Morale : une implication et sa réciproque mènent des vies séparées ([Remarque 1.10](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#rem-b1-logic-pitfalls)), même pour les théorèmes.

**Exemple 6.25 (Calculs pratiques de congruences).**

Quel est le reste de $7^{2026}$ modulo $11$ ? D’après Fermat, $7^{10}
\equiv 1 \pmod{11}$. Comme $2026 = 10 \times 202 + 6$ :

$$
7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4
\pmod{11}.
$$

Le reste vaut $4$. La stratégie : réduire l’exposant modulo l’ordre fourni par Fermat, puis réduire les puissances intermédiaires à chaque étape.

**Remarque 6.26 (Pièges classiques en arithmétique).**

1. *Diviser une [congruence](#def-b1-arith-congruence).* De $ac \equiv bc \pmod n$ on ne peut *pas* conclure $a \equiv b$ sauf si $\gcd(c,  n) = 1$ : $6 \equiv 2 \pmod 4$ mais $3 \not\equiv 1 \pmod  4$ . La règle générale correcte [divise](#def-b1-arith-divides) aussi le [module](https://one-course.com/books/math/3/fr/chapter/3-nombres-complexes#def-b1-complex-field) : $ac  \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
2. *Mésusage du lemme d’Euclide.* $a \mid bc$ entraîne $a  \mid b$ ou $a \mid c$ seulement si $a$ est *[premier](#def-b1-arith-prime)* (ou premier avec l’un des facteurs) : $6 \mid 4 \times 9$ alors que $6$ ne [divise](#def-b1-arith-divides) aucun des deux facteurs.
3. *« [Premiers entre eux](#cor-b1-arith-bezout) » est une relation, pas une propriété.* « $8$ et $9$ sont [premiers entre eux](#cor-b1-arith-bezout) » est vrai bien qu’aucun des deux ne soit [premier](#def-b1-arith-prime) ; « [premiers entre eux](#cor-b1-arith-bezout) deux à deux » est plus fort que « [premiers entre eux](#cor-b1-arith-bezout) dans leur ensemble » ( $\gcd(6, 10, 15) = 1$ mais aucune paire n’est formée d’entiers [premiers entre eux](#cor-b1-arith-bezout) ).
4. *Les exposants ne vivent pas modulo $n$.* Dans $a^k \bmod n$ , l’exposant ne peut être réduit que modulo l’ *ordre* de $a$ (par exemple $p - 1$ quand Fermat s’applique), jamais modulo $n$ : $2^{10} \bmod 11$ vaut $1$ , et non $2^{10 \bmod  11} = 2^{10}$ — la réduction qui marche est celle qu’effectue l’ [Exemple 6.25](#ex-b1-arith-congruences) .

**Remarque 6.27 (Où ce chapitre est utilisé).**

Ce chapitre est un modèle autant qu’une boîte à outils. Toute la chaîne — division euclidienne, PGCD, Bézout, Gauss, unicité de la factorisation — est rejouée mot pour mot pour les polynômes au [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly), où le « degré » joue le rôle de la valeur absolue ; comparer les deux chapitres côte à côte est la meilleure façon de comprendre les deux. Le calcul des [congruences](#def-b1-arith-congruence) devient l’anneau $\Z/n\Z$ au [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures), dont les éléments inversibles ([Proposition 6.20](#prop-b1-arith-invmod)) forment le premier exemple non trivial de groupe des unités. Les valuations reviennent dans le devoir maison ci-dessous ([formule de Legendre](#pb-b1-arith-1)) et alimentent les démonstrations d’irrationalité du [Chapitre 10](https://one-course.com/books/math/3/fr/chapter/10-nombres-reels#ch-b1-reals). Au-delà de ce volume, l’inversion de Bézout modulo $n$ est le moteur de la cryptographie à clé publique, et le [petit théorème de Fermat](#thm-b1-arith-fermat) est l’ancêtre des tests de primalité qui certifient les grands [nombres premiers](#def-b1-arith-prime) qu’on y utilise.

**Remarque 6.28 (Interlude : Z\ZZ comme modèle).**

Prenons du recul par rapport aux théorèmes individuels et observons l’architecture du chapitre : un outil (la division euclidienne) a produit une classification (les sous-groupes $n\Z$), qui a produit un théorème d’existence (PGCD, Bézout), qui a produit un calcul de [divisibilité](#def-b1-arith-divides) (Gauss), qui a produit l’unicité de la factorisation — chaque étage ne reposant que sur celui du dessous. Le même bâtiment sera élevé deux fois encore dans ce volume, sur des rez-de-chaussée différents : au [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly), où la division selon le degré remplace la division selon la taille et où tout l’étage supérieur se répète *mot pour mot* ; et, en miniature, à l’intérieur de chaque $\Z/n\Z$ du [Chapitre 7](https://one-course.com/books/math/3/fr/chapter/7-structures-algebriques#ch-b1-structures), où les questions d’inversibilité (la [Proposition 6.20](#prop-b1-arith-invmod) de ce chapitre) deviennent des énoncés structurels sur les anneaux et les corps. Reconnaître dans un argument « l’argument dans $\Z$, transplanté » est la façon la plus rapide d’apprendre ces chapitres — et le premier avant-goût de l’habitude centrale de l’algèbre : démontrer des théorèmes sur des *axiomes* plutôt que sur des objets.

![Les lignes 0 à 7 du triangle de Pascal, les coefficients impairs étant coloriés : la ligne n en contient 2s_2(n), où s_2(n) est le nombre de uns dans l’écriture binaire de n (lignes 1, 2, 4 : deux coefficients impairs ; ligne 7 = (111)_2 : tous les huit). Le motif autosimilaire — chaque « triangle d’impairs » engendre deux copies de lui-même — est le théorème de Kummer sous forme d’image, démontré dans le devoir maison ci-dessous.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

*Les lignes $0$ à $7$ du triangle de Pascal, les coefficients *impairs* étant coloriés : la ligne $n$ en contient $2^{s_2(n)}$, où $s_2(n)$ est le nombre de uns dans l’écriture binaire de $n$ (lignes $1, 2, 4$ : deux coefficients impairs ; ligne $7 = (111)_2$ : tous les huit). Le motif autosimilaire — chaque « triangle d’impairs » engendre deux copies de lui-même — est le [théorème de Kummer](#pb-b1-arith-1) sous forme d’image, démontré dans le devoir maison ci-dessous.*

## 6.5 Exercices

**Exercice 6.1 ★.**

Calculez $\gcd(1\,001, 777)$ par l’[algorithme d’Euclide](#met-b1-arith-euclid), ainsi qu’un couple de Bézout associé.

**Solution de Exercice 6.1.**

$1001 = 1 \times 777 + 224$ ; $777 = 3 \times 224 + 105$ ; $224 = 2
\times 105 + 14$ ; $105 = 7 \times 14 + 7$ ; $14 = 2 \times 7 + 0$. Donc $\gcd(1001, 777) = 7$. En remontant :

$$
7 = 105 - 7 \times 14
= 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224
$$

$$
= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224
= 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .
$$

Vérification : $67 \times 777 = 52\,059$ et $52 \times 1001 = 52\,052$ ; différence $7$. Couple de Bézout : $(u, v) = (-52, 67)$ pour $1001u + 777v =
7$.

**Exercice 6.2 ★.**

Démontrez les critères de [divisibilité](#def-b1-arith-divides) en base $10$ : un entier est [congru](#def-b1-arith-congruence) modulo $9$ à la somme de ses chiffres, et modulo $11$ à la somme alternée de ses chiffres. Que valent $123\,456\,789$ modulo $9$ et modulo $11$ ?

**Solution de Exercice 6.2.**

Comme $10 \equiv 1 \pmod 9$ : $10^k \equiv 1$, donc $\sum_k d_k 10^k
\equiv \sum_k d_k \pmod 9$. Comme $10 \equiv -1 \pmod{11}$ : $10^k
\equiv (-1)^k$, donc l’entier est [congru](#def-b1-arith-congruence) à la somme alternée $\sum_k (-1)^k d_k$ modulo $11$ (en partant du chiffre des *unités* avec le signe $+$).

$123\,456\,789$ : somme des chiffres $45 \equiv 0 \pmod 9$. Somme alternée à partir des unités : $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$, donc le nombre est $\equiv 5 \pmod{11}$.

**Exercice 6.3 ★.**

Résolvez dans $\Z$ : $91x \equiv 1 \pmod{237}$ *(Euclide étendu)*.

**Solution de Exercice 6.3.**

Euclide : $237 = 2 \times 91 + 55$ ; $91 = 1 \times 55 + 36$ ; $55 = 1
\times 36 + 19$ ; $36 = 1 \times 19 + 17$ ; $19 = 1 \times 17 + 2$ ; $17
= 8 \times 2 + 1$. En remontant :

$$
1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19
= 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19
$$

$$
= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55
= 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55
$$

$$
= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.
$$

Donc $91 \times 112 \equiv 1 \pmod{237}$ : les solutions sont $x \equiv
112 \pmod{237}$. (Vérification : $91 \times 112 = 10\,192 = 43 \times 237 +
1$.)

**Exercice 6.4 ★.**

Trouvez tous les couples $(x, y) \in \Z^2$ tels que $17x + 39y = 1$ ; puis tous les couples tels que $17 x + 39 y = 5$.

**Solution de Exercice 6.4.**

$\gcd(17, 39) = 1$ : Euclide donne $39 = 2\times 17 + 5$, $17 = 3\times
5 + 2$, $5 = 2\times 2 + 1$, et en remontant

$$
1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17
= 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .
$$

Solution particulière $(x_0, y_0) = (-16, 7)$. Solution générale de l’équation homogène $17x + 39y = 0$ : $x = 39k$, $y = -17k$ (car $17 \mid 39y$ et $\gcd(17,39) = 1$ imposent $17 \mid y$ — [lemme de Gauss](#thm-b1-arith-gauss)). D’où

$$
(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .
$$

Pour le second membre $5$, on multiplie la solution particulière par $5$ : $(x, y) = (-80 + 39k,\; 35 - 17k)$, $k \in \Z$.

**Exercice 6.5 ★★.**

Démontrez que, pour $a, b \in \N^*$ : $\gcd(a,b) \times
\operatorname{lcm}(a,b) = ab$. *(Utilisez les formules de valuation de la [Proposition 6.16](#prop-b1-arith-valuation) et $\min(\alpha,\beta) +
\max(\alpha,\beta) = \alpha + \beta$.)*

**Solution de Exercice 6.5.**

Pour tout [nombre premier](#def-b1-arith-prime) $p$, avec $\alpha = v_p(a)$ et $\beta = v_p(b)$ :

$$
v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr)
= \min(\alpha, \beta) + \max(\alpha, \beta)
= \alpha + \beta = v_p(ab) .
$$

Deux entiers strictement positifs ayant la même valuation en tout [nombre premier](#def-b1-arith-prime) sont égaux ([Proposition 6.16](#prop-b1-arith-valuation)), donc $\gcd(a,b)\operatorname{lcm}(a,b)
= ab$.

**Exercice 6.6 ★★.**

Soient $a = 2^{10} \times 3^4 \times 5^2$ et $b = 2^6 \times 3^7 \times
7$. Calculez $\gcd(a, b)$, $\operatorname{lcm}(a,b)$, et le nombre de diviseurs positifs de $a$. *(Démontrez la formule du nombre de diviseurs $\prod_i (\alpha_i + 1)$.)*

**Solution de Exercice 6.6.**

Valuations : $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)}
7^{\min(0,1)} = 2^6\, 3^4 = 5184$ ; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$.

Nombre de diviseurs : un diviseur positif de $n = \prod p_i^{\alpha_i}$ est exactement un choix $\prod p_i^{\beta_i}$ avec $0 \leq \beta_i \leq
\alpha_i$ ([Proposition 6.16](#prop-b1-arith-valuation)) ; les choix sont indépendants, donc il y a $\prod_i (\alpha_i + 1)$ diviseurs. Pour $a$ : $(10+1)(4+1)(2+1) = 165$.

**Exercice 6.7 ★★.**

Démontrez que $\sqrt p$ est irrationnel pour tout [nombre premier](#def-b1-arith-prime) $p$, en utilisant les valuations : comparez $v_p$ des deux membres de $p q^2 = r^2$.

**Solution de Exercice 6.7.**

Supposons $\sqrt p = \frac rq$ avec $r, q \in \N^*$, c’est-à-dire $p q^2 =
r^2$. Appliquons $v_p$ : $v_p(pq^2) = 1 + 2v_p(q)$ est impair, tandis que $v_p(r^2)
= 2 v_p(r)$ est pair. Un entier ne peut avoir à la fois une valuation $p$-adique paire et impaire : contradiction. Donc $\sqrt p \notin \Q$.

**Exercice 6.8 ★★.**

(Problème des restes chinois) Trouvez tous les entiers $x$ tels que

$$
x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.
$$

Démontrez au passage que, pour $m, n$ [premiers entre eux](#cor-b1-arith-bezout), le couple de [congruences](#def-b1-arith-congruence) $x \equiv a \ (m)$, $x \equiv b\ (n)$ a toujours une solution, unique modulo $mn$.

**Solution de Exercice 6.8.**

*Fait général.* Avec $\gcd(m,n) = 1$, Bézout donne $mu + nv = 1$. Posons $x_0 = b\,mu + a\,nv$. Alors $x_0 \equiv a\,nv \equiv a(1 - mu)
\equiv a \pmod m$ et de même $x_0 \equiv b \pmod n$ : existence. Si $x$ et $x'$ sont deux solutions, $m$ et $n$ [divisent](#def-b1-arith-divides) $x - x'$, donc $mn \mid x - x'$ ([Théorème 6.8](#thm-b1-arith-gauss) (2)) : unicité modulo $mn$.

*Numériquement :* $m = 7$, $n = 11$ : $7 \times (-3) + 11 \times 2 =
1$. Donc $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 +
44 = -61 \equiv 16 \pmod{77}$. Vérification : $16 = 2\times 7 + 2 \equiv 2
\pmod 7$ ; $16 = 11 + 5 \equiv 5 \pmod{11}$. Solutions : $x \equiv 16
\pmod{77}$.

**Exercice 6.9 ★★.**

Calculez $3^{1000}$ modulo $7$, ainsi que les deux derniers chiffres décimaux de $7^{100}$ *(modulo $100 = 4 \times 25$ : utilisez l’[Exercice 6.8](#exo-b1-arith-8))*.

**Solution de Exercice 6.9.**

Modulo $7$ : Fermat donne $3^6 \equiv 1$, et $1000 = 6 \times 166 + 4$, donc $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Deux derniers chiffres de $7^{100}$ : travaillons modulo $4$ et modulo $25$. Modulo $4$ : $7
\equiv -1$, donc $7^{100} \equiv 1$. Modulo $25$ : $7^2 = 49 \equiv -1$, donc $7^4 \equiv 1$ et $7^{100} = (7^4)^{25} \equiv 1$. D’après le [théorème des restes chinois](#rem-b1-arith-interlude) ([Exercice 6.8](#exo-b1-arith-8)), $7^{100} \equiv 1
\pmod{100}$ : les deux derniers chiffres sont $01$.

**Exercice 6.10 ★★★.**

Pour $m, n \in \N^*$, démontrez que $\gcd(2^m - 1,\, 2^n - 1) =
2^{\gcd(m,n)} - 1$. *Indication : montrez d’abord que le reste de $2^m
- 1$ modulo $2^n - 1$ est $2^r - 1$, où $r$ est le reste de $m$ modulo $n$ ; puis suivez l’[algorithme d’Euclide](#met-b1-arith-euclid).*

**Solution de Exercice 6.10.**

Écrivons $m = nq + r$, $0 \leq r < n$. Alors

$$
2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,
$$

et $2^n - 1$ [divise](#def-b1-arith-divides) $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots +
1)$. Donc, modulo $2^n - 1$, $\;2^m - 1 \equiv 2^r - 1$, et comme $0 \leq
2^r - 1 < 2^n - 1$, c’est bien *le* reste euclidien.

Par conséquent, l’[algorithme d’Euclide](#met-b1-arith-euclid) appliqué au couple $(2^m - 1, 2^n - 1)$ reproduit, exposant par exposant, l’algorithme appliqué à $(m, n)$ : chaque étape de division remplace $(m, n)$ par $(n, r)$ à l’étage du haut et $(2^m - 1,
2^n - 1)$ par $(2^n - 1, 2^r - 1)$ à l’étage du bas. En haut, l’algorithme se termine sur $\gcd(m,n)$, donc en bas il se termine sur $2^{\gcd(m,n)} - 1$.

**Exercice 6.11 ★★★.**

(Théorème de Wilson) Soit $p$ un [nombre premier](#def-b1-arith-prime). Démontrez que

$$
(p-1)! \equiv -1 \pmod p ,
$$

en appariant chaque facteur de $(p-1)!$ avec son inverse modulo $p$ et en identifiant les facteurs appariés à eux-mêmes (résolvez d’abord $x^2 \equiv 1 \pmod p$). Vérifiez la réciproque : si $n \geq 2$ n’est pas [premier](#def-b1-arith-prime), alors $(n-1)!
\not\equiv -1 \pmod n$.

**Solution de Exercice 6.11.**

Résolvons d’abord $x^2 \equiv 1 \pmod p$ : $p \mid (x-1)(x+1)$, donc, par le lemme d’Euclide, $x \equiv 1$ ou $x \equiv -1 \pmod p$.

Dans le produit $(p-1)! = 1 \times 2 \times \dots \times (p-1)$, tout facteur $a$ est inversible modulo $p$, et son inverse $a^{-1}$ est encore l’un des facteurs ([Proposition 6.20](#prop-b1-arith-invmod)). Apparions chaque $a$ avec $a^{-1}$ : les paires ont pour produit $1$, sauf les facteurs appariés à eux-mêmes ($a = a^{-1}$, c’est-à-dire $a^2 \equiv 1$) qui restent seuls — et ce sont exactement $1$ et $p - 1$. D’où

$$
(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .
$$

(Pour $p = 2$ : $1! = 1 \equiv -1 \pmod 2$ ; l’argument d’appariement dégénère mais le résultat subsiste.)

*Réciproque.* Soit $n \geq 2$ composé, $n = ab$ avec $1 < a
\leq b < n$. Si $a < b$, tous deux apparaissent comme facteurs distincts de $(n-1)!$, donc $n \mid (n-1)!$ et $(n-1)! \equiv 0 \not\equiv -1$. Si $a = b$ (c’est-à-dire $n = a^2$) : pour $a \geq 3$, $a$ et $2a$ sont tous deux $< n$, donc $n = a^2 \mid a \times 2a \mid (n-1)!$, même conclusion ; pour $n = 4$, $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$.

**Exercice 6.12 ★★★.**

(Nombres de Fermat) Pour $n \in \N$, posons $F_n = 2^{2^n} + 1$.

1. Démontrez que $F_0 F_1 \cdots F_{n-1} = F_n - 2$ pour $n \geq  1$ (récurrence).
2. Déduisez-en que les nombres de Fermat sont deux à deux [premiers entre eux](#cor-b1-arith-bezout) .
3. Déduisez-en une seconde démonstration, indépendante du [Théorème 6.14](#thm-b1-arith-euclidprimes) , du fait qu’il existe une infinité de [nombres premiers](#def-b1-arith-prime) .

**Solution de Exercice 6.12.**

1. Récurrence. Pour $n = 1$ : $F_0 = 3 = F_1 - 2 = 5 - 2$. En supposant $F_0\cdots F_{n-1} = F_n - 2$ : $$F_0 \cdots F_n = (F_n - 2)F_n  = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr)  = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$
2. Soient $m < n$ et $d = \gcd(F_m, F_n)$ . D’après (1), $F_m$ [divise](#def-b1-arith-divides) $F_n - 2$ , donc $d$ [divise](#def-b1-arith-divides) à la fois $F_n$ et $F_n -  2$ , et [divise](#def-b1-arith-divides) donc $2$ . Mais tout nombre de Fermat est impair, donc $d = 1$ .
3. Chaque $F_n \geq 3$ a un diviseur [premier](#def-b1-arith-prime) $p_n$ (première étape du [Théorème 6.14](#thm-b1-arith-euclidprimes) ). Si $m  \neq n$ , alors $p_m \neq p_n$ , car un [premier](#def-b1-arith-prime) commun diviserait $\gcd(F_m, F_n) = 1$ . L’ [application](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-map) $n \mapsto p_n$ est donc [injective](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-inj) de $\N$ dans l’ [ensemble](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-sets) des [nombres premiers](#def-b1-arith-prime) : il existe une infinité de [nombres premiers](#def-b1-arith-prime) .

## 6.6 Problème : la formule de Legendre et les retenues de Kummer

**Problème 6.1.**

Par combien de zéros se termine l’écriture décimale de $1000!$ — et, plus profondément, quelle est la puissance exacte d’un [nombre premier](#def-b1-arith-prime) $p$ qui [divise](#def-b1-arith-divides) $n!$, ou qui [divise](#def-b1-arith-divides) un [coefficient binomial](https://one-course.com/books/math/3/fr/chapter/2-denombrement#def-b1-counting-objects) ? Les réponses complètes sont deux joyaux de l’arithmétique élémentaire : la *formule de Legendre* $v_p(n!) = \sum_{k\geq1}
\lfloor n/p^k \rfloor$, avec son avatar en chiffres $v_p(n!) = \frac{n
- s_p(n)}{p-1}$, et le *théorème de Kummer* : $v_p\binom{m+n}m$ compte les *retenues* de l’addition de $m$ et $n$ en base $p$. Ce problème démontre les deux, les confronte numériquement l’un à l’autre, et en récolte les conséquences classiques — zéros terminaux, parité du triangle de Pascal, et une première minoration en direction du théorème des [nombres premiers](#def-b1-arith-prime). Dans tout ce qui suit, $p$ est un [nombre premier](#def-b1-arith-prime), $\floor{x}$ est la partie entière, et $s_p(n)$ désigne la somme des chiffres de $n$ écrit en base $p$.

**Partie I — Parties entières, valuations et [formule de Legendre](#pb-b1-arith-1).**

1. Échauffement : calculez $10!$ et lisez-y son nombre de zéros terminaux ; calculez $v_2(10!)$ et $v_5(10!)$ directement à partir de la factorisation de chacun des facteurs $1, 2, \dots, 10$ .
2. Démontrez que, pour $x \in \R$ et $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor =  \lfloor x/n \rfloor$ .
3. Démontrez que $v_p(a + b) \geq \min\bigl(v_p(a),  v_p(b)\bigr)$ pour tous $a, b \in \N^*$ , avec égalité dès que $v_p(a) \neq v_p(b)$ .
4. Montrez que le nombre de multiples de $m$ dans $\intint1n$ est $\lfloor n/m \rfloor$ .
5. Démontrez la *[formule de Legendre](#pb-b1-arith-1)* : pour tout $n \in \N^*$, $$v_p(n!) = \sum_{k=1}^{\infty}  \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (somme finie : les termes s’annulent dès que $p^k > n$). *Comptez, pour chaque $k$, les facteurs de $\intint1n$ divisibles par $p^k$ : chacun contribue exactement pour une unité par niveau qu’il atteint.*

**Partie II — La forme en chiffres et les zéros terminaux.**

6. Calculez $v_5(1000!)$ et $v_2(1000!)$ , et concluez : par combien de zéros se termine $1000!$ ?
7. Démontrez la forme en chiffres de la [formule de Legendre](#pb-b1-arith-1) : en écrivant $n =  \sum_i a_i p^i$ en base $p$, $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$
8. Deux conséquences pour $p = 2$ : montrez que $2^n$ ne [divise](#def-b1-arith-divides) jamais $n!$ , et que $2^{n-1}$ [divise](#def-b1-arith-divides) $n!$ exactement lorsque $n$ est une puissance de $2$ .
9. Encadrez le défaut : montrez que $\frac n{p-1} - \log_p(n) - 1 \leq  v_p(n!) < \frac n{p-1}$ , de sorte que $\frac{v_p(n!)}{n} \to  \frac1{p-1}$ : à la longue, il s’accumule une proportion $\frac1{p-1}$ de facteur $p$ par unité.
10. Soit $Z(n) = v_5(n!)$ le nombre de zéros terminaux de $n!$ . Montrez que $Z(n) - Z(n-1) = v_5(n)$ , déduisez-en que $Z$ saute entièrement la valeur $5$ (calculez $Z(24)$ et $Z(25)$ ), et démontrez qu’aucune factorielle ne se termine par exactement cinq zéros.

**Partie III — Le [théorème de Kummer](#pb-b1-arith-1).**

11. Démontrez que $\lfloor x + y \rfloor - \lfloor x \rfloor -  \lfloor y \rfloor \in \{0, 1\}$ pour tous $x, y \in \R$, et déduisez de la [formule de Legendre](#pb-b1-arith-1) que $$v_p\binom{m+n}m  = \sum_{k\geq1}\Bigl(  \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ somme de termes valant chacun $0$ ou $1$.
12. Démontrez le *[théorème de Kummer](#pb-b1-arith-1)* : le $k$ -ième terme de cette somme vaut $1$ exactement lorsque l’addition de $m$ et $n$ en base $p$ produit une retenue en position $k$ ; donc $v_p\binom{m+n}m$ est le nombre total de retenues. *(Écrivez $m = p^km_1 + m_0$ et $n = p^kn_1 + n_0$ avec $0 \leq m_0, n_0 < p^k$ et examinez $\lfloor (m_0 +  n_0)/p^k \rfloor$.)*
13. Déduisez-en que, pour $0 < j < p^k$ : $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ en comptant les retenues dans l’addition $j + (p^k - j)$. (En particulier $p \mid \binom p j$ pour $0 < j < p$ : l’étape clé du [Théorème 6.23](#thm-b1-arith-fermat), retrouvée.)
14. Démontrez que $v_2\binom{2n}n = s_2(n)$ . Déduisez-en que le [coefficient binomial](https://one-course.com/books/math/3/fr/chapter/2-denombrement#def-b1-counting-objects) central est toujours pair, et que $\binom{2n}n \equiv 2 \pmod 4$ exactement lorsque $n$ est une puissance de $2$ .
15. Montrez, à l’aide de l’identité de Vandermonde ( [Exercice 2.7](https://one-course.com/books/math/3/fr/chapter/2-denombrement#exo-b1-counting-7) ) et de la question 13, que $\binom{2p}p \equiv 2 \pmod p$ pour tout [nombre premier](#def-b1-arith-prime) $p$ .
16. Calculez $v_3\binom{1000}{500}$ de deux façons : une fois par Kummer (écrivez $500$ en base $3$ et comptez les retenues dans $500 +  500$ ), une fois par la forme en chiffres de Legendre (calculez $s_3(500)$ et $s_3(1000)$ ) ; vérifiez que les deux donnent la même valeur.

**Partie IV — La parité du triangle de Pascal, et une minoration de la densité des [nombres premiers](#def-b1-arith-prime).**

17. Démontrez le critère sur les chiffres : $\binom nk$ est *impair* si et seulement si chaque chiffre binaire de $k$ est au plus égal au chiffre correspondant de $n$ . Énoncez et démontrez le critère analogue pour $p \nmid \binom nk$ en base $p$ .
18. Déduisez-en que la ligne $n$ du triangle de Pascal contient exactement $2^{s_2(n)}$ coefficients impairs ; vérifiez-le sur les lignes $4$ et $5$ .
19. Déduisez-en que tous les coefficients intérieurs $\binom nk$ ( $0 < k < n$ ) sont pairs si et seulement si $n$ est une puissance de $2$ .
20. Démontrez que toute puissance de [nombre premier](#def-b1-arith-prime) divisant $\binom{m+n}m$ est au plus $m + n$ : si $p^a \mid \binom{m+n}m$ , alors $p^a \leq  m + n$ . *(Combien de termes non nuls la somme de la question 11 peut-elle avoir ?)*
21. Déduisez-en que $\binom{2n}n$ [divise](#def-b1-arith-divides) $\operatorname{lcm}(1, 2, \dots, 2n)$, et combinez avec la minoration $\binom{2n}n \geq \frac{4^n}{2n+1}$ (que vous démontrerez : le coefficient central est le plus grand des $2n + 1$ coefficients de la ligne $2n$) pour obtenir $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$$ les multiples communs des premiers entiers croissent *exponentiellement* — un premier aperçu quantitatif de l’abondance des [nombres premiers](#def-b1-arith-prime).

**Partie V — Synthèse.**

22. Trouvez le plus petit $n$ tel que $n!$ se termine par au moins $2026$ zéros. *(Estimez $Z(n) \approx n/4$, puis ajustez à l’aide de la formule exacte.)*
23. Une dernière vérification croisée : montrez que $7$ ne [divise](#def-b1-arith-divides) *pas* $\binom{100}{50}$ , d’abord en écrivant $50$ en base $7$ et en vérifiant que l’addition $50 + 50$ est sans retenue, puis en calculant $v_7(100!)$ et $v_7(50!)$ avec la [formule de Legendre](#pb-b1-arith-1) .
24. Où exactement le problème a-t-il utilisé : (i) l’unicité de la factorisation ; (ii) la décomposition par division euclidienne $n = p^k n_1 + n_0$ ; (iii) un argument de dénombrement du [Chapitre 2](https://one-course.com/books/math/3/fr/chapter/2-denombrement#ch-b1-counting) ? Une phrase pour chacun.
25. Synthèse, en un court paragraphe : la [formule de Legendre](#pb-b1-arith-1) transforme une question de [divisibilité](#def-b1-arith-divides) en arithmétique des chiffres, et le [théorème de Kummer](#pb-b1-arith-1) lit la réponse sur les retenues d’une seule addition — commentez cette traduction, les vérifications de la question 16, et ce que la minoration de la question 21 suggère au sujet des [nombres premiers](#def-b1-arith-prime) (l’énoncé complet, le théorème des [nombres premiers](#def-b1-arith-prime) , dépasse de loin ce volume ; l’analogue polynomial de la boîte à outils de ce chapitre est le [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly) ).

**Solution de Problème 6.1.**

**1.** $10! = 3\,628\,800$ : deux zéros terminaux. Valuations facteur par facteur : les puissances de $2$ proviennent de $2, 4 = 2^2, 6, 8 = 2^3,
10$, ce qui totalise $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$ ; les puissances de $5$ proviennent de $5$ et $10$ : $v_5(10!) = 2$. Zéros terminaux $=
\min(v_2, v_5) = 2$, cohérent.

**2.** Écrivons la division euclidienne $\lfloor x\rfloor = nq +
r$, $0 \leq r \leq n - 1$. Alors $x = nq + r + \{x\}$ avec $0 \leq
r + \{x\} < n$, donc $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor
x \rfloor / n \bigr\rfloor$.

**3.** Soit $\alpha = v_p(a) \leq \beta = v_p(b)$ (quitte à échanger) et écrivons $a = p^\alpha a'$, $b = p^\beta b'$ avec $p
\nmid a', b'$. Alors $a + b = p^\alpha\bigl(a' + p^{\beta -
\alpha}b'\bigr)$, donc $v_p(a + b) \geq \alpha = \min$. Si $\alpha <
\beta$, la parenthèse vaut $a' + p^{\beta-\alpha}b' \equiv a'
\not\equiv 0 \pmod p$ : la valuation est exactement $\alpha$.

**4.** Les multiples de $m$ dans $\intint1n$ sont $m, 2m, \dots,
qm$ où $q$ est le plus grand entier tel que $qm \leq n$, c’est-à-dire $q =
\lfloor n/m \rfloor$.

**5.** Par unicité de la factorisation, $v_p(n!) = \sum_{j=1}^{n}
v_p(j)$. Comptons autrement : chaque $j$ contribue pour $v_p(j) =
\#\{k \geq 1 : p^k \mid j\}$, donc

$$
v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\}
= \sum_{k\geq1} \#\{j \leq n : p^k \mid j\}
= \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor
$$

d’après la question 4 — c’est la [formule de Legendre](#pb-b1-arith-1). La somme est finie : les termes avec $p^k > n$ s’annulent.

**6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (divisions par $5, 25, 125, 625$) ; $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 +
7 + 3 + 1 = 994$. Zéros terminaux de $1000!$ : chaque zéro consomme un $2$ et un $5$, il y en a donc $\min(994, 249) = 249$.

**7.** Avec $n = \sum_i a_ip^i$, la question 2 donne $\lfloor
n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (on tronque le développement en base $p$). En sommant sur $k \geq 1$ et en échangeant les deux sommes finies :

$$
v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k}
= \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1}
= \frac{n - s_p(n)}{p - 1} .
$$

**8.** Pour $p = 2$ : $v_2(n!) = n - s_2(n)$. Comme $n \geq 1$ vérifie $s_2(n) \geq 1$, on a toujours $v_2(n!) \leq n - 1 < n$ : $2^n \nmid
n!$. Et $v_2(n!) = n - 1$ si et seulement si $s_2(n) = 1$, si et seulement si $n$ est une puissance de $2$.

**9.** $n$ a $\lfloor \log_p n \rfloor + 1$ chiffres en base $p$, chacun au plus $p - 1$, donc $1 \leq s_p(n) \leq
(p-1)\bigl(\log_p(n) + 1\bigr)$. En substituant dans la question 7 :

$$
\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},
$$

et en divisant par $n$ : $\frac{v_p(n!)}n \to \frac1{p-1}$.

**10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$ : le nombre de zéros terminaux fait un saut de $v_5(n)$ à chaque multiple de $5$ et est constant entre deux. $Z(24) = \lfloor24/5\rfloor = 4$ et $Z(25) =
5 + 1 = 6$ : en $n = 25$, le compte saute de $4$ directement à $6$ ($v_5(25) = 2$), et comme $Z$ est croissante avec $Z \leq 4$ avant et $Z \geq 6$ après, la valeur $5$ n’est jamais atteinte : aucune factorielle ne se termine par exactement cinq zéros.

**11.** Écrivons $x = \lfloor x\rfloor + \{x\}$ : $\lfloor x +
y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} +
\{y\}\rfloor$, et $0 \leq \{x\} + \{y\} < 2$ fait que la dernière partie entière vaut $0$ ou $1$. Puis, par Legendre appliqué trois fois,

$$
v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!)
= \sum_{k\geq1}\Bigl(
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),
$$

une somme finie de $0$ et de $1$ (on applique la première [assertion](https://one-course.com/books/math/3/fr/chapter/1-logique-ensembles-et-applications#def-b1-logic-statement) à $x =
m/p^k$, $y = n/p^k$).

**12.** Fixons $k \geq 1$ et écrivons $m = p^km_1 + m_0$, $n =
p^kn_1 + n_0$ avec $0 \leq m_0, n_0 < p^k$ (division euclidienne : $m_0$ est le nombre formé des $k$ chiffres de poids faible de $m$). Alors

$$
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac m{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac n{p^k}\Bigr\rfloor
= \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,
$$

qui vaut $1$ si $m_0 + n_0 \geq p^k$ et $0$ sinon. Or $m_0 +
n_0 \geq p^k$ signifie précisément que l’addition des $k$ chiffres de poids faible de $m$ et de $n$ déborde en position $k$ — une retenue en position $k$ dans l’algorithme d’addition appris à l’école. En sommant sur $k$ : $v_p\binom{m+n}m$ est le nombre de retenues de l’addition $m + n$ en base $p$. (Kummer, 1852.)

**13.** Appliquons Kummer à $m = j$, $n = p^k - j$, de somme $p^k =
(1\underbrace{0\cdots0}_{k})_p$. Posons $a = v_p(j)$ : les chiffres en base $p$ de $j$ aux positions $0, \dots, a-1$ sont nuls et le chiffre en position $a$ est non nul. Les chiffres de $p^k - j$ en dessous de la position $a$ sont nuls eux aussi ($p^k - j = p^a(p^{k-a} - j/p^a)$). En position $a$, les deux chiffres non nuls doivent avoir pour somme $p$ (chiffre résultat $0$) : une retenue ; à chacune des positions $a+1, \dots, k-1$, les chiffres augmentés de la retenue entrante ont pour somme $p$ (chiffre résultat $0$ de nouveau) : la retenue se propage. Au total : $k - a$ retenues, donc $v_p\binom{p^k}j = k -
v_p(j)$. Pour $k = 1$ : $v_p\binom pj = 1$ pour $0 < j < p$, la [divisibilité](#def-b1-arith-divides) utilisée au [Théorème 6.23](#thm-b1-arith-fermat).

**14.** Par la forme en chiffres (question 7), en utilisant $s_2(2n) =
s_2(n)$ (on ajoute un chiffre $0$) :

$$
v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n -
s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :
$$

$\binom{2n}n$ est toujours pair, et $v_2 = 1$ (c’est-à-dire $\binom{2n}n
\equiv 2 \pmod 4$) exactement lorsque $s_2(n) = 1$, c’est-à-dire lorsque $n$ est une puissance de $2$.

**15.** Vandermonde avec $m = n = k = p$ : $\binom{2p}p =
\sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. Pour $0 < j < p$, $p \mid \binom pj$ (question 13), donc $\binom
pj^2 \equiv 0 \pmod p$ ; les termes extrêmes donnent $1 + 1$ : $\binom{2p}p \equiv 2 \pmod p$.

**16.** Base $3$ : $500 = 486 + 9 + 3 + 2$, chiffres (des poids faibles aux poids forts) $(2, 1, 1, 0, 0, 2)$, donc $s_3(500) = 6$ ; et $1000 = 729 +
243 + 27 + 1$, chiffres $(1, 0, 0, 1, 0, 1, 1)$, donc $s_3(1000) = 4$. *Kummer :* additionnons $500 + 500$ en base $3$ : position $0$ : $2 + 2 =
4$, chiffre $1$, retenue $1$ ; position $1$ : $1 + 1 + 1 = 3$, chiffre $0$, retenue $1$ ; position $2$ : $1 + 1 + 1 = 3$, chiffre $0$, retenue $1$ ; position $3$ : $0 + 0 + 1 = 1$, pas de retenue ; position $4$ : $0$ ; position $5$ : $2 + 2 = 4$, chiffre $1$, retenue $1$ ; position $6$ : la retenue tombe : chiffre $1$. Quatre retenues : $v_3\binom{1000}{500} = 4$. *Legendre :* $v_3(1000!) = \frac{1000 - 4}2 = 498$ et $v_3(500!) = \frac{500 - 6}2 = 247$, donc $v_3\binom{1000}{500} =
498 - 2\times247 = 4$. Les deux calculs concordent — et les chiffres de l’addition $(1, 0, 0, 1, 0, 1, 1)$ redonnent $1000$, comme il se doit.

**17.** Par Kummer ($p = 2$, $m = k$, $n' = n - k$) : $\binom nk$ est impair si et seulement si l’addition $k + (n - k)$ en base $2$ n’a aucune retenue, si et seulement si, à chaque position, les chiffres vérifient $k_i + (n -
k)_i = n_i$ ; dans ce cas $k_i \leq n_i$ pour tout $i$. Réciproquement, si $k_i \leq n_i$ pour tout $i$, alors le nombre dont les chiffres sont $n_i -
k_i$ vaut $n - k$, et l’addition est sans retenue. Même démonstration en base $p$ : $p \nmid \binom nk$ si et seulement si chaque chiffre en base $p$ de $k$ est au plus égal au chiffre correspondant de $n$.

**18.** En comptant les $k \in \intint0n$ dont les chiffres vérifient $k_i \leq n_i$ : chaque chiffre de $k$ est choisi indépendamment parmi $n_i + 1$ valeurs, ce qui donne $\prod_i (n_i + 1)$ choix ; en base $2$ cela vaut $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. Ligne $4 =
(100)_2$ : $2^1 = 2$ coefficients impairs — en effet $1, 4, 6, 4, 1$ n’a de coefficients impairs qu’aux extrémités. Ligne $5 = (101)_2$ : $2^2 = 4$ — en effet $1, 5, 10, 10, 5, 1$.

**19.** Tous les coefficients intérieurs sont pairs $\iff$ la ligne a exactement $2$ coefficients impairs (les deux extrémités le sont toujours) $\iff 2^{s_2(n)} =
2 \iff s_2(n) = 1 \iff n$ est une puissance de $2$.

**20.** Dans la somme de la question 11, le $k$-ième terme s’annule dès que $p^k > m + n$ (les trois parties entières sont alors égales, la première valant même $0$ quand $p^k > m+n$ ; plus simplement, chaque terme est nul). Donc au plus $\lfloor \log_p(m+n)\rfloor$ termes sont non nuls, chacun valant $1$ : $a = v_p\binom{m+n}m \leq \log_p(m+n)$, c’est-à-dire $p^a \leq
m + n$.

**21.** Pour tout [nombre premier](#def-b1-arith-prime) $p$, $v_p\bigl(\operatorname{lcm}(1,
\dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (la plus grande puissance de $p$ n’excédant pas $2n$ figure parmi $1, \dots, 2n$). La question 20 avec $m = n$ donne $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ pour tout $p$ : d’après la [Proposition 6.16](#prop-b1-arith-valuation), $\binom{2n}n
\mid \operatorname{lcm}(1, \dots, 2n)$. Pour la taille : le rapport $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ exactement pour $k < n$, donc le coefficient central est le plus grand des $2n + 1$ coefficients de la ligne $2n$, d’où $4^n = \sum_k \binom{2n}k \leq
(2n+1)\binom{2n}n$. En combinant :

$$
\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq
\frac{4^n}{2n + 1} .
$$

S’il y avait peu de [nombres premiers](#def-b1-arith-prime) en dessous de $2n$, le PPCM ne pourrait pas être aussi grand : la croissance exponentielle du PPCM est une trace quantitative de l’abondance des [nombres premiers](#def-b1-arith-prime).

**22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac
n4$, on vise donc autour de $n = 4 \times 2026 = 8104$ : $Z(8104) = 1620 +
324 + 64 + 12 + 2 = 2022$. Montons de multiple de $5$ en multiple de $5$ : $Z(8110)
= 2024$, $Z(8115) = 2025$, et

$$
Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .
$$

Comme $Z$ est constante entre deux multiples de $5$ et que $Z(8119) =
Z(8115) = 2025$, le plus petit $n$ ayant au moins $2026$ zéros terminaux est $n = 8120$.

**23.** Base $7$ : $50 = 49 + 1$, chiffres (des poids faibles aux poids forts) $(1, 0,
1)$. Additionnons $50 + 50$ : position $0$ : $1 + 1 = 2 < 7$, pas de retenue ; position $1$ : $0 + 0 = 0$ ; position $2$ : $1 + 1 = 2 < 7$, pas de retenue. Sans retenue, donc par Kummer $v_7\binom{100}{50} = 0$ : $7 \nmid
\binom{100}{50}$. Legendre confirme : $v_7(100!) = \lfloor 100/7
\rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ et $v_7(50!) = 7
+ 1 = 8$, donc $v_7\binom{100}{50} = 16 - 2\times8 = 0$.

**24.** (i) L’unicité de la factorisation sous-tend la définition même de $v_p$ et son additivité, donc la [formule de Legendre](#pb-b1-arith-1) et toutes les conclusions de [divisibilité](#def-b1-arith-divides) ([Proposition 6.16](#prop-b1-arith-valuation)). (ii) La division euclidienne a produit l’identité de troncature de la question 2 et la décomposition $m = p^km_1 +
m_0$ qui isole la retenue (question 12). (iii) Dénombrement : le comptage des multiples de $m$ (question 4), le produit des choix de chiffres (question 18) et la majoration par la somme d’une ligne $4^n \leq
(2n+1)\binom{2n}n$ (question 21) sont tous des arguments dans l’esprit du [Chapitre 2](https://one-course.com/books/math/3/fr/chapter/2-denombrement#ch-b1-counting).

**25.** Legendre convertit « quelle puissance de $p$ [divise](#def-b1-arith-divides) $n!$ » en arithmétique des chiffres en base $p$ ; Kummer comprime la réponse, pour les coefficients binomiaux, dans les retenues d’une seule addition — la [divisibilité](#def-b1-arith-divides), apparemment propriété globale d’énormes nombres, se lit localement, chiffre par chiffre. La question 16 en est le paradigme : quatre retenues, calculées à la main, déterminent la puissance exacte de $3$ dans un nombre de plusieurs centaines de chiffres. Et la question 21 montre le même cercle d’idées effleurant des eaux profondes : une minoration exponentielle de $\operatorname{lcm}(1, \dots, 2n)$ est un premier pas, entièrement élémentaire, vers le théorème des [nombres premiers](#def-b1-arith-prime), dont la démonstration dépasse de loin ce volume. Toute la boîte à outils — division, PGCD, valuations — est rejouée pour les polynômes au [Chapitre 8](https://one-course.com/books/math/3/fr/chapter/8-polynomes#ch-b1-poly), où l’analogue du développement en chiffres est le développement suivant les puissances de $(X - a)$.