Définition
Un nombre premier est un entier naturel supérieur à 1 qui n’admet exactement que deux diviseurs positifs distincts : 1 et lui-même. Cette propriété d’indécomposabilité fait des nombres premiers les « atomes » de l’arithmétique.
Les premiers nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…
2 est le seul nombre premier pair. Tous les autres sont impairs. Le nombre 1 n’est pas premier par convention (il ne possède qu’un seul diviseur distinct) — cette exclusion garantit l’unicité de la décomposition en facteurs premiers.
Nombres premiers
2, 3, 5, 7, 11, 13, 17, 19, 23…
Nombres composés
4=2², 6=2×3, 9=3², 15=3×5…
Cas particulier
1 — ni premier, ni composé (unité)
Histoire
Euclide — Les Éléments
Euclide démontre dans le Livre IX que les nombres premiers sont infinis (proposition 20). Il énonce aussi le théorème fondamental de l’arithmétique (unicité de la décomposition).
Eratosthène — Le Crible
Premier algorithme systématique pour déterminer tous les nombres premiers jusqu’à N. Encore utilisé en informatique sous des formes optimisées.
Fermat — Petit théorème
Si p est premier et a non divisible par p, alors ap−1 ≡ 1 (mod p). Fondement des tests de primalité modernes.
Goldbach — Lettre à Euler
Conjecture qu’il n’est à ce jour ni prouvée ni réfutée : tout entier pair supérieur à 2 est somme de deux nombres premiers.
Riemann — Hypothèse
Riemann formule son hypothèse sur les zéros de la fonction ζ(s). Elle encode la distribution des nombres premiers et reste l’un des sept problèmes du Millénaire (prix : 1 000 000 USD).
RSA — Cryptographie
Rivest, Shamir et Adleman publient l’algorithme RSA basé sur la difficulté de factoriser le produit de deux grands nombres premiers. Il protège la majorité des communications Internet.
Record GIMPS
Le plus grand nombre premier connu est M136279841 = 2136 279 841−1, un nombre de Mersenne à plus de 41 millions de chiffres, découvert par le projet GIMPS.
Propriétés fondamentales
Infinité
Il existe une infinité de nombres premiers. Preuve d’Euclide par l’absurde : si p1…pn étaient tous les premiers, le nombre P = p1×…×pn + 1 ne serait divisible par aucun d’eux — contradiction.
Théorème fondamental
Tout entier n > 1 se décompose de manière unique en produit de nombres premiers (ordre mis à part). Ex. : 360 = 23 × 32 × 5. Cette unicité est le fondement de toute l’arithmétique.
Critère de Wilson
p est premier si et seulement si (p−1)! ≡ −1 (mod p). Ex. : (5−1)! = 24 ≡ −1 (mod 5). Peu pratique mais élégant théoriquement.
Nombres de Mersenne
Un nombre de Mersenne est de la forme Mp = 2p−1 avec p premier. Tous les plus grands nombres premiers connus sont de ce type. M2=3, M3=7, M5=31, M7=127…
Nombres premiers jumeaux
Paires de premiers différant de 2 : (3,5), (5,7), (11,13), (17,19), (29,31)… La conjecture des jumeaux postule leur infinité — non prouvée. Zhang (2013) a montré l’infinité des paires à écart borné (< 70 millions, ramené à 246).
Théorème de Fermat
Un nombre premier de la forme 4k+1 est somme de deux carrés (5=1+4, 13=4+9…). Les premiers 4k+3 ne le sont pas. Ce résultat est à la base de la théorie des formes quadratiques.
Théorèmes majeurs
Le nombre de premiers ≤ x, noté π(x), est asymptotiquement équivalent à x/ln(x). Plus précisément, la fonction logarithme intégrale Li(x) = ∫2x dt/ln(t) en est une bien meilleure approximation.
Pour tout entier a et tout premier p, ap−a est divisible par p. Si pgcd(a,p)=1, alors ap−1 ≡ 1 (mod p). Base des tests de primalité probabilistes (Miller-Rabin).
Dans toute progression arithmétique a, a+q, a+2q… avec pgcd(a,q)=1, il y a une infinité de nombres premiers. Ex. : parmi 1, 11, 21, 31, 41… (progression de raison 10), il y a infiniment de premiers.
Les nombres premiers contiennent des progressions arithmétiques de longueur arbitraire. Ex. : 5, 11, 17, 23, 29 est une PA de longueur 5 et de raison 6. Ce théorème a valu la médaille Fields à Terence Tao (2006).
Répartition et crible
Le crible d’Ératosthène (vers 240 av. J.-C.) est le premier algorithme de l’histoire pour calculer tous les nombres premiers jusqu’à N. Son principe : barrer itérativement tous les multiples de chaque premier trouvé.
Les nombres premiers deviennent de plus en plus rares à mesure qu’on avance dans les entiers, mais ils ne disparaissent jamais. L’écart entre deux premiers consécutifs peut être arbitrairement grand (démontrable par N! + 2, N! + 3, … N! + N, tous composés).
Grandes conjectures ouvertes
Hypothèse de Riemann (1859)
Tous les zéros non triviaux de la fonction zêta de Riemann ζ(s) = ∑n=1∞ 1/ns ont leur partie réelle égale à 1/2. Elle implique la distribution la plus régulière possible des premiers. Prix Clay : 1 million de dollars. Des milliards de zéros ont été vérifiés numériquement, mais aucune preuve générale.
Conjecture de Goldbach (1742)
Tout entier pair > 2 est la somme de deux nombres premiers. Vérifiée jusqu’à 4 × 1018 par calcul informatique. La conjecture ternaire de Goldbach (tout impair > 5 = somme de 3 premiers) a été démontrée par Helfgott en 2013.
Conjecture des premiers jumeaux
Il existe une infinité de paires de premiers (p, p+2). Zhang (2013) a prouvé l’infinité de paires d’écart ≤ 246 (Maynard-Tao-Polymath). L’écart 2 reste hors de portée des méthodes actuelles.
Conjecture de Legendre
Entre deux carrés consécutifs n2 et (n+1)2, il existe toujours au moins un nombre premier. Vérifiée pour n très grands, mais non démontrée en général.
Cryptographie et applications
La sécurité d’une grande partie des communications Internet repose directement sur les nombres premiers, et plus précisément sur la difficulté de factoriser le produit de deux grands premiers.
Choisir deux grands premiers secrets p et q (512 à 4096 bits chacun). Calculer n = p × q (clé publique) et φ(n) = (p−1)(q−1).
Choisir e premier avec φ(n). Clé publique = (n, e). Message chiffré : c = me mod n.
Trouver d tel que e × d ≡ 1 mod φ(n). Clé privée = d. Message original : m = cd mod n.
Casser RSA-2048 requiert de factoriser n (~617 chiffres). Les meilleurs algorithmes connus prendraient des milliards d’années sur les ordinateurs classiques actuels.
Au-delà de RSA, les premiers interviennent dans la cryptographie sur courbes elliptiques (ECC), les protocoles Diffie-Hellman, les fonctions de hachage, et les preuves à divulgation nulle.
Records & curiosités
Curiosités
- Nombres de Sophie Germain : p premier tel que 2p+1 est aussi premier. Ex. : 2 (2×2+1=5), 3, 5, 11, 23… Utilisés en cryptographie.
- Nombres premiers répunit : formés uniquement de 1 en base 10 : 11, mais 111=3×37, 1111=11×101… très rares.
- Formule d’Euler : f(n) = n²+n+41 donne un premier pour n = 0 à 39, mais échoue pour n=40. Aucune formule polynomiale ne peut générer que des premiers.
- Nombre d’or des premiers : La spirale d’Ulam (1963) révèle des diagonales où les premiers s’alignent de manière étonnante, non encore totalement expliquée.
- Chanson de David Bowie : Le musicien avait une passion pour les nombres premiers et les intégraient dans certaines de ses compositions.