121 Nombres premiers. Applications.

Nombres premiers. Applications.

algebra

Généralités

Nombres premiers et premiers entre eux

Définition 1. Soient $a, b \in Z$ . On dit que $a$ divise $b$ (ou que $b$ est un multiple de $a$ ), et on note $a ∣ b$ s’il existe $n \in Z$ tel que $b = an$ . Dans le cas contraire, on note $a ∤ b$ .

Théorème 2 (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 ∣]]$

Définition 3. Soient $a_{1}, \dots, a_{n} \in Z$ . Par principalité de $Z$ , il existe un unique $d \in N$ tel que $a_{1} Z + \dots + a_{n} Z = d Z$ Ainsi défini, $d$ s’appelle le pgcd de $a_{1}, \dots, a_{n}$ et on note $d = pgcd (a_{1}, \dots, a_{n})$ .

Remarque 4. Dans la définition précédente, $d$ est le plus entier naturel divisant tous les $a_{i}$ .

Définition 5. Soient $a_{1}, \dots, a_{n} \in Z$ . Lorsque $pgcd (a_{1}, \dots, a_{n}) = 1$ , on dit que $a_{1}, \dots, a_{n}$ sont premiers entre eux dans leur ensemble. Lorsque $pgcd (a_{i}, a_{j}) = 1$ dès que $i \neq = j$ , on dit que $a_{1}, \dots, a_{n}$ sont premiers entre eux deux à deux.

Théorème 6 (Bézout). Soient $a_{1}, \dots, a_{n} \in Z$ . $pgcd (a_{1}, \dots, a_{n}) = 1 ⟺ \exists u_{1}, \dots, u_{n} \in Z tels que i = 1 \sum n u_{i} a_{i} = 1$

Théorème 7 (Gauss). Soient $a, b, c \in Z$ . $a ∣ b c et pgcd (a, b) = 1 ⟹ a ∣ c$

[ROM21]
p. 304

Définition 8. On dit qu’un entier naturel $p$ est premier s’il est supérieur ou égal à $2$ et si ses seuls diviseurs positifs sont $1$ et $p$ .

Exemple 9. Les nombres de Fermat $F_{n} = 2^{2^{n}} + 1$ sont premiers pour $n \in [[0, 4]]$ , mais pas pour $n \in [[5, 32]]$ .

Théorème 10 (Euclide). L’ensemble $P$ des nombres premiers est infini.

Théorème 11 (Fondamental de l’arithmétique). Tout entier naturel $n \geq 2$ se décompose de manière unique sous la forme : $n = k = 1 \prod r p_{k}^{α_{k}}$ où les $p_{k}$ sont des nombres premiers distincts et où les $α_{k}$ sont des entiers naturels non nuls.

[GOU21]
p. 11

Proposition 12.

Si $n = \prod_{i = 1}^{k} p_{i}^{α_{i}}$ et $m = \prod_{i = 1}^{k} p_{i}^{β_{i}}$ , alors $pgcd (n, m) = \prod_{i = 1}^{k} p_{i}^{i n f (α_{i}, β_{i})}$ .
Soient $p \in P$ et $k \in [[1, p - 1]]$ . Alors $p ∣ (k p)$ .

Théorème 13 (Fermat). Soient $p \in P$ et $a \in Z$ . Alors :

$a^{p} \equiv a mod p$ .
$p ∤ a ⟹ a^{p - 1} \equiv 1 mod p$ .

Fonctions arithmétiques

[GOZ]
p. 3

Définition 14. On définit :

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$ .
La fonction de Möbius, notée $μ$ , par $μ : Z n \to \mapsto Z ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 si n = 1 si n = p_{1} \dots p_{k} avec p_{1}, \dots, p_{k} premiers distincts sinon$

Proposition 15.

$\forall m, n \in Z$ premiers entre eux, $φ (mn) = φ (m) φ (n)$ .
Pour tout entier relatif $a$ premier avec $n$ , $a^{φ (n)} \equiv 1 mod n$ .
Pour tout entier naturel $n$ , $\sum_{d ∣ n} φ (d) = n$ .

p. 89

Théorème 16 (Formule d’inversion de Möbius). Soient $f$ et $g$ des fonctions de $N^{*}$ dans $C$ telles que $\forall n \in N^{*}, f (n) = \sum_{d ∣ n} g (d)$ . Alors, $\forall n \in N^{*}, g (n) = d ∣ n \sum μ (d) f (\frac{n}{d})$

Corollaire 17. $\forall n \in N^{*}, φ (n) = d ∣ n \sum d μ (\frac{n}{d})$

Répartition des nombres premiers

p. 67

Définition 18. L’ensemble des générateurs de $μ_{n}$ , noté $μ_{n}^{*}$ , est formé des racines primitives $n$ -ièmes de l’unité.

