120 Anneaux $Z / n Z$ . Applications.

Anneaux $Z / n Z$ . Applications.

algebra

Soit $n \geq 2$ un entier.

L’anneau $Z / n Z$

Construction

Théorème 1

Division euclidienne dans $Z$ $\forall (a, b) \in Z^{2}, \exists! (q, r) \in Z^{2} tel que a = b q + r et r \in [[0, ∣ b ∣]]$

[ROM21]
p. 279

Définition 2

Soient $a, b \in Z$ . On dit que $a$ est congru à $b$ modulo $n$ si $n ∣ b - a$ . On note cela $a \equiv b mod n$ .

Proposition 3

Soient $a, b, c, d \in Z$ tels que $a \equiv b mod n$ et $c \equiv d mod n$ . Alors :

$a + c \equiv b + d mod n$ .
$a c \equiv b d mod n$

Lemme 4

Tout idéal de $Z$ est principal, de la forme $(n) = n Z$ .

Définition 5

Le quotient de l’anneau $Z$ par son idéal $n Z$ est l’anneau noté $Z / n Z$ . On note $\overline{a} = {a + q n ∣ q \in Z}$ l’image d’un élément $a \in Z$ dans $Z / n Z$ .

Remarque 6

Soient $a, b \in Z$ . $\overline{a} = \overline{b} ⟺ a \equiv b mod n$

Proposition 7

$Z / n Z = {\overline{0}, \dots, \overline{n - 1}}$ .
La compatibilité de $\equiv$ avec les lois $+$ et $\times$ sur $Z$ conjuguée à la remarque précédente transporte la structure d’anneau à $Z / n Z$ en posant, pour tout $\overline{a}, \overline{b} \in Z / n Z$ :
- $\overline{a} + \overline{b} = \overline{a + b}$ .
- $\overline{a} \overline{b} = \overline{ab}$ .

Le groupe multiplicatif

Générateurs

p. 283

Théorème 8

Soit $a \in Z$ . Les assertions suivantes sont équivalentes :

$\overline{a} \in (Z / n Z)^{\times}$ .
$pgcd (a, n) = 1$ .
$a$ est un générateur de $(Z / n Z, +)$ .

p. 301

Exemple 9

$(Z /4 Z)^{\times} = {\pm \overline{1}}$ .

p. 14

Proposition 10

$Z$ est monogène, l’ensemble de ses générateurs est $Z^{\times} = {\pm 1}$ .
$Z / n Z$ , l’ensemble de ses générateurs est $(Z / n Z)^{\times}$ .

Corollaire 11

Soit $G$ un groupe.

Si $G$ est monogène infini, alors $G ≅ Z$ .
Si $G$ est cyclique d’ordre $n$ , alors $G ≅ Z / n Z$ .

Exemple 12

Le groupe des racines $n$ -ièmes de l’unité, $μ_{n}$ , est isomorphe $Z / n Z$ via $\overline{k} \mapsto e^{\frac{2 ik π}{n}}$

Sous-groupes additifs et idéaux

p. 281

Théorème 13

Les sous-groupes additifs de $Z / n Z$ sont cycliques d’ordre divisant $n$ . Réciproquement, pour tout diviseur $d$ de $n$ , il existe un unique sous-groupe de $Z / n Z$ , c’est le groupe cyclique engendré par $\overline{\frac{n}{d}}$ .

p. 255

Théorème 14

Les idéaux de $Z / n Z$ sont ses sous-groupes additifs.
Les idéaux premiers de $Z / n Z$ sont les idéaux maximaux de $Z / n Z$ : ce sont les idéaux engendrés par $(\overline{p})$ où $p$ est un diviseur premier de $n$ .

Indicatrice d’Euler

p. 283

Définition 15

L’indicatrice d’Euler $φ$ est la fonction qui, à un entier $k$ , associe le nombre d’entiers compris entre $1$ et $k$ qui sont premiers avec $k$ .

Remarque 16

D’après le 8, $φ (n)$ est le nombre de générateurs de $Z / n Z$ et est également le cardinal de $(Z / n Z)^{\times}$ .

Exemple 17

Si $n$ est premier, $φ (n) = n - 1$ .
$φ (4) = 2$ d’après l’9.

[GOZ]
p. 4

