Comment savoir rapidement si un entier $n$ est premier ?

On teste la divisibilité de $n$ par les nombres premiers $p$ tels que $p \leq \sqrt n$. Si aucun ne divise $n$, alors $n$ est premier. En effet, si $n = ab$ avec $1 < a \leq b$, alors $a^2 \leq ab = n$, donc $a \leq \sqrt n$, et $a$ possède un diviseur premier lui aussi inférieur à $\sqrt n$. Pour $199$ : $\sqrt{199} \approx 14{,}1$, on teste $2, 3, 5, 7, 11, 13$ ; aucun ne divise 199, qui est donc premier. Pour $91$ : $7 \mid 91$, donc 91 n'est pas premier.

Pourquoi la démonstration d'Euclide ne prouve-t-elle pas que $p_1p_2\cdots p_k + 1$ est premier ?

Elle prouve seulement que ce nombre $N$ n'est divisible par aucun des premiers $p_1, \ldots, p_k$ (le reste vaut 1). Comme $N \geq 2$ admet au moins un diviseur premier, ce diviseur est un nouveau nombre premier, ce qui contredit l'hypothèse « il n'y a que $k$ nombres premiers ». Par exemple $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$ n'est pas premier, mais ses facteurs premiers sont bien nouveaux.

À quoi sert l'unicité de la décomposition en facteurs premiers ?

Elle permet de lire sur la décomposition toutes les propriétés de divisibilité : les diviseurs de $n = \prod p_i^{\alpha_i}$ sont les $\prod p_i^{\beta_i}$ avec $0 \leq \beta_i \leq \alpha_i$, leur nombre est $\prod(\alpha_i + 1)$, le PGCD de deux nombres s'obtient avec les exposants minimaux. Elle sert aussi dans des démonstrations : $\sqrt2$ est irrationnel car dans $a^2 = 2b^2$ l'exposant de 2 serait pair à gauche et impair à droite.

Nombres premiers

Définitions

Définition 1 — nombre premier. Un entier naturel $p$ est premier s’il admet exactement deux diviseurs positifs : $1$ et $p$ . Un entier $n \geq 2$ non premier est dit composé. Ainsi $0$ et $1$ ne sont pas premiers, et $2$ est le seul nombre premier pair. Premiers inférieurs à 50 : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ .

Définition 2 — décomposition en facteurs premiers. Décomposer un entier $n \geq 2$ en facteurs premiers, c’est l’écrire sous la forme $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \qquad (p_1 < p_2 < \cdots < p_k \text{ premiers},\ \alpha_i \geq 1).$ Exemples : $360 = 2^3 \times 3^2 \times 5$ ; $1001 = 7 \times 11 \times 13$ ; $97 = 97$ (un nombre premier est sa propre décomposition).

Théorèmes et propriétés

Théorème 1 (existence d’un diviseur premier). (démonstration exigible) Tout entier $n \geq 2$ admet au moins un diviseur premier. Si $n$ est composé, il admet un diviseur premier $p \leq \sqrt n$ .

Idée de la démonstration : le plus petit diviseur $p \geq 2$ de $n$ est premier (sinon un diviseur de $p$ plus petit diviserait $n$ ). Si $n = pq$ est composé avec $p$ minimal, alors $q \geq p$ , donc $p^2 \leq pq = n$ , soit $p \leq \sqrt n$ .

Théorème 2 (critère de primalité). Si un entier $n \geq 2$ n’est divisible par aucun nombre premier $p \leq \sqrt n$ , alors $n$ est premier. C’est la contraposée du Théorème 1 : elle limite les tests de divisibilité à $\sqrt n$ .

Théorème 3 (infinité des nombres premiers). (démonstration exigible — Euclide) L’ensemble des nombres premiers est infini.

Démonstration : par l’absurde, supposons qu’il n’y ait qu’un nombre fini de premiers $p_1, \ldots, p_k$ et posons $N = p_1p_2\cdots p_k + 1$ . La division de $N$ par chaque $p_i$ a pour reste $1$ , donc aucun $p_i$ ne divise $N$ ; or $N \geq 2$ admet un diviseur premier (Théorème 1), nécessairement absent de la liste : contradiction. Attention : $N$ n’est pas forcément premier ( $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$ ), ses facteurs premiers sont seulement « nouveaux ».