Proposition 19.

$μ_{n}^{*} = {e^{\frac{2 ikπ}{n}} ∣ k \in [[0, n - 1]], pgcd (k, m) = 1}$ .
$∣ μ_{n}^{*} ∣ = φ (n)$ , où $φ$ désigne l’indicatrice d’Euler.

Définition 20. On appelle $n$ -ième polynôme cyclotomique le polynôme $Φ_{n} = ξ \in μ_{n}^{*} \prod (X - ξ)$

Théorème 21.

$X^{n} - 1 = \prod_{d ∣ n} Φ_{d}$ .
$Φ_{n} \in Z [X]$ .
$Φ_{n}$ est irréductible sur $Q$ .

Corollaire 22. Le polynôme minimal sur $Q$ de tout élément $ξ$ de $μ_{n}^{*}$ est $Φ_{n}$ . En particulier, $[Q (ξ) : Q] = φ (m)$

[GOU21]
p. 99

theoreme-de-dirichlet-faible

Théorème 23 (Dirichlet faible). Pour tout entier $n$ , il existe une infinité de nombres premiers congrus à $1$ modulo $n$ .

Remarque 24. La version forte de ce théorème est que, pour tout entiers naturels $a$ , $b$ non nuls, il existe une infinité de nombres premiers de la forme $ak + b$ , $k \in N$ .

p. 16

Théorème 25 (des nombres premiers). Si $x > 0$ , on note $π (x)$ le nombre de nombres premiers inférieurs à $x$ . Alors, $π (x) \sim \frac{x}{ln ( x )}$

Théorie des corps

Corps finis

[GOZ]
p. 3

Proposition 26. Les conditions suivantes sont équivalentes :

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

Notation 27. On note $F_{p} = Z / p Z$ .

p. 7

Définition 28. Soit $A$ un anneau. L’application $f_{A} : Z n \to \mapsto A n fois 1 + \dots + 1$ On note $car (A)$ l’unique $n \in N$ tel que $Ker (f_{A}) = n Z$ : c’est la caractéristique de $A$ .

Proposition 29.

Soit $A$ un anneau intègre. Alors, $car (A) = 0 ou p$ avec $p$ premier.
Soit $A$ un anneau fini. Alors, $car (A) \neq = 0$ et $car (A) ∣ ∣ A ∣$ .
Un anneau et un quelconque de ses sous-anneaux ont la même caractéristique.

Remarque 30.

Le Point 1 est en particulier vrai pour un corps.
Si $car (A) = 0$ , $A$ est infini.

p. 81

Proposition 31. Soit $K$ un corps fini.

$car (K)$ est un nombre premier $p$ .
Le sous-corps premier de $K$ est isomorphe à $F_{p}$ .
$∣ K ∣ = p^{n}$ pour $n \geq 2$ .

Proposition 32. Soit $K$ un corps de caractéristique $p$ . L’application $Frob : K x \to \mapsto K x^{p}$ est un morphisme de corps.

Si $K$ est fini, c’est un automorphisme.
Si $K = F_{p}$ , c’est l’identité.

Théorème 33. Soient $p \in P$ et $n \in N^{*}$ . On pose $q = p^{n}$ . Alors :

Il existe un corps $K$ à $q$ éléments : c’est le corps de décomposition de $X^{q} - X$ sur $F_{p}$ .
$K$ est unique à isomorphisme près : on le note $F_{q}$ .

Corollaire 34 (Théorème de Wilson). Soit $n \geq 2$ un entier. Alors, $n est premier ⟺ (n - 1)! + 1 \equiv 0 mod n$

[PER]
p. 74

Théorème 35. $F_{q}^{*}$ est cyclique, isomorphe à $Z / (q - 1) Z$ .

Remarque 36. En fait, tout sous-groupe fini du groupe multiplicatif d’un corps commutatif est cyclique.

[GOU21]
p. 100

Théorème 37 (Wedderburn). Tout corps fini est commutatif.

Carrés dans les corps finis

[GOZ]
p. 93

Soit $q = p^{n}$ avec $p$ premier et $n \geq 2$ .

Proposition 38. On note $F_{q}^{2} = {x^{2} ∣ x \in F_{q}}$ et $F_{q}^{* 2} = F_{q}^{2} \cap F_{q}^{*}$ . Alors $F_{q}^{* 2}$ est un sous-groupe de $F_{q}^{*}$ .

Proposition 39.

