Arithmétique dans l'ensemble des entiers relatifs

Cours · mathématiques MPSI, chapitre 7 · MPSI (classe préparatoire scientifique) · le début du chapitre, la suite sur Adloun

Le crible d'Ératosthène de 1 à 30, avec les nombres premiers mis en évidence.

7.1 Introduction et motivation

L'objectif de ce chapitre est d'étudier les propriétés de la divisibilité des entiers et des congruences. L'approche reste élémentaire : elle ne fait pas appel au langage des structures algébriques (groupes, anneaux), qui sera introduit plus tard — toute la théorie se construit ici à partir de la seule division euclidienne.

Longtemps considérée comme la plus « pure » des disciplines mathématiques, l'arithmétique est devenue au XX^e siècle le socle de la sécurité numérique : le chiffrement RSA, les signatures électroniques et les cartes bancaires reposent précisément sur les théorèmes de ce chapitre — Bézout, Gauss, et le petit théorème de Fermat. Les nombres premiers y jouent le rôle d'« atomes » : tout entier s'écrit de façon unique comme produit de nombres premiers, et c'est la difficulté de retrouver ces atomes qui protège nos communications.

7.2 Divisibilité et division euclidienne

7.2.1 Divisibilité

Définition 7.1Divisibilité, diviseurs, multiples

Soient $a, b \in Z$ . On dit que $a$ divise $b$ , et on note $a ∣ b$ , s'il existe $c \in Z$ tel que $b = a c$ . On dit alors que $a$ est un diviseur de $b$ , et que $b$ est un multiple de $a$ .

Exemple 7.2

$7 ∣ 91$ (car $91 = 7 \times 13$ ) ; $1$ et $- 1$ divisent tout entier ; tout entier divise $0$ ; mais $0$ ne divise que $0$ . Les diviseurs de $12$ sont $\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12$ .

Proposition 7.3Propriétés de la divisibilité

Pour tous entiers $a, b, c$ :

Transitivité : si $a ∣ b$ et $b ∣ c$ , alors $a ∣ c$ .
Combinaisons linéaires : si $a ∣ b$ et $a ∣ c$ , alors $a ∣ (b u + c v)$ pour tous $u, v \in Z$ .
Si $a ∣ b$ et $b \neq = 0$ , alors $∣ a ∣ \leq ∣ b ∣$ : un entier non nul n'a qu'un nombre fini de diviseurs.

Proposition 7.4Couples d'entiers associés

Pour $a, b \in Z$ :

$a ∣ b et b ∣ a ⟺ ∣ a ∣ = ∣ b ∣ ⟺ b = a ou b = - a .$

On dit alors que $a$ et $b$ sont associés.

Démonstration

Si $a ∣ b$ et $b ∣ a$ avec $a, b$ non nuls, alors $∣ a ∣ \leq ∣ b ∣$ et $∣ b ∣ \leq ∣ a ∣$ , d'où $∣ a ∣ = ∣ b ∣$ . (Si l'un est nul, l'autre aussi.) La réciproque est immédiate.

7.2.2 Division euclidienne

◆Théorème 7.5Théorème de la division euclidienne

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

$a = b q + r et 0 \leq r < b .$

L'entier $q$ est le quotient, $r$ le reste de la division euclidienne de $a$ par $b$ . (Pour $b \in Z^{*}$ , l'énoncé subsiste avec $0 \leq r < ∣ b ∣$ .)

Démonstration

Existence. L'ensemble $E = {k \in Z : k b \leq a}$ est non vide (il contient $- ∣ a ∣$ ) et majoré (par $∣ a ∣$ ) : il admet un plus grand élément $q$ . Alors $q b \leq a < (q + 1) b$ , et $r = a - b q$ vérifie $0 \leq r < b$ .

Unicité. Si $b q + r = b q^{'} + r^{'}$ avec $0 \leq r, r^{'} < b$ , alors $b (q - q^{'}) = r^{'} - r$ , donc $b ∣ r^{'} - r$ ; or $∣ r^{'} - r ∣ < b$ , ce qui force $r^{'} = r$ , puis $q^{'} = q$ .

Exemple 7.6

$47 = 5 \times 9 + 2$ : quotient $9$ , reste $2$ . Attention aux négatifs : $- 47 = 5 \times (- 10) + 3$ : le reste est $3$ (toujours positif), pas $- 2$ . En Python, -47 % 5 renvoie bien 3.

iRemarque

Le reste de la division par $b$ classe les entiers en $b$ familles ( $r = 0, 1, \dots, b - 1$ ) : c'est le point de départ des congruences de la fin du chapitre. Par exemple, tout entier est de la forme $2 k$ ou $2 k + 1$ (pair ou impair).

7.3 PGCD et algorithme d'Euclide

7.3.1 Le PGCD

Définition 7.7PGCD

Soient $a, b \in N$ , non tous deux nuls. L'ensemble des diviseurs communs positifs à $a$ et $b$ est fini et non vide (il contient $1$ ) : il admet un plus grand élément (pour l'ordre naturel de $N$ ), appelé PGCD de $a$ et $b$ et noté $a \land b$ (ou $pgcd (a, b)$ ).

Exemple 7.8

Diviseurs positifs de $12$ : $1, 2, 3, 4, 6, 12$ ; de $18$ : $1, 2, 3, 6, 9, 18$ . Diviseurs communs : $1, 2, 3, 6$ , donc $12 \land 18 = 6$ . Noter aussi $a \land 0 = a$ pour $a \in N^{*}$ .