Proposition 18

Pour tout $p$ premier et pour tout entier $n$ , $φ (p^{n}) = p^{n} - p^{n - 1}$

theoreme-chinois

Théorème 19

Théorème chinoisSoient $n$ et $m$ deux entiers premiers entre eux. Alors, $Z / nm Z \equiv Z / n Z \times Z / m Z$

Corollaire 20

$\forall m, n \in N^{*}$ premiers entre eux, $φ (mn) = φ (m) φ (n)$

Proposition 21

Théorème EulerPour tout entier relatif $a$ premier avec $n$ , $a^{φ (n)} \equiv 1 mod n$ .

Proposition 22

Petit théorème de FermatPour tout entier relatif $a$ et tout nombre premier $p$ tels que $p ∤ a$ , on a $a^{p - 1} \equiv 1 mod p$ .

Proposition 23

Pour tout entier naturel $n$ , $d ∣ n \sum φ (d) = n$

Cas où $n$ est premier

Structure de corps

Proposition 24

Les assertions suivantes sont équivalentes.

$n$ est un nombre premier.
$Z / n Z$ est intègre.
$Z / n Z$ est un corps.

p. 83

Théorème 25

Tout sous-groupe fini du groupe multiplicatif d’un corps commutatif est cyclique.

Corollaire 26

Si $p$ désigne un nombre premier, $(Z / p Z)^{\times}$ est cyclique.

[ROM21]
p. 294

Remarque 27

On a un résultat encore plus fort : $(Z / n Z)^{\times}$ est cyclique si et seulement si $n = 2, 4, p^{α} ou 2 p^{α}$ avec $p$ premier impair et $α \geq 1$ .

Carrés

p. 427

Remarque 28

Tout élément de $Z /2 Z$ est un carré.

Soit $p$ un nombre premier impair.

Théorème 29

Il y a $\frac{p - 1}{2}$ carrés et autant de non carrés dans $(Z / p Z)^{\times}$ .
Les carrés de $(Z / p Z)^{\times}$ sont les racines de $X^{\frac{p - 1}{2}} - 1$ et les non carrés celles de $X^{\frac{p - 1}{2}} + 1$ .

Corollaire 30

$- 1$ est un carré dans $(Z / p Z)^{\times}$ si et seulement si $p \equiv 1 mod 4$ .

Applications

Systèmes de congruences

p. 289

Proposition 31

Soit $a$ un entier non nul. L’équation $a x \equiv 1 mod n$ admet des solutions si et seulement si $pgcd (a, n) = 1$ .

Corollaire 32

Soient $a$ un entier non nul et $b$ un entier relatif. L’équation $a x \equiv b mod n$ a des solutions si et seulement si $d = pgcd (a, n) ∣ b$ . Dans ce cas, l’ensemble des solutions est ${\frac{b}{d} x_{0} + k \frac{n}{d} ∣ k \in Z}$ où $x_{0}$ est une solution de l’équation $\frac{a}{d} x \equiv 1 mod \frac{n}{d}$ .

p. 285

Pour résoudre des systèmes de congruences, on va préciser le 19.

Théorème 33

Théorème chinoisSoient $n_{1}, \dots, n_{r} \geq 2$ des entiers. On note $n = \prod_{i = 1}^{r} n_{i}$ et $π_{k} = π_{n_{k} Z}$ la surjection canonique de $Z$ sur $Z / n_{k} Z$ pour tout $k \in [[1, r]]$ .

Les entiers $n_{1}, \dots, n_{r}$ sont premiers entre eux deux à deux si et seulement si les anneaux $Z / n Z$ et $\prod_{i = 1}^{r} Z / n_{i} Z$ sont isomorphes. Dans ce cas, l’isomorphisme est explicité par l’application $ψ : Z / n Z π_{n} (k) \to \mapsto \prod_{i = 1}^{r} Z / n_{i} Z (π_{i} (k))_{i \in [[1, r]]}$

p. 291

Exemple 34

$⎩ ⎨ ⎧ k \equiv 2 mod 4 k \equiv 3 mod 5 k \equiv 1 mod 9$ admet pour ensemble de solutions ${838 + 180 q ∣ q \in Z}$ .

Étude d’équations diophantiennes

Entiers sommes de deux carrés

[I-P]
p. 137