Théorème 4 (corollaire de Gauss). Si $p$ est premier et $p \mid ab$ , alors $p \mid a$ ou $p \mid b$ . En particulier, si $p$ est premier et $p \nmid a$ , alors $\text{PGCD}(a, p) = 1$ , et si un premier divise un produit de nombres premiers, il est égal à l’un d’eux.

Théorème 5 (théorème fondamental de l’arithmétique). (démonstration exigible) Tout entier $n \geq 2$ admet une décomposition en facteurs premiers, et cette écriture est unique à l’ordre des facteurs près.

Existence : récurrence forte ( $n$ premier, ou $n = ab$ avec $a, b < n$ déjà décomposés). Unicité : si $p_1\cdots p_r = q_1\cdots q_s$ , le Théorème 4 montre que $p_1$ est l’un des $q_j$ ; on simplifie et on recommence. Application : $\sqrt 2$ est irrationnel, car dans $a^2 = 2b^2$ l’exposant de $2$ serait pair à gauche et impair à droite.

Théorème 6 (diviseurs et PGCD). Soit $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ . Les diviseurs positifs de $n$ sont les $p_1^{\beta_1}\cdots p_k^{\beta_k}$ avec $0 \leq \beta_i \leq \alpha_i$ ; leur nombre est $d(n) = (\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_k + 1).$ Le PGCD de deux entiers s’obtient avec les facteurs premiers communs affectés de l’exposant minimal ; deux entiers sont premiers entre eux si et seulement s’ils n’ont aucun facteur premier commun. Enfin, $n$ est un carré parfait si et seulement si tous ses exposants $\alpha_i$ sont pairs.

Théorème 7 (petit théorème de Fermat). (démonstration exigible) Soit $p$ un nombre premier.

Si $a$ est un entier non divisible par $p$ , alors $a^{p-1} \equiv 1 \ [p]$ .
Pour tout entier $a$ : $a^p \equiv a \ [p]$ .

Idée de la démonstration : les restes de $a, 2a, \ldots, (p-1)a$ modulo $p$ sont $1, 2, \ldots, p-1$ dans un certain ordre (Théorème 4) ; en multipliant, $(p-1)!\,a^{p-1} \equiv (p-1)! \ [p]$ , et on simplifie par $(p-1)!$ , premier avec $p$ . La réciproque est fausse : $2^{340} \equiv 1 \ [341]$ alors que $341 = 11 \times 31$ .

Méthodes

Méthode 1 — tester la primalité d’un entier.

Calculer $\sqrt n$ et lister les nombres premiers $p \leq \sqrt n$ .
Tester la divisibilité de $n$ par chacun d’eux (critères de divisibilité par $2$ , $3$ , $5$ , puis divisions).
Conclure : si aucun ne divise $n$ , alors $n$ est premier (Théorème 2) ; sinon $n$ est composé.

Exemple : $199$ : $\sqrt{199} \approx 14{,}1$ , on teste $2, 3, 5, 7, 11, 13$ ; aucun ne divise $199$ , qui est premier. $91 = 7 \times 13$ est composé.

def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:          # diviseurs jusqu'a racine de n
        if n % d == 0:
            return False
        d += 1
    return True

Méthode 2 — dresser la liste des premiers par le crible d’Ératosthène.

Écrire les entiers de $2$ à $n$ .
Entourer le plus petit nombre non barré $p$ (il est premier) et barrer tous ses multiples à partir de $p^2$ (les plus petits sont déjà barrés).
Recommencer tant que $p \leq \sqrt n$ (Théorème 2) : les nombres non barrés sont les premiers.

Exemple : pour $n = 50$ , on barre les multiples de $2$ , $3$ , $5$ , $7$ (car $7^2 = 49 \leq 50 < 11^2$ ) ; il reste les 15 premiers listés dans la Définition 1.