7.3.2 L'algorithme d'Euclide

▪Lemme 7.9Lemme d'Euclide

Si $a = b q + r$ , alors les diviseurs communs de $a$ et $b$ sont exactement les diviseurs communs de $b$ et $r$ . En particulier :

$a \land b = b \land r .$

Démonstration

Si $d ∣ a$ et $d ∣ b$ , alors $d ∣ a - b q = r$ ; si $d ∣ b$ et $d ∣ r$ , alors $d ∣ b q + r = a$ . Les deux couples ont donc le même ensemble de diviseurs communs — et a fortiori le même plus grand élément.

ImportantAlgorithme d'Euclide

Pour calculer $a \land b$ ( $a \geq b > 0$ ) : on remplace $(a, b)$ par $(b, r)$ où $r$ est le reste de la division de $a$ par $b$ , et on recommence jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD. L'algorithme termine car les restes forment une suite strictement décroissante d'entiers positifs.

$252 \land 198 : 252 = 1 \times 198 + 54, 198 = 3 \times 54 + 36, 54 = 1 \times 36 + 18, 36 = 2 \times 18 + 0,$

donc $252 \land 198 = 18$ .

◆Théorème 7.10Propriétés fondamentales du PGCD

Soient $a, b \in N$ non tous deux nuls.

L'ensemble des diviseurs communs à $a$ et $b$ est exactement l'ensemble des diviseurs de $a \land b$ . Autrement dit, $a \land b$ est le plus grand des diviseurs communs au sens de la divisibilité : $d ∣ a$ et $d ∣ b$ $⟺$ $d ∣ a \land b$ .
Pour tout $k \in N^{*}$ : $(k a) \land (k b) = k (a \land b)$ .

Démonstration

Le premier point s'obtient en remontant l'algorithme d'Euclide : à chaque étape, l'ensemble des diviseurs communs est inchangé (lemme) ; à la fin, c'est l'ensemble des diviseurs du dernier reste non nul $a \land b$ . Pour le second : en multipliant chaque division $a = b q + r$ par $k$ , on obtient $k a = (k b) q + k r$ avec $0 \leq k r < k b$ — l'algorithme d'Euclide pour $(k a, k b)$ reproduit celui de $(a, b)$ multiplié par $k$ , et le dernier reste non nul est $k (a \land b)$ .

Définition 7.11Extension aux entiers relatifs

Pour $a, b \in Z$ non tous deux nuls, on pose $a \land b = ∣ a ∣ \land ∣ b ∣$ : la divisibilité ne dépend pas des signes.

7.3.3 Relation de Bézout et algorithme d'Euclide étendu

◆Théorème 7.12Relation de Bézout

Soient $a, b \in Z$ non tous deux nuls. Il existe $(u, v) \in Z^{2}$ tel que :

$a u + b v = a \land b .$

Un tel couple $(u, v)$ est appelé couple de Bézout (il n'est pas unique).

Démonstration

On remonte l'algorithme d'Euclide. Chaque reste s'écrit $r = a - b q$ : c'est une combinaison $a u + b v$ . Par récurrence descendante, si deux restes consécutifs $r_{k - 1}$ et $r_{k}$ sont des combinaisons de $a$ et $b$ , alors $r_{k + 1} = r_{k - 1} - q_{k} r_{k}$ aussi. Le dernier reste non nul, $a \land b$ , est donc de la forme $a u + b v$ .

ImportantMéthode : l'algorithme d'Euclide étendu

On exécute Euclide, puis on remonte les calculs en exprimant chaque reste à partir de $a$ et $b$ . Exemple avec $a = 40$ , $b = 17$ :

$40 = 2 \times 17 + 6, 17 = 2 \times 6 + 5, 6 = 1 \times 5 + 1, 5 = 5 \times 1 + 0.$

Donc $40 \land 17 = 1$ , et en remontant :

$1 = 6 - 5 = 6 - (17 - 2 \times 6) = 3 \times 6 - 17 = 3 (40 - 2 \times 17) - 17 = 3 \times 40 - 7 \times 17.$

D'où le couple de Bézout $(u, v) = (- 7, 3)$ : $17 \times (- 7) + 40 \times 3 = 1$ .

7.3.4 PPCM

Définition 7.13PPCM

Soient $a, b \in N^{*}$ . L'ensemble des multiples communs strictement positifs de $a$ et $b$ est non vide (il contient $ab$ ) : son plus petit élément est le PPCM de $a$ et $b$ , noté $a \lor b$ . Les multiples communs de $a$ et $b$ sont exactement les multiples de $a \lor b$ , et l'on a (voir section sur les valuations) :

$(a \land b) (a \lor b) = ab .$

Exemple 7.14

$12 \lor 18 = 36$ , et l'on vérifie $6 \times 36 = 216 = 12 \times 18$ .

Exercices du chapitre

Mersenne, Fermat et le démenti d'Euler corrigé
Euclide à l'étage des exposants : $(2^{a} - 1) \land (2^{b} - 1) = 2^{a \land b} - 1$ corrigé
Le problème des deux pièces (Sylvester) corrigé
Gauss et les racines : entier ou irrationnel corrigé
Aucun polynôme ne fabrique que des nombres premiers corrigé
Les valuations font tout : PGCD, PPCM et la formule de Legendre corrigé

La suite du cours · Tous les exercices du chapitre