Nombres premiers et petit théorème de Fermat

Ce que tu sais déjà. Tu sais utiliser les congruences (Divisibilité, division euclidienne et congruences) et les théorèmes de Bézout et de Gauss (PGCD, Bézout et Gauss). Les nombres premiers sont les « atomes » des entiers : tout entier se construit à partir d’eux, et leur étude sert aujourd’hui à sécuriser les paiements en ligne.

1. Nombres premiers

Définition. Un entier naturel $p$ est premier s’il admet exactement deux diviseurs positifs : $1$ et lui-même. $0$ et $1$ ne sont pas premiers. Les premiers nombres premiers sont $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$…

Propriété. Tout entier $n \geqslant 2$ admet au moins un diviseur premier : son plus petit diviseur $d \geqslant 2$ est premier. Si de plus $n$ n’est pas premier, ce plus petit diviseur vérifie $d \leqslant \sqrt n$.

Justification. Si $d$ n’était pas premier, il aurait un diviseur $d'$ avec $1 < d' < d$, qui diviserait aussi $n$ : contradiction. Si $n = d \times e$ avec $d \leqslant e$, alors $d^2 \leqslant de = n$.

Crible d’Ératosthène. Pour obtenir tous les nombres premiers jusqu’à $N$, on écrit les entiers de $2$ à $N$ ; on garde $2$ et on barre ses multiples, on garde le premier nombre non barré ($3$) et on barre ses multiples, etc. On peut s’arrêter dès que le nombre gardé dépasse $\sqrt N$.

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

print(crible(50))   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

→ S’entraîner : Exercice 1

2. Une infinité de nombres premiers

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

Attention. $N$ n’est pas forcément premier : $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30\,031 = 59 \times 509$. Mais ses facteurs premiers ($59$ et $509$) sont nouveaux.

→ S’entraîner : Exercice 2

3. Décomposition en produit de facteurs premiers

Lemme d’Euclide. Si un nombre premier $p$ divise un produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$.

Justification. Si $p$ ne divise pas $a$, alors $\text{PGCD}(p\,;\,a) = 1$ (les seuls diviseurs positifs de $p$ sont $1$ et $p$) ; par le théorème de Gauss, $p$ divise $b$.

Théorème fondamental de l’arithmétique. Tout entier $n \geqslant 2$ s’écrit comme un produit de nombres premiers : $$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_k^{\alpha_k},$$ avec $p_1 < p_2 < \dots < p_k$ premiers et $\alpha_i \geqslant 1$ entiers. Cette écriture est unique.

Idée. L’existence vient de la propriété du § 1 : on extrait un facteur premier, puis on recommence avec le quotient (qui diminue). L’unicité découle du lemme d’Euclide : un premier qui divise un produit de premiers est égal à l’un d’eux.

Applications. Si $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ :

• les diviseurs positifs de $n$ sont les $p_1^{\beta_1} \dots p_k^{\beta_k}$ avec $0 \leqslant \beta_i \leqslant \alpha_i$ ; il y en a $(\alpha_1 + 1)(\alpha_2 + 1) \dots (\alpha_k + 1)$ ;
• le PGCD de deux entiers s’obtient en prenant les facteurs premiers communs, avec le plus petit exposant.

Exemples. $360 = 2^3 \times 3^2 \times 5$ a $(3 + 1)(2 + 1)(1 + 1) = 24$ diviseurs positifs. $252 = 2^2 \times 3^2 \times 7$, donc $\text{PGCD}(360\,;\,252) = 2^2 \times 3^2 = 36$.

def decomposition(n):
    facteurs = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            facteurs[p] = facteurs.get(p, 0) + 1
            n //= p
        p += 1
    if n > 1:
        facteurs[n] = facteurs.get(n, 0) + 1
    return facteurs

print(decomposition(360))   # {2: 3, 3: 2, 5: 1}

→ S’entraîner : Exercice 3 · Exercice 4

4. Petit théorème de Fermat

Théorème (Fermat, 1640). Soit $p$ un nombre premier et $a$ un entier.

• Si $p$ ne divise pas $a$, alors $a^{p - 1} \equiv 1\ [p]$.
• Pour tout entier $a$, $a^p \equiv a\ [p]$.

Exemples.

• $13$ est premier et ne divise pas $2$ : $2^{12} \equiv 1\ [13]$. Donc $2^{2027} = (2^{12})^{168} \times 2^{11} \equiv 2^{11} = 2\,048 \equiv 7\ [13]$ ($2\,027 = 12 \times 168 + 11$ et $2\,048 = 13 \times 157 + 7$).
• Pour tout entier $n$, $n^7 - n$ est divisible par $7$.

Test de Fermat. Si $a^{n-1} \not\equiv 1\ [n]$ pour un $a$ premier avec $n$, alors $n$ n’est pas premier. La réciproque est fausse : $561 = 3 \times 11 \times 17$ vérifie $a^{560} \equiv 1\ [561]$ pour tout $a$ premier avec $561$ (c’est un nombre de Carmichael).

→ S’entraîner : Exercice 5 · Exercice 6 · Exercice 7

À retenir.

• $p$ premier : exactement deux diviseurs positifs. Un entier $n \geqslant 2$ non premier a un diviseur premier $\leqslant \sqrt n$.
• Il y a une infinité de nombres premiers (démonstration par l’absurde avec $p_1 \dots p_k + 1$).
• Lemme d’Euclide : $p \mid ab \Rightarrow p \mid a$ ou $p \mid b$. Décomposition unique $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$.
• Nombre de diviseurs : $(\alpha_1 + 1) \dots (\alpha_k + 1)$ ; PGCD : facteurs communs, plus petits exposants.
• Fermat : $p$ premier, $p \nmid a$ $\Rightarrow$ $a^{p-1} \equiv 1\ [p]$ ; toujours $a^p \equiv a\ [p]$.