Les Nombres Premiers – webclasse.fr

📌 1. Définition et premiers exemples

Définition : Un entier naturel \(n \geq 2\) est dit premier s’il possède exactement deux diviseurs : \(1\) et \(n\) lui-même.

Si un entier \(n \geq 2\) possède au moins un diviseur différent de \(1\) et de lui-même, on dit qu’il est composé.

⚠️ Attention : 1 n’est pas premier – il n’a qu’un seul diviseur. Cette convention est essentielle pour que le théorème fondamental de l’arithmétique soit vrai.

Les 25 premiers nombres premiers (inférieurs à 100)

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

💡 2 est le seul nombre premier pair. Tout entier pair \(\geq 4\) est divisible par 2, donc composé.

Testeur interactif

Entrez un entier pour vérifier s’il est premier :

📜 2. Un peu d’histoire

Époque	Mathématicien / Événement	Contribution
~300 av. J.-C.	Euclide (Éléments)	Preuve de l’infinité des nombres premiers ; définition
~240 av. J.-C.	Ératosthène	Algorithme du crible
1644	Marin Mersenne	Étude des nombres de la forme \(2^p - 1\)
1736	Leonhard Euler	Démonstration que \(2^{31}-1\) est premier
1859	Bernhard Riemann	Hypothèse de Riemann sur la distribution des premiers
1896	Hadamard & de la Vallée-Poussin	Théorème des nombres premiers : \(\pi(n) \approx \dfrac{n}{\ln n}\)
1977	Rivest, Shamir, Adleman	Algorithme RSA : cryptographie à clé publique
2024	GIMPS	Plus grand premier connu : \(2^{136\,279\,841}-1\) (41 millions de chiffres !)

🧱 3. Théorème fondamental de l’arithmétique

Théorème : Tout entier \(n \geq 2\) se décompose de manière unique en produit de facteurs premiers (à l’ordre des facteurs près).

Les nombres premiers sont les « briques élémentaires » de tous les entiers.

Exemples

\(12 = 2^2 \times 3\)
\(360 = 2^3 \times 3^2 \times 5\)
\(1001 = 7 \times 11 \times 13\)
\(97 = 97\) (déjà premier)

Application : PGCD et PPCM

\(\text{PGCD}(a,b)\) : on prend le minimum des exposants communs.
\(\text{PPCM}(a,b)\) : on prend le maximum des exposants.

Exemple : \(\text{PGCD}(360,\,504) = 2^3 \times 3^2 = 72\) car \(504 = 2^3 \times 3^2 \times 7\).

∞ 4. Il y en a une infinité !

Euclide démontra vers 300 av. J.-C. qu’il existe une infinité de nombres premiers.

Preuve par l’absurde (Euclide) :

Supposons qu’il n’existe qu’un nombre fini de premiers : \(p_1, p_2, \ldots, p_k\).
Posons \(N = p_1 \times p_2 \times \cdots \times p_k + 1\).
En divisant \(N\) par l’un des \(p_i\), il reste toujours 1 : aucun \(p_i\) ne divise \(N\).
Pourtant \(N \geq 2\) admet un diviseur premier, différent de tous les \(p_i\).
Contradiction ! Donc il existe une infinité de nombres premiers. \(\blacksquare\)

Le théorème des nombres premiers

Si \(\pi(n)\) désigne le nombre de premiers \(\leq n\) :

\[\pi(n) \;\underset{n \to +\infty}{\sim}\; \frac{n}{\ln n}\]

📊 Il y a 25 premiers ≤ 100 | 168 premiers ≤ 1 000 | 1 229 premiers ≤ 10 000 | 78 498 premiers ≤ 1 000 000.

⚙️ 5. Algorithmes

5.1 – Tester si un entier est premier

Pour tester si \(n\) est premier, il suffit de chercher un diviseur \(d\) tel que \(2 \leq d \leq \sqrt{n}\). En effet, si \(n = a \times b\) avec \(a \leq b\), alors \(a \leq \sqrt{n}\).

Algorithme (langage naturel) :

