Nombres premiers

Les nombres premiers sont les « atomes » des entiers : tout entier se décompose, de façon unique, en produit de nombres premiers. Il y en a une infinité, leur répartition reste en partie mystérieuse, et ils protègent aujourd'hui nos communications grâce au chiffrement RSA.

  • Reconnaître un nombre premier, utiliser le crible d'Ératosthène
  • Démontrer que l'ensemble des nombres premiers est infini
  • Décomposer un entier en facteurs premiers et en tirer ses diviseurs
  • Utiliser le petit théorème de Fermat, comprendre le chiffrement RSA

Cours

1. Définition et premières propriétés

Un entier naturel $p$ est premier s'il admet exactement deux diviseurs positifs : $1$ et $p$. Ainsi $1$ n'est pas premier. Les premiers nombres premiers sont $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$

Un entier $n \geqslant 2$ non premier est dit composé : il s'écrit $n = ab$ avec $1 < a, b < n$.

(1) Tout entier $n \geqslant 2$ admet au moins un diviseur premier : son plus petit diviseur supérieur ou égal à 2.

(2) Si $n \geqslant 2$ est composé, il admet un diviseur premier $p$ tel que $p \leqslant \sqrt n$.

Preuve des propriétés (1) et (2).

(1) L'ensemble des diviseurs de $n$ supérieurs ou égaux à 2 contient $n$ : il a un plus petit élément $p$. Si $p$ n'était pas premier, il aurait un diviseur $d$ avec $1 < d < p$, qui diviserait aussi $n$ : contradiction avec la minimalité de $p$.

(2) Si $n$ est composé, $n = pk$ où $p$ est ce plus petit diviseur et $k \geqslant p$ (car $k \geqslant 2$ divise aussi $n$). Donc $n = pk \geqslant p^2$, soit $p \leqslant \sqrt n$. $\blacksquare$

Pour savoir si $n$ est premier, il suffit de tester sa divisibilité par les nombres premiers $p \leqslant \sqrt n$. Exemple : $401$ ; $\sqrt{401} \approx 20{,}02$ ; aucun des nombres $2, 3, 5, 7, 11, 13, 17, 19$ ne divise 401 : il est premier.

2. Une infinité de nombres premiers

Il existe une infinité de nombres premiers.

Raisonnons par l'absurde : supposons qu'il n'y ait qu'un nombre fini de nombres premiers, $p_1, p_2, \dots, p_k$. On considère $$N = p_1 \times p_2 \times \dots \times p_k + 1.$$

On a $N \geqslant 2$, donc $N$ admet un diviseur premier (propriété précédente). Ce diviseur est l'un des $p_i$. Alors $p_i$ divise $N$ et divise le produit $p_1p_2\cdots p_k$, donc il divise leur différence $N - p_1\cdots p_k = 1$. C'est impossible puisque $p_i \geqslant 2$.

L'hypothèse est fausse : il y a une infinité de nombres premiers. $\blacksquare$

$N$ n'est pas forcément premier : $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30\,031 = 59 \times 509$. La preuve dit seulement que ses facteurs premiers ne sont pas dans la liste.

3. Décomposition en facteurs premiers

Tout entier $n \geqslant 2$ s'écrit comme un produit de nombres premiers : $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ avec $p_1 < p_2 < \dots < p_k$ premiers et $\alpha_i \geqslant 1$. Cette écriture est unique.

Idée de la preuve.

Existence, par récurrence forte : si tous les entiers de $2$ à $n - 1$ se décomposent, alors soit $n$ est premier (il est sa propre décomposition), soit $n = ab$ avec $2 \leqslant a, b < n$, et on met bout à bout les décompositions de $a$ et $b$.

Unicité : si $p_1\cdots p_r = q_1\cdots q_s$ (produits de nombres premiers), alors $p_1$ divise $q_1(q_2\cdots q_s)$. D'après le corollaire du théorème de Gauss, $p_1$ divise $q_1$ ou $q_2\cdots q_s$, et de proche en proche, $p_1$ divise l'un des $q_j$, donc lui est égal (deux premiers). On simplifie par $p_1$ et on recommence. $\blacksquare$

Les diviseurs positifs de $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ sont les nombres $p_1^{\beta_1}\cdots p_k^{\beta_k}$ avec $0 \leqslant \beta_i \leqslant \alpha_i$. Il y en a $(\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_k + 1)$.

