Arithmétique dans Z — leçon d'oral du CAPES

Prérequis

Situation dans les programmes : multiples, diviseurs, nombres premiers et décomposition en facteurs premiers au cycle 4 et en seconde ; en option mathématiques expertes de terminale, division euclidienne, congruences, PGCD, théorèmes de Bézout et de Gauss, petit théorème de Fermat, avec des activités de chiffrement.
Construction de $\mathbb{N}$ et de $\mathbb{Z}$ , récurrence, toute partie non vide de $\mathbb{N}$ admet un plus petit élément.
Groupes, sous-groupes, anneaux, idéaux, théorème de Lagrange.
Algorithmique : boucles et fonctions en Python (algorithme d'Euclide, exponentiation modulaire rapide).

Proposition de plan en trois parties

I. Divisibilité, PGCD et algorithme d'Euclide

Division euclidienne : pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^{\ast}$ , il existe un unique couple $(q, r)$ avec $a = bq + r$ et $0 \le r \lt b$ . Les sous-groupes de $\mathbb{Z}$ sont les $n\mathbb{Z}$ , $n \in \mathbb{N}$ . PGCD défini par $a\mathbb{Z} + b\mathbb{Z} = (a \wedge b)\mathbb{Z}$ , PPCM par $a\mathbb{Z} \cap b\mathbb{Z} = (a \vee b)\mathbb{Z}$ , et $(a \wedge b)(a \vee b) = |ab|$ . Algorithme d'Euclide, fondé sur $a \wedge b = b \wedge r$ , et algorithme étendu. Théorèmes de Bézout et de Gauss. L'équation $ax + by = c$ a des solutions entières si et seulement si $a \wedge b$ divise $c$ . Exemple : $17 \wedge 5 = 1$ et $17 \times (-2) + 5 \times 7 = 1$ .

II. Nombres premiers et décomposition

Tout entier $n \ge 2$ admet un diviseur premier ; il existe une infinité de nombres premiers. Lemme d'Euclide : si un nombre premier $p$ divise $ab$ , alors $p$ divise $a$ ou $b$ . Théorème fondamental de l'arithmétique : existence et unicité, à l'ordre près, de la décomposition en produit de facteurs premiers. Valuations $p$ -adiques, expression du PGCD et du PPCM, nombre de diviseurs $\prod(\alpha_i + 1)$ . Crible d'Ératosthène : un entier $n \ge 2$ sans diviseur premier inférieur ou égal à $\sqrt{n}$ est premier. Exemple : $360 = 2^3 \times 3^2 \times 5$ possède $4 \times 3 \times 2 = 24$ diviseurs positifs.

III. Congruences, anneaux Z/nZ et cryptographie

Congruences modulo $n$ , compatibles avec l'addition et la multiplication ; anneau $\mathbb{Z}/n\mathbb{Z}$ . Théorème : la classe de $a$ est inversible si et seulement si $a \wedge n = 1$ , et $\mathbb{Z}/n\mathbb{Z}$ est un corps si et seulement si $n$ est premier. Indicateur d'Euler $\varphi(n)$ , multiplicativité, $\varphi(p^k) = p^k - p^{k-1}$ . Théorème d'Euler $a^{\varphi(n)} \equiv 1 \pmod n$ si $a \wedge n = 1$ , conséquence du théorème de Lagrange dans le groupe des inversibles, et petit théorème de Fermat. Théorème chinois. Chiffrement RSA avec $n = pq$ et $ed \equiv 1 \pmod{\varphi(n)}$ , exponentiation rapide. Exemple : $p = 5$ , $q = 11$ , $n = 55$ , $\varphi(n) = 40$ , $e = 3$ , $d = 27$ .

Théorème clé et démonstration

Théorème de Bézout et lemme de Gauss

Soient $a, b \in \mathbb{Z}$ et $d = a \wedge b$ leur PGCD (avec $0 \wedge 0 = 0$ ). (i) Il existe $u, v \in \mathbb{Z}$ tels que $au + bv = d$ . (ii) Les entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$ . (iii) Lemme de Gauss : si $a$ divise $bc$ et si $a \wedge b = 1$ , alors $a$ divise $c$ .

Démonstration

1. Sous-groupe. $H = a\mathbb{Z} + b\mathbb{Z} = \{au + bv : u, v \in \mathbb{Z}\}$ contient 0 et est stable par différence : c'est un sous-groupe de $(\mathbb{Z}, +)$ .
2. Sous-groupes de $\mathbb{Z}$ . Si $H = \{0\}$ , $H = 0\mathbb{Z}$ . Sinon, $H \cap \mathbb{N}^{\ast}$ est non vide (car $H$ est stable par opposé) et admet un plus petit élément $\delta$ , et $\delta\mathbb{Z} \subset H$ . Pour $h \in H$ , la division euclidienne $h = \delta q + r$ avec $0 \le r \lt \delta$ donne $r = h - \delta q \in H$ , donc $r = 0$ par minimalité de $\delta$ . Ainsi $H = \delta\mathbb{Z}$ avec $\delta \in \mathbb{N}$ .
3. Identification du PGCD. Comme $a = a \times 1 + b \times 0 \in H$ , $\delta$ divise $a$ , et de même $\delta$ divise $b$ . Réciproquement, tout diviseur commun de $a$ et $b$ divise toute combinaison $au + bv$ , en particulier $\delta \in H$ . Donc $\delta$ est le plus grand diviseur commun positif, $\delta = d$ , et puisque $d \in H$ , (i) est démontré.
4. Point (ii). Si $a \wedge b = 1$ , (i) fournit $u, v$ . Réciproquement, si $au + bv = 1$ , tout diviseur commun positif de $a$ et $b$ divise 1, donc $a \wedge b = 1$ .
5. Lemme de Gauss. Avec $au + bv = 1$ , on a $c = acu + bcv$ . Or $a$ divise $acu$ et $a$ divise $bc$ , donc $a$ divise $c$ .

Développements possibles pour l’oral

Cryptosystème RSA (niveau mathématiques expertes-L2) : choix de $n = pq$ avec $p \neq q$ premiers, de $e$ premier avec $\varphi(n)$ et de $d$ inverse de $e$ modulo $\varphi(n)$ par Euclide étendu ; preuve que $m^{ed} \equiv m \pmod n$ pour tout entier $m$ , même non premier avec $n$ , par le petit théorème de Fermat modulo $p$ et modulo $q$ puis le lemme de Gauss ; sécurité liée à la difficulté de factoriser $n$ .
Théorème chinois (niveau mathématiques expertes-L2) : si $m \wedge n = 1$ , l'application de $\mathbb{Z}/mn\mathbb{Z}$ dans $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ est un isomorphisme d'anneaux, avec une solution explicite par Bézout ; exemple : $x \equiv 2 \pmod 3$ et $x \equiv 3 \pmod 5$ équivalent à $x \equiv 8 \pmod{15}$ ; corollaire : multiplicativité de $\varphi$ .
Infinité des nombres premiers et variantes (niveau seconde-L1) : preuve d'Euclide, infinité des nombres premiers de la forme $4k + 3$ , et existence de $n$ entiers consécutifs composés, $(n+1)! + 2, \dots, (n+1)! + n + 1$ .
Petit théorème de Fermat (niveau mathématiques expertes) : preuve par la formule du binôme, $p$ divisant $\binom{p}{k}$ pour $1 \le k \le p - 1$ , et récurrence sur $a$ , puis preuve par le groupe des inversibles de $\mathbb{Z}/p\mathbb{Z}$ ; la réciproque est fausse : $561 = 3 \times 11 \times 17$ vérifie $a^{560} \equiv 1 \pmod{561}$ pour tout $a$ premier avec 561.

Remarques et questions du jury

Le lemme de Gauss exige l'hypothèse $a \wedge b = 1$ : 6 divise $4 \times 3$ sans diviser ni 4 ni 3.
Le lemme d'Euclide est faux pour un diviseur non premier, et c'est lui qui fonde l'unicité de la décomposition en facteurs premiers ; le jury demande souvent où il intervient dans la preuve.
Le couple de Bézout n'est pas unique : si $au_0 + bv_0 = 1$ , les solutions de $au + bv = 1$ sont les $(u_0 + kb, v_0 - ka)$ , $k \in \mathbb{Z}$ ; pour $17u + 5v = 1$ , $(-2, 7)$ et $(3, -10)$ conviennent.
Sachez exécuter l'algorithme d'Euclide étendu au tableau pour calculer un inverse modulaire : l'inverse de 7 modulo 26 est 15, car $7 \times 15 = 105 = 4 \times 26 + 1$ .
Situer la notion : divisibilité et nombres premiers sont travaillés au collège et en seconde, congruences et Bézout en mathématiques expertes ; le jury apprécie un raisonnement accessible à un élève, comme la preuve par la parité de l'irrationalité de $\sqrt{2}$ .

Exercices corrigés

Exercice 1 Équation diophantienne et identité de Bézout

Palier 1 · découverte

Soient $a, b \in \mathbb{Z}^*$ . L'équation diophantienne $ax + by = c$ d'inconnue $(x, y) \in \mathbb{Z}^2$ admet au moins une solution entière si et seulement si :

$\mathrm{PGCD}(a, b)$ divise c
a et b sont tous les deux pairs
$c > a + b$
c est un nombre premier

Un indice

L'ensemble $a\mathbb{Z} + b\mathbb{Z}$ est l'idéal $d\mathbb{Z}$ où $d = \mathrm{PGCD}(a, b)$ .

Voir la correction

Bonne réponse : A. $\mathrm{PGCD}(a, b)$ divise c

L'ensemble ${ax + by \mid x, y \in \mathbb{Z}}$ est le sous-groupe de $\mathbb{Z}$ engendré par $a$ et $b$ . Tout sous-groupe de $\mathbb{Z}$ est de la forme $d\mathbb{Z}$ avec $d = \mathrm{PGCD}(a, b)$ . L'entier $c$ s'écrit donc sous la forme $ax + by$ si et seulement si $c \in d\mathbb{Z}$ , c'est-à-dire si et seulement si $\mathrm{PGCD}(a, b) \mid c$ .

Exercice 2 Algorithme d'Euclide étendu et inverse modulaire

Palier 2 · application

Quel est l'inverse de 7 dans le corps fini $\mathbb{Z}/31\mathbb{Z}$ (c'est-à-dire l'unique $x \in \{1, \dots, 30\}$ tel que $7x \equiv 1 \pmod{31}$ ) ?

9 (car $7 \times 9 = 63 = 2 \times 31 + 1$ )
4
15
22

Un indice

Applique l'algorithme d'Euclide étendu : $31 = 4 \times 7 + 3$ et $7 = 2 \times 3 + 1$ , puis remonte les égalités pour écrire $1 = 7u + 31v$ ; $u$ modulo $31$ est l'inverse cherché.

Voir la correction

Bonne réponse : A. 9 (car $7 \times 9 = 63 = 2 \times 31 + 1$ )

On cherche $x \in \mathbb{Z}$ tel que $7x - 31y = 1$ . L'algorithme d'Euclide donne : $31 = 4 \times 7 + 3$ , puis $7 = 2 \times 3 + 1$ . En remontant : $1 = 7 - 2 \times 3 = 7 - 2 \times (31 - 4 \times 7) = 9 \times 7 - 2 \times 31$ . Donc $9 \times 7 \equiv 1 \pmod{31}$ . L'inverse de 7 modulo 31 est donc 9.

Exercice 3 Protocole RSA et validité pour tout message

Palier 3 · approfondissement

Dans le cryptosystème RSA, on choisit deux nombres premiers distincts $p$ et $q$ , on pose $n = pq$ , et on choisit l'exposant de chiffrement $e$ premier avec $\varphi(n) = (p-1)(q-1)$ . L'exposant de déchiffrement $d$ vérifie $ed \equiv 1 \pmod{\varphi(n)}$ . Pourquoi a-t-on $m^{ed} \equiv m \pmod n$ pour TOUT message $m \in \mathbb{Z}/n\mathbb{Z}$ , même si $\mathrm{PGCD}(m, n) \ne 1$ ?

Car modulo $p$ , si $p \mid m$ alors $m^{ed} \equiv 0 \equiv m \pmod p$ , et si $p \nmid m$ le petit théorème de Fermat s'applique ; de même modulo $q$ , et on conclut par les restes chinois
Car $\varphi(n)$ est toujours impair
Car tout élément de $\mathbb{Z}/n\mathbb{Z}$ est inversible
Car $m^{ed} = m$ dans $\mathbb{Z}$ sans réduction modulaire

Un indice

Écrire $ed = 1 + k(p-1)(q-1)$ et distinguer les cas $p \mid m$ et $p \nmid m$ pour montrer $m^{ed} \equiv m \pmod p$ .

Voir la correction

Bonne réponse : A. Car modulo $p$ , si $p \mid m$ alors $m^{ed} \equiv 0 \equiv m \pmod p$ , et si $p \nmid m$ le petit théorème de Fermat s'applique ; de même modulo $q$ , et on conclut par les restes chinois

On a $ed = 1 + k(p-1)(q-1)$ .

Si $p \mid m$ , $m \equiv 0 \pmod p$ , donc $m^{ed} \equiv 0 \equiv m \pmod p$ .
Si $p \nmid m$ , par le petit théorème de Fermat $m^{p-1} \equiv 1 \pmod p$ , donc $m^{ed} = m \cdot (m^{p-1})^{k(q-1)} \equiv m \cdot 1 \equiv m \pmod p$ .

Dans les deux cas, $p \mid (m^{ed} - m)$ . De même, $q \mid (m^{ed} - m)$ . Comme $p$ et $q$ sont premiers entre eux, leur produit $n = pq$ divise $m^{ed} - m$ , c'est-à-dire $m^{ed} \equiv m \pmod n$ .

Exercice 4 Théorème des restes chinois et structure d'anneaux

Palier 4 · défi

Soient $m, n \in \mathbb{N}^*$ premiers entre eux. Quelle est la structure de l'anneau quotient $\mathbb{Z}/mn\mathbb{Z}$ d'après le théorème des restes chinois ?

L'application $\psi : x \bmod mn \mapsto (x \bmod m, x \bmod n)$ est un isomorphisme d'anneaux de $\mathbb{Z}/mn\mathbb{Z}$ sur $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$
$\mathbb{Z}/mn\mathbb{Z}$ est un corps fini
L'application $\psi$ est seulement un morphisme de groupes additifs non multiplicatif
$\mathbb{Z}/mn\mathbb{Z}$ est isomorphe à $\mathbb{Z}/m\mathbb{Z} + \mathbb{Z}/n\mathbb{Z}$

Un indice

Le noyau du morphisme canonique est $m\mathbb{Z} \cap n\mathbb{Z} = \mathrm{PPCM}(m, n)\mathbb{Z} = mn\mathbb{Z}$ car $\mathrm{PGCD}(m, n) = 1$ , et les cardinaux sont égaux.

Voir la correction

Bonne réponse : A. L'application $\psi : x \bmod mn \mapsto (x \bmod m, x \bmod n)$ est un isomorphisme d'anneaux de $\mathbb{Z}/mn\mathbb{Z}$ sur $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$

L'application $\psi : \mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ est un morphisme d'anneaux. Son noyau est $\ker(\psi) = m\mathbb{Z} \cap n\mathbb{Z}$ . Comme $\mathrm{PGCD}(m, n) = 1$ , $m\mathbb{Z} \cap n\mathbb{Z} = mn\mathbb{Z}$ . Par le premier théorème d'isomorphisme, $\bar{\psi} : \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ est un morphisme injectif. Comme les deux ensembles ont le même cardinal fini $mn$ , c'est un isomorphisme d'anneaux. En corollaire, pour le groupe des inversibles : $(\mathbb{Z}/mn\mathbb{Z})^\times \simeq (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$ , ce qui prouve la multiplicativité de l'indicateur d'Euler : $\varphi(mn) = \varphi(m)\varphi(n)$ .