def crible(n):
    """Liste des nombres premiers <= n (crible d'Eratosthene)."""
    premier = [True] * (n + 1)
    premier[0] = premier[1] = False
    p = 2
    while p * p <= n:
        if premier[p]:
            for m in range(p * p, n + 1, p):   # on barre les multiples de p
                premier[m] = False
        p += 1
    return [k for k in range(n + 1) if premier[k]]

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

Méthode 3 — décomposer un entier en facteurs premiers.

Diviser $n$ par $2$ tant que c’est possible, puis par $3$ , puis par les premiers suivants.
S’arrêter quand le quotient vaut $1$ (ou quand le quotient restant est premier : c’est le dernier facteur).
Regrouper les facteurs en puissances (Définition 2) ; l’écriture obtenue est unique (Théorème 5).

Exemple : $360 \xrightarrow{\div 2} 180 \xrightarrow{\div 2} 90 \xrightarrow{\div 2} 45 \xrightarrow{\div 3} 15 \xrightarrow{\div 3} 5 \xrightarrow{\div 5} 1$ , donc $360 = 2^3 \times 3^2 \times 5$ .

def decomposition(n):
    """Liste des (p, alpha) de la decomposition de n >= 2."""
    facteurs = []
    d = 2
    while d * d <= n:
        alpha = 0
        while n % d == 0:
            n //= d
            alpha += 1
        if alpha > 0:
            facteurs.append((d, alpha))
        d += 1
    if n > 1:                     # le reste est un facteur premier
        facteurs.append((n, 1))
    return facteurs

print(decomposition(360))   # [(2, 3), (3, 2), (5, 1)]

Méthode 4 — compter les diviseurs et calculer un PGCD.

Décomposer le ou les entiers en facteurs premiers (Méthode 3).
Nombre de diviseurs : multiplier les $(\alpha_i + 1)$ (Théorème 6).
PGCD : garder les facteurs premiers communs avec l’exposant minimal (Théorème 6).

Exemple : $360 = 2^3 \times 3^2 \times 5$ a $(3+1)(2+1)(1+1) = 24$ diviseurs ; avec $84 = 2^2 \times 3 \times 7$ , $\text{PGCD}(360, 84) = 2^2 \times 3 = 12$ .

Méthode 5 — calculer un reste avec le petit théorème de Fermat.

Vérifier que le module $p$ est premier et que $p \nmid a$ : alors $a^{p-1} \equiv 1 \ [p]$ (Théorème 7).
Écrire l’exposant $n = (p-1)q + r$ (division euclidienne par $p - 1$ ).
Conclure : $a^n = (a^{p-1})^q \times a^r \equiv a^r \ [p]$ , puis réduire $a^r$ modulo $p$ .

Exemple : reste de $3^{100}$ par $7$ : $3^6 \equiv 1 \ [7]$ et $100 = 6 \times 16 + 4$ , donc $3^{100} \equiv 3^4 = 81 \equiv 4 \ [7]$ .

Méthode 6 — montrer qu’un entier n’est pas premier avec un témoin de Fermat.

Choisir un entier $a$ premier avec $n$ (souvent $a = 2$ ).
Calculer $a^{n-1}$ modulo $n$ (par puissances successives).
Si $a^{n-1} \not\equiv 1 \ [n]$ , alors $n$ n’est pas premier (contraposée du Théorème 7) : $a$ est un témoin. Si $a^{n-1} \equiv 1 \ [n]$ , on ne peut rien conclure : la réciproque est fausse ( $341 = 11 \times 31$ et les nombres de Carmichael comme $561 = 3 \times 11 \times 17$ ).

Exemple : $2^8 = 256 = 28 \times 9 + 4 \not\equiv 1 \ [9]$ , donc $9$ n’est pas premier ( $a = 2$ est un témoin). Ce test probabiliste, répété avec plusieurs témoins, est utilisé en pratique (RSA).

Définitions

Théorèmes et propriétés

Méthodes

Reste informé