Mathématiques universitaires — Licence 1 · Bachelor Year 1

6Arithmétique des entiers

L’arithmétique — l’étude de la divisibilité dans $\Z$ — a été commencée dans le volume de Terminale (lycée). Ce chapitre la reconstruit entièrement à partir de la division euclidienne, avec des démonstrations complètes : plus grand commun diviseur et algorithme d’Euclide, théorème de Bézout et lemme de Gauss, décomposition en facteurs premiers, et le calcul des congruences jusqu’au petit théorème de Fermat. Au-delà de son charme propre, ce matériau est le modèle que le Chapitre 8 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 $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 à 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$ ; existence du PGCD)

Tout sous-groupe de $(\Z, +)$ est de la forme $n\Z = \{nk : k \in \Z\}$ pour un unique $n \in \N$ .
Pour $a, b \in \Z$ non tous deux nuls, l’ensemble $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 $a$ et $b$ , et tout diviseur commun de $a$ et $b$ divise $d$ .

Démonstration. (1) Soit $H \subseteq \Z$ un sous-groupe (non vide, stable par soustraction ; la définition formelle est au Chapitre 7, 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) ; $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 les deux. Et si $c$ divise $a$ et $b$ , alors $c$ divise 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 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$ .

(Lemme de Gauss) Si $a \mid bc$ et $\gcd(a, b) = 1$ , alors $a \mid c$ .
Si $a \mid c$ , $b \mid c$ et $\gcd(a,b) = 1$ , alors $ab \mid c$ .
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, $\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 $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 ( $\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, le lemme de 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 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 à 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), 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 $\leq \sqrt n$ . Ainsi, pour tester si $n$ est premier, il suffit d’essayer les nombres premiers 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, 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.

Théorème 6.14 (Euclide)

Il existe une infinité de nombres premiers.

Démonstration. Tout entier $n \geq 2$ possède un diviseur premier : son plus petit diviseur $\geq 2$ est premier (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, et posons $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Un certain premier $p_i$ divise $N$ ; mais $p_i$ divise 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, 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) : $n = 2$ est premier ; pour $n > 2$ , ou bien $n$ est premier, 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 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 dépasse $1$ ). Pour $r \geq 1$ : le premier $p_1$ divise $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 un certain $q_j$ . Mais $q_j$ est premier 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 égaux. ∎

Proposition 6.16 (Valuations)

Pour $p$ premier 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 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 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 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 modulo $9$ à la somme de ses chiffres (démontré à l’Exercice 6.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 de l’Exemple 6.24 : les vérifications par congruence réfutent, elles ne certifient pas.

Proposition 6.20 (Inversibilité modulo $n$ )

$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 é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). Unicité : si $ab \equiv ab' \equiv 1$ , alors $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Exemple 6.21 (Inverser $7$ modulo $26$ )

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 $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, où les modules 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 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. 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 $\binom pk = \frac{p!}{k!(p-k)!}$ est divisible par $p$ : en effet $k!\,(p-k)!\, \binom pk = p!$ et $p$ divise $p!$ tout en étant premier avec $k!(p-k)!$ (tous les facteurs sont $< p$ ), donc le lemme de 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). ∎

Exemple 6.24 (La réciproque de Fermat est fausse : $341$ )

Le petit théorème de 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. 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 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 de la Remarque 6.27. Morale : une implication et sa réciproque mènent des vies séparées (Remarque 1.10), 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)

Diviser une 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 aussi le module : $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Mésusage du lemme d’Euclide. $a \mid bc$ entraîne $a \mid b$ ou $a \mid c$ seulement si $a$ est premier (ou premier avec l’un des facteurs) : $6 \mid 4 \times 9$ alors que $6$ ne divise aucun des deux facteurs.
« Premiers entre eux » est une relation, pas une propriété. « $8$ et $9$ sont premiers entre eux » est vrai bien qu’aucun des deux ne soit premier ; « premiers entre eux deux à deux » est plus fort que « premiers entre eux dans leur ensemble » ( $\gcd(6, 10, 15) = 1$ mais aucune paire n’est formée d’entiers premiers entre eux).
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.

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, 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 devient l’anneau $\Z/n\Z$ au Chapitre 7, dont les éléments inversibles (Proposition 6.20) forment le premier exemple non trivial de groupe des unités. Les valuations reviennent dans le devoir maison ci-dessous (formule de Legendre) et alimentent les démonstrations d’irrationalité du Chapitre 10. 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 est l’ancêtre des tests de primalité qui certifient les grands nombres premiers qu’on y utilise.