Notation 35

On note $N : Z [i] a + ib \to \mapsto N a^{2} + b^{2}$ et $Σ$ l’ensemble des entiers qui sont somme de deux carrés.

Remarque 36

$n \in Σ ⟺ \exists z \in Z [i] tel que N (z) = n$ .

Théorème 37

Deux carrés de FermatSoit $n \in N^{*}$ . Alors $n \in Σ$ si et seulement si $v_{p} (n)$ est pair pour tout $p$ premier tel que $p \equiv 3 mod 4$ (où $v_{p} (n)$ désigne la valuation $p$ -adique de $n$ ).

Premiers congrus à $1$ modulo $n$

[GOU21]
p. 99

Notation 38

On note $Φ_{n}$ le $n$ -ième polynôme cyclotomique.

Lemme 39

Soient $a \in N$ et $p$ premier tels que $p ∣ Φ_{n} (a)$ mais $p ∤ Φ_{d} (a)$ pour tout diviseur strict $d$ de $n$ . Alors $p \equiv 1 mod n$ .

theoreme-de-dirichlet-faible

Théorème 40

Dirichlet faiblePour tout entier $n$ , il existe une infinité de nombres premiers congrus à $1$ modulo $n$ .

Irréductibilité de polynômes

[GOZ]
p. 10

Lemme 41

Lemme de Gauss

Le produit de deux polynômes primitifs est primitif (ie. dont le PGCD des coefficients est égal à $1$ ).
$\forall P, Q \in Z [X] ∖ {0}$ , $γ (P Q) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

Théorème 42

Critère d’EisensteinSoit $P = \sum_{i = 0}^{n} a_{i} X^{i} \in Z [X]$ de degré $n \geq 1$ . On suppose qu’il existe $p$ premier tel que :

$p ∣ a_{i}$ , $\forall i \in [[0, n - 1]]$ .
$p ∤ a_{n}$ .
$p^{2} ∤ a_{0}$ .

Alors $P$ est irréductible dans $Q [X]$ .

[PER]
p. 67

Application 43

Soit $n \in N^{*}$ . Il existe des polynômes irréductibles de degré $n$ sur $Z$ .

[GOZ]
p. 12

Théorème 44

Critère d’irréductibilité modulo $p$ Soit $P = \sum_{i = 0}^{n} a_{i} X^{i} \in Z [X]$ de degré $n \geq 1$ . Soit $p$ un premier. On suppose $p ∤ a_{n}$ .

Si $\overline{P}$ est irréductible dans $(Z / p Z) [X]$ , alors $P$ est irréductible dans $Q [X]$ .

Exemple 45

Le polynôme $X^{3} - 127 X^{2} + 3608 X + 19$ est irréductible dans $Z [X]$ .

Chiffrement RSA

[ULM18]
p. 62

Définition 46

Afin de chiffrer un message (tout entier découpé en séquence d’entiers de taille bornée) en utilisant RSA, on choisit deux nombres premiers distincts $p$ et $q$ , puis on pose $n = pq$ :

On choisit $e$ premier avec $φ (n)$ et on note $d$ son inverse modulo $φ (n)$ .
La clé publique est $(n, e)$ et la clé privée est $(n, d)$ ; les facteurs $p$ et $q$ doivent rester secrets.

Nous conserverons ces notations pour la suite.

Théorème 47

Chiffrement RSASoit $m = (m_{i})_{i \in [[1, r]]}$ un message où pour tout $i$ , $m_{i} < n$ .

Possédant la clé publique, on peut chiffrer ce message en un message $m^{'}$ , dont on note $m_{1}^{'}, \dots, m_{r}$ les coordonnées : $\forall i \in [[1, r]], m_{i}^{'} \equiv m_{i}^{e} mod n, 0 \leq m_{i}^{'} < n$
Possédant la clé privée, on peut déchiffrer le message $m^{'}$ pour reconstituer $m$ : $\forall i \in [[1, r]], (m_{i}^{'})^{d} \equiv m_{i} mod n$

Remarque 48

L’intérêt vient pour des premiers $p$ et $q$ très grands : il devient alors très compliqué de factoriser $n$ et d’obtenir la clé privée.
Les inverses peuvent se calculer à l’aide de l’algorithme de Bézout.