Le PGCD de deux entiers s'obtient en prenant pour chaque premier le plus petit exposant ; le PPCM avec le plus grand.

$360 = 2^3 \times 3^2 \times 5$ a $(3 + 1)(2 + 1)(1 + 1) = 24$ diviseurs positifs. Avec $84 = 2^2 \times 3 \times 7$ : $\mathrm{PGCD}(360, 84) = 2^2 \times 3 = 12$.

4. Petit théorème de Fermat

Soit $p$ un nombre premier.

  • Pour tout entier $a$ non divisible par $p$ : $\;a^{p-1} \equiv 1\ [p]$.
  • Pour tout entier $a$ : $\;a^p \equiv a\ [p]$.

Preuve par le binôme et une récurrence.

Étape 1. Pour $1 \leqslant k \leqslant p - 1$, $p$ divise $\binom pk$. En effet $k\binom pk = p\binom{p-1}{k-1}$, donc $p$ divise $k\binom pk$ ; comme $p$ est premier et $k < p$, $p$ est premier avec $k$ et le théorème de Gauss donne $p \mid \binom pk$.

Étape 2. Par la formule du binôme, $(a + 1)^p = a^p + \sum_{k=1}^{p-1}\binom pk a^k + 1 \equiv a^p + 1\ [p]$.

Étape 3. Récurrence sur $a \in \mathbb{N}$ : $0^p \equiv 0$ ; si $a^p \equiv a\ [p]$, alors $(a + 1)^p \equiv a^p + 1 \equiv a + 1\ [p]$. Pour $a$ négatif, on utilise $a \equiv r\ [p]$ avec $r$ le reste. Donc $a^p \equiv a\ [p]$ pour tout entier $a$.

Étape 4. Si $p \nmid a$ : $p$ divise $a^p - a = a(a^{p-1} - 1)$ et est premier avec $a$, donc (Gauss) $p \mid a^{p-1} - 1$. $\blacksquare$

Reste de $3^{2026}$ modulo 11 : 11 est premier et ne divise pas 3, donc $3^{10} \equiv 1\ [11]$. Comme $2026 = 10 \times 202 + 6$, $3^{2026} \equiv 3^6 = 729 \equiv 3\ [11]$ ($729 = 66 \times 11 + 3$).

Si l'on trouve un $a$ tel que $a^{n-1} \not\equiv 1\ [n]$ (avec $a$ premier avec $n$), alors $n$ n'est pas premier : $a$ est un témoin. La réciproque est fausse : les nombres de Carmichael comme $561 = 3 \times 11 \times 17$ trompent le test pour tous les $a$ premiers avec eux.

5. Chiffrement

  • Chiffrement affine : on remplace chaque lettre (A = 0, …, Z = 25) de rang $x$ par la lettre de rang $y \equiv ax + b\ [26]$. On peut déchiffrer si et seulement si $a$ est premier avec 26 : on utilise l'inverse de $a$ modulo 26.
  • RSA (1977) : on choisit deux grands nombres premiers $p$ et $q$, on publie $n = pq$ et un exposant $e$ premier avec $\varphi = (p - 1)(q - 1)$. On chiffre $m$ en $c \equiv m^e\ [n]$. Le destinataire, qui connaît $d$ inverse de $e$ modulo $\varphi$, déchiffre avec $m \equiv c^d\ [n]$.

La sécurité de RSA repose sur la difficulté de factoriser $n$ : multiplier deux nombres premiers de 300 chiffres est instantané, retrouver $p$ et $q$ à partir de leur produit est hors de portée des ordinateurs actuels.

def crible(N):
    est_premier = [True] * (N + 1)
    est_premier[0] = est_premier[1] = False
    p = 2
    while p * p <= N:
        if est_premier[p]:
            for m in range(p * p, N + 1, p):
                est_premier[m] = False
        p = p + 1
    return [k for k in range(N + 1) if est_premier[k]]

def decomposition(n):
    facteurs = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            facteurs.append(d)
            n = n // d
        d = d + 1
    if n > 1:
        facteurs.append(n)
    return facteurs

print(crible(100))
print(decomposition(360), decomposition(30031))