Remarque 6.28 (Interlude : $\Z$ 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é (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, 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, où les questions d’inversibilité (la Proposition 6.20 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. — 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 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, ainsi qu’un couple de Bézout associé.

Solution

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é en base $10$ : un entier est congru 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

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 à 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

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

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). 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 et $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solution

Solution de Exercice 6.5.

Pour tout nombre premier $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 sont égaux (Proposition 6.16), 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

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) ; 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 $p$ , en utilisant les valuations : comparez $v_p$ des deux membres de $p q^2 = r^2$ .

Solution

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, le couple de congruences $x \equiv a \ (m)$ , $x \equiv b\ (n)$ a toujours une solution, unique modulo $mn$ .

Solution

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 $x - x'$ , donc $mn \mid x - x'$ (Théorème 6.8 (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).

Solution

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 (Exercice 6.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.

Solution

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 $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 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. 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, alors $(n-1)! \not\equiv -1 \pmod n$ .

Solution

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). 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$ .

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

Solution

Solution de Exercice 6.12.

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 .$
Soient $m < n$ et $d = \gcd(F_m, F_n)$ . D’après (1), $F_m$ divise $F_n - 2$ , donc $d$ divise à la fois $F_n$ et $F_n - 2$ , et divise donc $2$ . Mais tout nombre de Fermat est impair, donc $d = 1$ .
Chaque $F_n \geq 3$ a un diviseur premier $p_n$ (première étape du Théorème 6.14). Si $m \neq n$ , alors $p_m \neq p_n$ , car un premier commun diviserait $\gcd(F_m, F_n) = 1$ . L’application $n \mapsto p_n$ est donc injective de $\N$ dans l’ensemble des nombres premiers : il existe une infinité de nombres premiers.

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 $p$ qui divise $n!$ , ou qui divise un coefficient binomial ? 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. Dans tout ce qui suit, $p$ est un nombre premier, $\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.

É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$ .
Démontrez que, pour $x \in \R$ et $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
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)$ .
Montrez que le nombre de multiples de $m$ dans $\intint1n$ est $\lfloor n/m \rfloor$ .
Démontrez la formule de Legendre : 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.

Calculez $v_5(1000!)$ et $v_2(1000!)$ , et concluez : par combien de zéros se termine $1000!$ ?
Démontrez la forme en chiffres de la formule de Legendre : en écrivant $n = \sum_i a_i p^i$ en base $p$ ,

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
Deux conséquences pour $p = 2$ : montrez que $2^n$ ne divise jamais $n!$ , et que $2^{n-1}$ divise $n!$ exactement lorsque $n$ est une puissance de $2$ .
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é.
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.

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 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$ .
Démontrez le théorème de Kummer : 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$ .)
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, retrouvée.)
Démontrez que $v_2\binom{2n}n = s_2(n)$ . Déduisez-en que le coefficient binomial central est toujours pair, et que $\binom{2n}n \equiv 2 \pmod 4$ exactement lorsque $n$ est une puissance de $2$ .
Montrez, à l’aide de l’identité de Vandermonde (Exercice 2.7) et de la question 13, que $\binom{2p}p \equiv 2 \pmod p$ pour tout nombre premier $p$ .
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.

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$ .
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$ .
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$ .
Démontrez que toute puissance de nombre premier 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 ?)
Déduisez-en que $\binom{2n}n$ divise $\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.

Partie V — Synthèse.

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.)
Une dernière vérification croisée : montrez que $7$ ne divise 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.
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 ? Une phrase pour chacun.
Synthèse, en un court paragraphe : la formule de Legendre transforme une question de divisibilité en arithmétique des chiffres, et le théorème de Kummer 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 (l’énoncé complet, le théorème des nombres premiers, dépasse de loin ce volume ; l’analogue polynomial de la boîte à outils de ce chapitre est le Chapitre 8).

Solution

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. 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 à $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é utilisée au Théorème 6.23.

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 $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, $\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 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.

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 et toutes les conclusions de divisibilité (Proposition 6.16). (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.

25. Legendre convertit « quelle puissance de $p$ divise $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é, 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, 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, où l’analogue du développement en chiffres est le développement suivant les puissances de $(X - a)$ .