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

29Arithmétique

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

29.1 Divisibilité et division euclidienne

Définition 29.1 (Divisibilité)

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

Proposition 29.2

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

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

Théorème 29.3 (Division euclidienne)

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

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

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

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

29.2 Congruences

Définition 29.4 (Congruence)

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

Proposition 29.5 (Compatibilité avec les opérations)

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

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

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

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

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

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

29.3 PGCD, Bézout et Gauss

Définition 29.7 (PGCD)

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

Proposition 29.8 (Algorithme d’Euclide)

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

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

Exemple 29.9

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

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

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

au + bv = d .

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

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

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

Théorème 29.11 (Lemme de Gauss)

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

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

Corollaire 29.12

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

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

29.4 Nombres premiers

Définition 29.13 (Premier)

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

Proposition 29.14

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

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

Théorème 29.15 (Euclide)

Il existe une infinité de nombres premiers.

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

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

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

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

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

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

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

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

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

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

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

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

Exemple 29.18 (Application à la cryptographie)

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

29.5 Exercices

Exercice 29.1 ★

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

Solution

Solution de Exercice 29.1.

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

Exercice 29.2 ★

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

Solution

Solution de Exercice 29.2.

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

Exercice 29.3 ★

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

Solution

Solution de Exercice 29.3.

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

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

Exercice 29.4 ★

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

Solution

Solution de Exercice 29.4.

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

Exercice 29.5 ★★

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

Solution

Solution de Exercice 29.5.

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

Exercice 29.6 ★★

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

Solution

Solution de Exercice 29.6.

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

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

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

Exercice 29.7 ★★

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

17x - 40y = 1,

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

Solution

Solution de Exercice 29.7.

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

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

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

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

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

Exercice 29.8 ★★

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

Solution

Solution de Exercice 29.8.

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

Exercice 29.9 ★★★

Soit $p$ un nombre premier.

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

Solution

Solution de Exercice 29.9.

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

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

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

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

Exercice 29.10 ★★★

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

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

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

Solution

Solution de Exercice 29.10.

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

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

n \equiv 23 \pmod{105}.

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