La preuve de l'infinité des nombres premiers se trouve dans les Éléments d'Euclide (livre IX). Fermat énonce son « petit » théorème dans une lettre à Frénicle en 1640, sans preuve ; Euler le démontre en 1736. Les records de taille sont presque toujours des nombres de Mersenne $2^p - 1$ : celui découvert en 2024 compte plus de 41 millions de chiffres.

Mini-jeux

Exercices

Les nombres $391$ et $401$ sont-ils premiers ?

$391 = 17 \times 23$ : composé. $401$ : premier (voir la méthode du cours).

Décomposer $2\,520$ en facteurs premiers. Combien a-t-il de diviseurs positifs ?

$2\,520 = 2^3 \times 3^2 \times 5 \times 7$ : $(3 + 1)(2 + 1)(1 + 1)(1 + 1) = 48$ diviseurs.

Déterminer le reste de $3^{100}$ dans la division par 7.

7 est premier et ne divise pas 3 : $3^6 \equiv 1\ [7]$. $100 = 6 \times 16 + 4$, donc $3^{100} \equiv 3^4 = 81 \equiv 4\ [7]$.

Avec $a = 360$ et $b = 588$, calculer $\mathrm{PGCD}(a, b)$ et $\mathrm{PPCM}(a, b)$ grâce aux décompositions. Vérifier que $\mathrm{PGCD} \times \mathrm{PPCM} = ab$.

$360 = 2^3 \times 3^2 \times 5$, $588 = 2^2 \times 3 \times 7^2$. PGCD $= 2^2 \times 3 = 12$ ; PPCM $= 2^3 \times 3^2 \times 5 \times 7^2 = 17\,640$. Et $12 \times 17\,640 = 211\,680 = 360 \times 588$.

Soit $p \geqslant 5$ un nombre premier. Montrer que $p^2 - 1$ est divisible par 24.

$p^2 - 1 = (p - 1)(p + 1)$. $p$ est impair : $p - 1$ et $p + 1$ sont deux pairs consécutifs, l'un est multiple de 4, donc le produit est divisible par 8. Parmi $p - 1, p, p + 1$, l'un est multiple de 3, et ce n'est pas $p$ : donc $3 \mid p^2 - 1$. Comme 3 et 8 sont premiers entre eux, $24 \mid p^2 - 1$.

Montrer que pour tout entier $n$, $n^{13} - n$ est divisible par 13, puis par 7.

13 est premier : $n^{13} \equiv n\ [13]$ (Fermat). Pour 7 : $n^7 \equiv n\ [7]$, donc $n^{13} = n^7 \times n^6 \equiv n \times n^6 = n^7 \equiv n\ [7]$.

Montrer que si $2^n - 1$ est premier, alors $n$ est premier. Indication : si $n = ab$, penser à $x^b - 1$ avec $x = 2^a$. La réciproque est-elle vraie ? (Tester $n = 11$.)

Si $n = ab$ avec $1 < a, b < n$, alors $2^n - 1 = x^b - 1 = (x - 1)(x^{b-1} + \dots + 1)$ avec $x = 2^a$ : $2^a - 1$ divise $2^n - 1$ et $1 < 2^a - 1 < 2^n - 1$, donc $2^n - 1$ n'est pas premier. La réciproque est fausse : $2^{11} - 1 = 2\,047 = 23 \times 89$.

On prend $p = 5$, $q = 11$, donc $n = 55$ et $\varphi = 40$. (a) Vérifier que $e = 3$ convient et que $d = 27$ est l'inverse de $e$ modulo 40. (b) Chiffrer $m = 2$. (c) Vérifier que le déchiffrement redonne 2, en calculant $8^{27}$ modulo 55 par carrés successifs.

(a) $\mathrm{PGCD}(3, 40) = 1$ et $3 \times 27 = 81 = 2 \times 40 + 1$. (b) $c \equiv 2^3 = 8\ [55]$. (c) $8^2 = 64 \equiv 9$ ; $8^4 \equiv 81 \equiv 26$ ; $8^8 \equiv 676 \equiv 16$ ; $8^{16} \equiv 256 \equiv 36\ [55]$. $27 = 16 + 8 + 2 + 1$ : $8^{27} \equiv 36 \times 16 \times 9 \times 8$. Or $36 \times 16 = 576 \equiv 26$, $26 \times 9 = 234 \equiv 14$, $14 \times 8 = 112 \equiv 2\ [55]$. On retrouve bien $m = 2$.