Sciences · Mathématiques
Les nombres premiers
Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts : 1 et lui-même. Les premiers sont 2, 3, 5, 7, 11, 13… Il en existe une infinité.
Mis à jour le 5 min de lecture
Les nombres premiers sont les « atomes » de l’arithmétique : tout entier supérieur à 1 se décompose de manière unique en un produit de nombres premiers. Étudiés depuis Euclide, ils recèlent encore des mystères célèbres, et ils protègent aujourd’hui les paiements en ligne et les communications chiffrées.
Les nombres premiers jusqu’à 100
Il y en a 25 :
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
| Intervalle | Nombre de premiers |
|---|---|
| 1 à 10 | 4 |
| 1 à 100 | 25 |
| 1 à 1 000 | 168 |
| 1 à 10 000 | 1 229 |
| 1 à 1 000 000 | 78 498 |
Remarques :
- 1 n’est pas premier : il n’a qu’un seul diviseur. Cette convention garantit l’unicité de la décomposition en facteurs premiers.
- 2 est le seul nombre premier pair ; tous les autres sont impairs.
- Les nombres premiers se raréfient en moyenne, mais irrégulièrement.
Comment savoir si un nombre est premier ?
Les critères de divisibilité
| Divisible par | Si… | Exemple |
|---|---|---|
| 2 | le dernier chiffre est pair | 358 |
| 3 | la somme des chiffres est divisible par 3 | 471 (4 + 7 + 1 = 12) |
| 5 | le dernier chiffre est 0 ou 5 | 1 245 |
| 9 | la somme des chiffres est divisible par 9 | 7 281 (7 + 2 + 8 + 1 = 18) |
| 11 | la différence entre la somme des chiffres de rang pair et celle de rang impair est divisible par 11 | 2 728 (2 − 7 + 2 − 8 = −11) |
La méthode des divisions successives
Pour tester un nombre n, il suffit d’essayer de le diviser par les nombres premiers inférieurs ou égaux à √n. Si aucun ne le divise, n est premier. En effet, si n = a × b avec a ≤ b, alors a ≤ √n.
Le crible d’Ératosthène
Attribué au savant grec Ératosthène (IIIe siècle av. J.-C.), il donne tous les nombres premiers jusqu’à une limite N :
- Écrire tous les entiers de 2 à N.
- Entourer 2 et barrer tous ses multiples (4, 6, 8…).
- Entourer le premier nombre non barré (3) et barrer ses multiples.
- Recommencer avec 5, 7… jusqu’à √N.
- Les nombres non barrés sont premiers.
La décomposition en facteurs premiers
Théorème fondamental de l’arithmétique : tout entier supérieur ou égal à 2 s’écrit comme un produit de nombres premiers, et cette écriture est unique à l’ordre des facteurs près.
Applications :
- simplifier une fraction :
84 / 360 = (2² × 3 × 7) / (2³ × 3² × 5) = 7 / 30(voir les fractions) ; - PGCD (plus grand commun diviseur) : produit des facteurs communs avec le plus petit exposant ;
- PPCM (plus petit commun multiple) : produit de tous les facteurs avec le plus grand exposant, utile pour le dénominateur commun.
Il existe une infinité de nombres premiers
La démonstration d’Euclide (Éléments, livre IX, vers 300 av. J.-C.) est l’une des plus élégantes des mathématiques. Supposons qu’il n’y ait qu’un nombre fini de premiers p₁, p₂, …, pₙ. Considérons N = p₁ × p₂ × … × pₙ + 1. Divisé par n’importe lequel des pᵢ, N laisse un reste de 1. Donc aucun pᵢ ne divise N. Or N, supérieur à 1, a au moins un diviseur premier : celui-ci ne figure pas dans la liste. Contradiction : la liste ne peut pas être complète.
Répartition et grandes questions
- Théorème des nombres premiers (démontré en 1896 par Hadamard et de La Vallée Poussin) : le nombre de premiers inférieurs à x est proche de
x / ln(x). Autour d’un nombre x, environ un nombre sur ln(x) est premier. - Nombres premiers jumeaux : couples de premiers séparés de 2 (3 et 5, 11 et 13, 17 et 19, 41 et 43). On conjecture qu’il y en a une infinité ; ce n’est pas démontré.
- Conjecture de Goldbach (1742) : tout nombre pair supérieur à 2 est la somme de deux nombres premiers (
28 = 5 + 23 = 11 + 17). Vérifiée par ordinateur jusqu’à 4 × 10¹⁸, elle reste non démontrée. - Hypothèse de Riemann (1859) : elle concerne la répartition fine des nombres premiers. C’est l’un des sept « problèmes du millénaire » de l’Institut Clay, doté d’un million de dollars.
Records et nombres de Mersenne
Les plus grands nombres premiers connus sont des nombres de Mersenne, de la forme 2ᵖ − 1 (avec p premier), du nom du moine Marin Mersenne (XVIIe siècle). Il existe pour eux un test de primalité très efficace (test de Lucas-Lehmer). Le projet collaboratif GIMPS en découvre régulièrement de nouveaux ; le record établi en octobre 2024, 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1, compte plus de 41 millions de chiffres.
À quoi servent les nombres premiers ?
Le chiffrement RSA (Rivest, Shamir, Adleman, 1977) repose sur un fait simple : multiplier deux grands nombres premiers est facile, mais retrouver ces facteurs à partir de leur produit est extrêmement long pour un ordinateur classique quand le produit compte plusieurs centaines de chiffres. Ce principe sécurise depuis des décennies une part importante des échanges sur Internet, des cartes bancaires et des signatures électroniques. Un ordinateur quantique suffisamment puissant pourrait le casser (algorithme de Shor, 1994), d’où le développement de la cryptographie dite post-quantique.
Questions fréquentes
Pourquoi 1 n’est-il pas un nombre premier ?
Parce qu’il n’a qu’un seul diviseur (lui-même). S’il était premier, la décomposition en facteurs premiers ne serait plus unique : 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3…
0 et 2 sont-ils premiers ?
0 n’est pas premier (il est divisible par tous les entiers). 2 est premier : ses seuls diviseurs sont 1 et 2. C’est le plus petit et le seul pair.
Existe-t-il une formule qui donne tous les nombres premiers ?
Aucune formule simple et pratique n’est connue. Des formules théoriques existent, mais elles sont plus lentes que le simple crible.
Quel est le plus grand nombre premier ?
Il n’y en a pas, puisqu’il en existe une infinité. Le plus grand nombre premier connu est 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1, découvert en octobre 2024.