120 Anneaux $Z / n Z$ . Applications.

Anneaux $Z / n Z$ . Applications.

algebra

Soit $n \geq 2$ un entier.

L’anneau $Z / n Z$

Construction

GOU21

p. 9

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 $n$ 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 (Chinois). Soient $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 Z$ premiers entre eux, $φ (mn) = φ (m) φ (n)$

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

Proposition 22 (Petit théorème de Fermat). Pour tout entier relatif $a$ , pour tout $p$ premier, $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}{n} x \equiv 1 mod n$ .

p. 285

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

Théorème 33 (Chinois). Soient $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 / k Z$ pour tout $k \in [[1, r]]$ .

Les entiers $n_{1}, \dots, n_{r}$ sont premiers entre eux 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 Fermat). Soit $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 faible). Pour tout entier $n$ , il existe une infinité de nombres premiers congrus à $1$ modulo $n$ .

Irréductibilité de polynômes

GOZ

p. 10

Lemme 41 (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}$ , $γ (PQ) = γ (P) γ (Q)$ (où $γ (P)$ est le contenu du polynôme $P$ ).

Théorème 42 (Critère d’Eisenstein). Soit $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 doit a besoin de deux clés :

Une clé privée, qui est un couple de nombres premiers $(p, q)$ .
La clé publique correspondante, qui est le couple $(n, e)$ où $n = pq$ et $e$ est l’inverse de $d$ modulo $ϕ (n)$ où $d$ désigne un nombre premier à $ϕ (n)$ .

Nous conserverons ces notations pour la suite.

Théorème 47 (Chiffrement RSA). Soit $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^{'}$ : $m^{'} = (m_{i}^{e})_{i \in [[1, r]]}$
Possédant la clé privée, on peut déchiffrer le message $m^{'}$ pour reconstituer $m$ : $\forall i \in [[1, r]], (m_{i}^{e})^{d} \equiv d 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.