Si \(n < 2\), répondre NON.
Pour \(d\) allant de \(2\) à \(\lfloor\sqrt{n}\rfloor\) :
Si \(d\) divise \(n\), répondre NON et s’arrêter.
Répondre OUI.

Code Python :

from math import sqrt

def est_premier(n):
    if n < 2:
        return False
    for d in range(2, int(sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

print(est_premier(97))   # True
print(est_premier(100))  # False

🕐 Complexité : cet algorithme est en \(\mathcal{O}(\sqrt{n})\). Suffisant pour de petits entiers.

5.2 – Liste des premiers jusqu’à \(n\) : Crible d’Ératosthène

Algorithme (langage naturel) :

Créer une liste booléenne premier[0..n], initialement tous à VRAI.
Poser premier[0] = premier[1] = FAUX.
Pour \(i\) de \(2\) à \(\lfloor\sqrt{n}\rfloor\) :
Si premier[i] est VRAI, marquer FAUX tous les multiples de \(i\) à partir de \(i^2\).
Les indices encore à VRAI sont les nombres premiers.

Code Python :

def crible_eratosthene(n):
    premier = [True] * (n + 1)
    premier[0] = premier[1] = False
    for i in range(2, int(n**0.5) + 1):
        if premier[i]:
            for j in range(i*i, n + 1, i):
                premier[j] = False
    return [i for i in range(n + 1) if premier[i]]

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

🕐 Complexité : \(\mathcal{O}(n \ln (\ln n))\), beaucoup plus efficace que tester chaque entier.

🎮 6. Crible d’Ératosthène interactif

Visualisez l’algorithme pas à pas. Cases bleues = premiers confirmés | rose = premier courant | orange = multiples éliminés.

Appuyez sur « Étape suivante » pour commencer.

🔐 7. Nombres premiers et cryptographie

Les nombres premiers sont au cœur de la sécurité informatique moderne. Vos connexions HTTPS, paiements en ligne et messageries chiffrées reposent sur eux.

Pourquoi les premiers ?

✅ Multiplier deux grands premiers \(p\) et \(q\) : rapide (millisecondes).
❌ Factoriser leur produit \(n = p \times q\) : infaisable si \(p, q\) ont des centaines de chiffres.

💻 Factoriser un nombre de 2048 bits prendrait, avec les meilleurs algorithmes actuels, des milliards d’années sur les ordinateurs classiques.

Les outils mathématiques nécessaires

Avant de comprendre pourquoi RSA fonctionne, il faut maîtriser deux notions.

Congruence : on dit que \(a\) est congru à \(b\) modulo \(n\), noté \(a \equiv b \pmod n\), lorsque \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\) (autrement dit, \(n\) divise \(a-b\)).

Indicatrice d’Euler \(\varphi(n)\) : le nombre d’entiers entre \(1\) et \(n\) qui sont premiers avec \(n\) (de PGCD 1 avec \(n\)).
Propriété clé : si \(p\) et \(q\) sont deux premiers distincts, alors \(\varphi(p \times q) = (p-1)(q-1)\).

💡 Cette formule vient du fait que, parmi les entiers de 1 à \(pq\), seuls les multiples de \(p\) (il y en a \(q\)) et les multiples de \(q\) (il y en a \(p\)) ne sont pas premiers avec \(pq\). En les retirant sans compter deux fois \(pq\) lui-même, il reste exactement \((p-1)(q-1)\) entiers premiers avec \(pq\).

Théorème d’Euler : si \(\text{PGCD}(m, n) = 1\), alors \(m^{\varphi(n)} \equiv 1 \pmod n\). C’est cette identité qui rend le déchiffrement de RSA possible.

Génération des clés RSA

Étape 1

Choisir \(p, q\)

Deux grands nombres premiers, gardés secrets

Étape 2

\(n = p \times q\)

Le module, rendu public

Étape 3

\(\varphi(n) = (p{-}1)(q{-}1)\)

Calculé en secret grâce à \(p\) et \(q\)

Étape 4

Choisir \(e\)

Tel que \(\text{PGCD}(e, \varphi(n)) = 1\) : exposant public

Étape 5

Calculer \(d\)

L’inverse de \(e\) modulo \(\varphi(n)\) : \(e \times d \equiv 1 \pmod{\varphi(n)}\)

Étape 6

Clés finales

Publique : \((n, e)\) — Privée : \((n, d)\)

Résumé en langage naturel :

On choisit deux grands nombres premiers \(p\) et \(q\), gardés secrets.
On calcule \(n = p \times q\) : ce sera le module, rendu public.
On calcule \(\varphi(n) = (p-1)(q-1)\), qui reste secret (il faut connaître \(p\) et \(q\) pour le calculer facilement).
On choisit un exposant \(e\) premier avec \(\varphi(n)\) (en pratique, souvent \(e = 65\,537\)).
On calcule \(d\), l’inverse de \(e\) modulo \(\varphi(n)\), grâce à l’algorithme d’Euclide étendu.
La clé publique \((n, e)\) sert à chiffrer ; la clé privée \((n, d)\) sert à déchiffrer.

Chiffrer et déchiffrer

Un message est d’abord transformé en un (ou plusieurs) entier(s) \(m\) vérifiant \(0 \leq m < n\).

Chiffrement (avec la clé publique \((n,e)\)) : \(\quad c \equiv m^{e} \pmod n\)
Déchiffrement (avec la clé privée \((n,d)\)) : \(\quad m \equiv c^{d} \pmod n\)

🔐 Seule la personne qui connaît \(d\) – donc \(p\) et \(q\) – peut remonter de \(c\) à \(m\). Or retrouver \(p\) et \(q\) à partir de \(n\) seul revient à factoriser \(n\), ce qui est infaisable pour de grands nombres.

Pourquoi le déchiffrement fonctionne-t-il ?

Démonstration (cas où \(m\) est premier avec \(n\)) :

Par construction, \(e \times d \equiv 1 \pmod{\varphi(n)}\), donc il existe un entier \(k\) tel que \(e \times d = 1 + k\,\varphi(n)\).
On calcule : \(c^{d} \equiv (m^{e})^{d} = m^{ed} = m^{1 + k\varphi(n)} = m \times \left(m^{\varphi(n)}\right)^{k} \pmod n\).
Or, d’après le théorème d’Euler, \(m^{\varphi(n)} \equiv 1 \pmod n\) (car \(m\) et \(n\) sont premiers entre eux).
Il reste donc \(c^{d} \equiv m \times 1^{k} \equiv m \pmod n\). \(\blacksquare\)

📚 En toute rigueur, il faut aussi traiter le cas où \(m\) n’est pas premier avec \(n\) (multiple de \(p\) ou de \(q\)) : on utilise alors le théorème des restes chinois, mais la conclusion \(c^d \equiv m \pmod n\) reste vraie.

Exemple détaillé, pas à pas

On prend de petits premiers pour pouvoir calculer à la main (en réalité, \(p\) et \(q\) auraient des centaines de chiffres) :

1 – Choix des premiers : \(p = 5\), \(q = 11\).
2 – Module : \(n = p \times q = 55\).
3 – Indicatrice d’Euler : \(\varphi(n) = (5-1)(11-1) = 4 \times 10 = 40\).
4 – Exposant public : on choisit \(e = 3\) car \(\text{PGCD}(3, 40) = 1\). Clé publique : \((55,\,3)\).

5 – Calcul de l’exposant privé \(d\) par l’algorithme d’Euclide étendu : on cherche \(d\) tel que \(3d \equiv 1 \pmod{40}\).

Division euclidienne : \(40 = 13 \times 3 + 1\).
On isole le reste : \(1 = 40 - 13 \times 3\).
Donc \((-13) \times 3 \equiv 1 \pmod{40}\), soit \(d \equiv -13 \equiv 27 \pmod{40}\).
Vérification : \(3 \times 27 = 81 = 2 \times 40 + 1\). ✓

Clé privée : \((55,\, 27)\).

6 – Chiffrement du message \(m = 2\) :

\(c = m^{e} \bmod n = 2^{3} \bmod 55 = 8\).

7 – Déchiffrement de \(c = 8\) : il faut calculer \(8^{27} \bmod 55\). Calculer directement \(8^{27}\) donnerait un nombre énorme – on utilise l’exponentiation rapide (« par carrés successifs »), qui ne demande que quelques multiplications.

Puissance de 8	Calcul	Résultat mod 55
\(8^1\)	—	8
\(8^2\)	\(8 \times 8 = 64\)	9
\(8^4\)	\(9^2 = 81\)	26
\(8^8\)	\(26^2 = 676\)	16
\(8^{16}\)	\(16^2 = 256\)	36

On écrit l’exposant en base 2 : \(27 = 16 + 8 + 2 + 1\). Il suffit donc de multiplier les puissances correspondantes : \[8^{27} = 8^{16} \times 8^{8} \times 8^{2} \times 8^{1} \equiv 36 \times 16 \times 9 \times 8 \pmod{55}\]

\(36 \times 16 = 576 \equiv 26 \pmod{55}\)
\(26 \times 9 = 234 \equiv 14 \pmod{55}\)
\(14 \times 8 = 112 \equiv 2 \pmod{55}\)

✅ On retrouve bien \(8^{27} \bmod 55 = 2 = m\) : le message initial est parfaitement reconstitué !

Et en pratique ?

Les vrais \(p\) et \(q\) ont plusieurs centaines de chiffres (clés de 2048 ou 4096 bits).
L’exposant public est presque toujours \(e = 65\,537 = 2^{16}+1\), un choix qui accélère le chiffrement.
Un vrai message (texte, image…) est découpé en blocs numériques, et des schémas de remplissage (padding, comme OAEP) empêchent certaines attaques.
En pratique, RSA sert surtout à échanger une clé symétrique (AES), plus rapide pour chiffrer de gros volumes de données.

Et demain ? L’informatique quantique…

L’algorithme de Shor (1994), exécuté sur un ordinateur quantique suffisamment puissant, factoriserait efficacement de grands entiers, rendant RSA obsolète. C’est pourquoi les cryptographes développent déjà des systèmes post-quantiques.

✨ 8. Curiosités et familles spéciales

🔵 Nombres de Mersenne

Forme \(2^p - 1\). Ex : \(2^7 - 1 = 127\). Le plus grand premier connu (2024) est \(2^{136\,279\,841} - 1\) : plus de 41 millions de chiffres !

👫 Premiers jumeaux

Paires \((p, p+2)\) toutes deux premières. Ex : (11, 13), (17, 19), (29, 31). On conjecture qu’il en existe une infinité.

🍸 Sophie Germain

\(p\) est un premier de Sophie Germain si \(2p+1\) est aussi premier. Ex : \(11 \to 23\). Ils jouent un rôle en cryptographie.

🏅 Nombres de Fermat

Forme \(2^{2^n}+1\). Fermat les croyait tous premiers, mais \(2^{2^5}+1 = 641 \times 6\,700\,417\) !

🌈 Premiers de Wieferich

Vérifient \(2^{p-1} \equiv 1 \pmod{p^2}\). Seuls deux sont connus : 1093 et 3511. Mystérieux et rarissimes.

🌐 GIMPS

Great Internet Mersenne Prime Search : projet collaboratif où tout le monde peut participer à la chasse aux records de grands premiers !

🚪 9. Problèmes encore ouverts

Après des siècles de recherche, les nombres premiers gardent encore des secrets profonds :

Conjecture de Goldbach (1742)
Tout entier pair \(\geq 4\) est la somme de deux nombres premiers.
Ex : \(28 = 11 + 17\), \(100 = 3 + 97\). Vérifiée jusqu’à \(4 \times 10^{18}\)… mais non démontrée.

Conjecture des premiers jumeaux
Il existerait une infinité de paires \((p, p+2)\) premières. Non démontrée, malgré de récents progrès (Zhang, 2013 ; Maynard, 2014).

Hypothèse de Riemann (1859)
Concerne la distribution précise des nombres premiers via la fonction zêta de Riemann. C’est l’un des 7 Problèmes du Millénaire, dotés d’un prix d’1 million de dollars. Non résolue après 165 ans de travaux.

💬 Ces problèmes montrent qu’en mathématiques, des questions simples à formuler peuvent résister à l’humanité entière pendant des siècles.