Si $p = 2$ , $F_{q}^{2} = F_{q}$ , donc $F_{q}^{* 2} = F_{q}^{*}$ .
Si $p > 2$ , alors :
- $F_{q}^{* 2}$ est le noyau de l’endomorphisme de $F_{q}^{*}$ défini par $x \mapsto x^{\frac{q - 1}{2}}$ .
- $F_{q}^{* 2}$ est un sous-groupe d’indice $2$ de $F_{q}^{*}$ .
- $∣ F_{q}^{* 2} ∣ = \frac{q - 1}{2}$ et $∣ F_{q}^{2} ∣ = \frac{q + 1}{2}$ .
- $(- 1) \in F_{q}^{* 2} ⟺ q \equiv 1 mod 4$ .

[I-P]
p. 203

Notation 40. Soit $a \in F_{p}$ . On note $(\frac{a}{p})$ le symbole de Legendre de $a$ modulo $p$ . On a ainsi $(\frac{a}{p}) = \pm 1$ avec $(\frac{a}{p}) = 1$ si et seulement si $a \in F_{p}^{2}$ .

Application 41 (Frobenius-Zolotarev). Soient $p \geq 3$ un nombre premier et $V$ un espace vectoriel sur $F_{p}$ de dimension finie. $\forall u \in GL (V), ϵ (u) = (\frac{det ( u )}{p})$ où $u$ est vu comme une permutation des éléments de $V$ .

Réduction modulo $p$

Le résultat suivant justifie que l’on s’intéresse aux polynômes irréductibles en théorie des corps.

[GOZ]
p. 57

Théorème 42. Soit $P \in K [X]$ un polynôme irréductible sur un corps $K$ .

Il existe un corps de rupture de $P$ .
Si $L = K [α]$ et $L^{'} = K [β]$ sont deux corps de rupture de $P$ , alors il existe un unique $K$ -isomorphisme $φ : L \to L^{'}$ tel que $φ (α) = β$ .
$K [X] / (P)$ est un corps de rupture de $P$ .

p. 10

Lemme 43 (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$ ).

critere-d-eisenstein

Théorème 44 (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 45. Soit $n \in N^{*}$ . Il existe des polynômes irréductibles de degré $n$ sur $Z$ .

[GOZ]
p. 12

Théorème 46 (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 47. Le polynôme $X^{3} - 127 X^{2} + 3608 X + 19$ est irréductible dans $Z [X]$ .

Autres applications en algèbre

Entiers sommes de deux carrés

[I-P]
p. 137

Notation 48. 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 49. $n \in Σ ⟺ \exists z \in Z [i] tel que N (z) = n$ .

Théorème 50 (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$ ).

En théorie des groupes

[ROM21]
p. 22

Soit $G$ un groupe fini opérant sur un ensemble fini $X$ .

Définition 51. On dit que $G$ est un $p$ -groupe s’il est d’ordre une puissance d’un nombre premier $p$ .

Théorème 52 (Formule des classes). Soit $Ω$ un système de représentants des orbites de l’action de $G$ sur $X$ . Alors, $∣ X ∣ = ω \in Ω \sum ∣ G \cdot ω ∣ = ω \in Ω \sum (G : Stab_{G} (ω)) = ω \in Ω \sum \frac{∣ G ∣}{∣ Stab _{G} ( ω ) ∣}$

Corollaire 53. Soit $p$ un nombre premier. Si $G$ est un $p$ -groupe opérant sur $X$ , alors, $∣ X^{G} ∣ \equiv ∣ X ∣ mod p$ où $X^{G}$ désigne l’ensemble des points fixes de $X$ sous l’action de $G$ .

Corollaire 54. On note $G \cdot h_{1}, \dots, G \cdot h_{r}$ les classes de conjugaison de $G$ . Alors, $∣ G ∣ = ∣ Z (G) ∣ + i = 1 ∣ G \cdot h_{i} ∣ = 2 \sum r ∣ G \cdot h_{i} ∣ = ∣ Z (G) ∣ + i = 1 ∣ G \cdot h_{i} ∣ = 2 \sum r \frac{∣ G ∣}{∣ Stab _{G} ( h _{i} ) ∣}$

Corollaire 55. Soit $p$ un nombre premier. Le centre d’un $p$ -groupe non trivial est non trivial.

Corollaire 56. Soit $p$ un nombre premier. Un groupe d’ordre $p^{2}$ est toujours abélien.

Application 57 (Théorème de Cauchy). On suppose $G$ non trivial et fini. Soit $p$ un premier divisant l’ordre de $G$ . Alors il existe un élément d’ordre $p$ dans $G$ .

[GOU21]
p. 44

Application 58 (Premier théorème de Sylow). On suppose $G$ fini d’ordre $n p^{α}$ avec $n, α \in N$ et $p$ premier tel que $p ∤ n$ . Alors, il existe un sous-groupe de $G$ d’ordre $p^{α}$ .

RSA

[ULM18]
p. 62

Définition 59. 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 60 (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 61.

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.