Voir la source de Nombre premier

[[Fichier:Primencomposite0100.svg|vignette|Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge.]]
[[Fichier:Nombrepremier 2017.png|vignette|Le nombre [[7 (nombre)|7]] est premier car il admet exactement deux diviseurs positifs distincts.]]

Un '''nombre premier''' est un [[entier naturel]] qui admet exactement deux [[Divisibilité|diviseurs]] distincts entiers et [[nombre positif|positifs]] : 1 et le nombre considéré lui-même. Puisque tout nombre a pour diviseurs 1 et lui-même, comme le montre l’égalité <math>n=n\times 1</math>, les nombres premiers sont ceux qui n'ont pas d'autre diviseur. Par exemple, le nombre entier 7 est premier car 1 et 7 sont ses seuls diviseurs entiers et positifs. Tout nombre pair étant multiple de 2, les nombres premiers sont tous impairs, excepté le nombre 2 lui-même. De plus, tout nombre se terminant par 5 étant un multiple de 5, les nombres premiers (sauf 2 et 5) se terminent tous par 1, 3, 7 ou 9.

Par opposition, on appelle [[nombre composé]] tout nombre entier qui est le produit de deux entiers strictement supérieurs à 1 et possède de ce fait au moins trois diviseurs ; sont composés, par exemple, 4&nbsp;=&nbsp;2&nbsp;×&nbsp;2 qui en possède 3 (à savoir 1, 2 et 4), 9&nbsp;=&nbsp;3&nbsp;×&nbsp;3 qui en possède 3 (à savoir 1, 3 et 9) et 12&nbsp;=&nbsp;2&nbsp;×&nbsp;2&nbsp;×&nbsp;3 qui en possède 6 (à savoir 1, 2, 3, 4, 6 et 12).

Selon cette définition, les nombres [[Zéro|0]] et [[1 (nombre)|1]] ne sont donc ni premiers ni composés : 1 n'est pas premier car il n'a qu'un seul diviseur entier positif et 0 non plus car il est divisible par tous les entiers positifs. Durant une relativement courte période de l'Histoire, de la fin du {{sp-|XVII|au début du|XX}}, certains mathématiciens, grâce à une définition légèrement différente des nombres premiers, ont considéré que [[1 (nombre)|1]] était premier. Mais au début du {{s-|XX}}, un consensus a abouti à la définition donnée ici, qui exclut 1 des nombres premiers<ref>C. K. Caldwell, A. Reddick, Y. Xiong, W. Keller. ''The history of the primality of one : a selection of sources.'' Journal of Integer sequences, Vol. 15, 2012, Article 12.9.8. [https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html]
</ref>, en particulier pour garantir un énoncé simple du [[théorème fondamental de l'arithmétique]].

Les vingt-cinq nombres premiers inférieurs à [[100 (nombre)|100]] sont :
{{Retrait| [[2 (nombre)|2]], [[3 (nombre)|3]], [[5 (nombre)|5]], [[7 (nombre)|7]], [[11 (nombre)|11]], [[13 (nombre)|13]], [[17 (nombre)|17]], [[19 (nombre)|19]], [[23 (nombre)|23]], [[29 (nombre)|29]], [[31 (nombre)|31]], [[37 (nombre)|37]], [[41 (nombre)|41]], [[43 (nombre)|43]], [[47 (nombre)|47]], [[53 (nombre)|53]], [[59 (nombre)|59]], [[61 (nombre)|61]], [[67 (nombre)|67]], [[71 (nombre)|71]], [[73 (nombre)|73]], [[79 (nombre)|79]], [[83 (nombre)|83]], [[89 (nombre)|89]], et [[97 (nombre)|97]].}}

De telles [[Liste de nombres premiers|listes de nombres premiers]] inférieurs à une borne donnée, ou compris entre deux bornes, peuvent être obtenues grâce à diverses méthodes de calcul. Mais il ne peut pas y avoir de liste exhaustive finie des nombres premiers, car on sait (depuis l'[[Antiquité]] : voir [[Théorème d'Euclide sur les nombres premiers]]) qu'il en existe une infinité. On ne connaît d’ailleurs pas de [[Formules pour les nombres premiers|formules simples pour produire de telles listes]] ; la recherche de formules approchées a amené à l’important [[théorème des nombres premiers]].

La notion de nombre premier est une notion de base en [[arithmétique]] élémentaire : le [[théorème fondamental de l'arithmétique]] assure qu'un nombre composé est [[Décomposition en produit de facteurs premiers|factorisable]] en un produit de nombres premiers, et que cette factorisation est unique à l'ordre des facteurs près. Elle admet des généralisations importantes, mais délicates, dans des branches des mathématiques plus avancées, comme la [[théorie algébrique des nombres]], qui prennent ainsi à leur tour l'appellation d'arithmétique. Par ailleurs, de nombreuses applications industrielles de l'arithmétique reposent sur la connaissance [[algorithme|algorithmique]] des nombres premiers, et parfois plus précisément sur la difficulté des problèmes algorithmiques qui leur sont liés ; c'est le cas de certains systèmes [[cryptographie|cryptographiques]] et des méthodes de [[théorie de l'information|transmission de l'information]]. Les nombres premiers sont aussi utilisés pour construire des [[table de hachage|tables de hachage]] et pour constituer des [[générateur de nombres pseudo-aléatoires|générateurs de nombres pseudo-aléatoires]].

Découvert le {{Date-|21|octobre|2024}}, le [[plus grand nombre premier connu]] est le [[#Nombres premiers de Mersenne|nombre premier de Mersenne]] <math>2^{136\,279\,841}-1</math>, qui comporte plus de {{nobr|41 millions}} de chiffres en [[Développement décimal|écriture décimale]].

== Éléments historiques ==
Les entailles retrouvées sur l'[[os d'Ishango]] daté à plus de {{unité|20000|ans}} avant notre ère, mis au jour par l'archéologue [[Jean de Heinzelin de Braucourt]]<ref>Voir [[Marcus du Sautoy]], ''[[La Symphonie des nombres premiers]]'', {{p.|42}}.</ref> et antérieur à l'apparition de l'[[écriture]] (antérieur à {{unité|3200|ans}} {{av JC}}), semblent isoler quatre groupes de valeurs : 11, 13, 17 et 19. Certains archéologues l'interprètent comme la preuve de la connaissance des nombres premiers. Toutefois, il existe trop peu de découvertes permettant de cerner les connaissances réelles de cette période ancienne<ref>{{Lien web|url=http://irem.univ-reunion.fr/IMG/pdf/Keller_prehistoire_geometrie.pdf|titre=Préhistoire de la géométrie : le problème des sources|auteur=Olivier Keller}}.</ref>.

Des [[Tablette d'argile|tablettes d'argile]] séchées attribuées aux civilisations qui se sont succédé en [[Mésopotamie]] durant le {{-m|II|e}} montrent la résolution de problèmes arithmétiques et attestent des premières connaissances de l'époque. Les calculs nécessitaient de connaître des tables d'inverses d'entiers (les ''réciproques'') dont certaines ont été retrouvées. Dans le [[système sexagésimal]] utilisé par la [[Babylone|civilisation babylonienne]] pour écrire les entiers, les réciproques des diviseurs des puissances de 60 (''nombres réguliers'') se calculent facilement : par exemple, diviser par 24, c'est multiplier par 2 × 60 + 30 (= 150) puis décaler la virgule de deux rangs vers la droite (soit diviser par 60{{2}}), puisque <math>\frac{1}{24}=\frac{150}{60^2}</math>. Leur connaissance nécessitait une bonne compréhension de la multiplication, de la division. Dans les [[Mathématiques dans l'Égypte antique|mathématiques égyptiennes]], le calcul fractionnaire demandait aussi des connaissances sur les opérations et les divisions d’entiers. Les textes mathématiques égyptiens ne notaient que certaines fractions, en particulier celles correspondant actuellement aux inverses d’entiers (<math>\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\ldots </math>) ; l’écriture des fractions se faisait en additionnant ces « inverses d'entiers », si possible sans répétition (<math>\frac 1 2 +\frac 1 6</math> au lieu de <math>\frac 1 3 +\frac 1 3</math>)<ref>{{Ouvrage|auteur1=Paul Benoit|directeur1=oui|auteur2=Karine Chemla|auteur3=Jim Ritter|titre=Histoire des fractions, fractions d'histoire|éditeur=Birkhäuser|année=1992|isbn=|directeur2=oui |directeur3=oui |lieu=Bâle}}.</ref>. Mais il n'y a pas de trace de factorisation d'entiers ou de nombres premiers dans ces textes<ref>Kawai Lui remarque aussi [http://hub.hku.hk/bitstream/10722/30464/15/FullText.pdf?accept=1 dans sa thèse] {{en}} qu'en dépit de compétences techniques bien supérieures, il ne semble pas que les nombres premiers (ni d'ailleurs les [[conique]]s) aient été remarqués en Chine avant le {{s|XVII}}, lorsque les missionnaires occidentaux les firent connaître.</ref>.

La première trace incontestable de la présentation des nombres premiers remonte à l'Antiquité (vers [[300 av. J.-C.]]), et se trouve dans les ''[[Éléments (Euclide)|Éléments]]'' d’[[Euclide]] (livres [[Livre VII des Éléments d'Euclide|VII]] à [[Livre IX des Éléments d'Euclide|IX]]). Euclide donne une définition des nombres premiers, la preuve de leur infinité, la définition du [[plus grand commun diviseur]] (pgcd) et du [[plus petit commun multiple]] (ppcm), et les algorithmes pour les déterminer, aujourd’hui appelés algorithmes d’Euclide. Il est possible que les connaissances présentées soient antérieures.
{{Clr}}

=== Jalons symboliques ===
L'esprit ludique et l'émulation ont amené des mathématiciens à définir des seuils de gigantisme pour les nombres premiers{{Référence nécessaire}}, exprimés en nombre de chiffres en [[base dix]]. Parmi ces records, battus ou à battre, on notera en particulier :
* les ''[[Nombre premier titanesque|nombres premiers titanesques]]'' ({{lang|en|''titanic primes''}}), au-delà de mille chiffres,
* les ''[[Nombre premier gigantesque|nombres premiers gigantesques]]'' ({{lang|en|''gigantic primes''}}), au-delà de dix mille chiffres,
* les ''[[Méga-nombre premier|méga-nombres premiers]]'' ({{lang|en|''megaprimes''}}), au-delà d'un million de chiffres.

En {{date-|2021}}, {{unité|plus de mille|''méga-nombres''}} ''premiers'' étaient connus<ref>{{en}} Chris Caldwell, [http://primes.utm.edu/primes/lists/short.txt The Largest Known Primes] at The [[Prime Pages]].<!--Retrieved on 2013-01-05.--></ref>. Le premier à être découvert fut, en 1999, le [[#Nombres premiers de Mersenne|nombre de Mersenne]] 2<sup>{{unité|6972593}}</sup> − 1 avec ses {{unité|2098960|chiffres}}<ref>{{en}} [[GIMPS]] press release, [http://www.mersenne.org/primes/6972593.htm ''GIMPS Finds First Million-Digit Prime''].<!-- Retrieved on 2008-01-04.--></ref>{{,}}<ref>{{en}} Chris Caldwell, [http://primes.utm.edu/notes/by_year.html ''The Largest Known Prime by Year: A Brief History''] at The Prime Pages. Part 1 : Before Electronic Computers, Part 2 : The Age of Electronic Computers.</ref>, grâce aux efforts du projet collaboratif de [[calcul distribué]] ''{{Lang|en|[[Great Internet Mersenne Prime Search]]}}'' (GIMPS).

L'''[[Electronic Frontier Foundation]]'' offre des prix de calcul coopératif pour encourager les internautes à contribuer à la résolution de problèmes scientifiques par le calcul distribué. Le GIMPS a ainsi reçu {{unité|100000|[[Dollar américain|dollars]]}} pour sa découverte en 2008 du premier nombre premier d'au moins dix millions de chiffres décimaux. L'EFF offre encore {{formatnum:150000}} et {{unité|250000|dollars}} respectivement pour la découverte du premier nombre premier de cent millions et un milliard de chiffres décimaux<ref>{{en}} [https://www.eff.org/awards/coop EFF Cooperative Computing Awards].</ref>.

=== Historique du plus grand nombre premier connu ===
{{Article détaillé|Plus grand nombre premier connu}}
Le record du plus grand nombre premier connu a presque toujours été trouvé parmi les [[#Nombres premiers de Mersenne|nombres de Mersenne]], comme le dernier en date,2<sup>136.279.841</sup> – 1, un nombre découvert le {{Date-|12 octobre 2024}}, ayant {{unité|41.024.320|chiffres}} décimaux.

=== Historique des nombres premiers tous connus ou dénombrés en dessous d'un seuil ===
Découvrir un nombre premier plus grand que tous ceux déjà connus n'implique pas de connaître tous les nombres premiers intermédiaires.

Plus généralement, la recherche de tous les nombres premiers inférieurs à un nombre donné (premier ou non) constitue un défi mathématique spécifique.

{| class="wikitable"
! scope=col width="10%" | Date
! scope=col width="29%" | Seuil {{mvar|s}}
! scope=col width="23%" | Quantité {{math|π(''s'')}}<sup>(*)</sup> 
! scope=col width="19%" | Vérificateurs
! scope=col width="19%" | Méthode
|- 
| align="center" | Antiquité
| align="right" | {{formatnum:1000}}
| align="right" | 168 
| align="center" |[[Ératosthène]], [[Euclide]]<ref name=historique>[http://villemin.gerard.free.fr/Wwwgvmm/Premier/historiq.htm villemin.gerard.free.fr] Nombres premiers : Historique.</ref>
|rowspan=5 align="center" | Essais par division<ref name=historique/>
|- 
| align="center" | 1746<ref name=historique/>
| align="right" | {{formatnum:100000}}
| align="right" | {{formatnum:9592}}
|rowspan=3 align="center" | ?
|-
| align="center" | 1797<ref name=historique/>
| align="right" | {{formatnum:400000}}
| align="right" | {{formatnum:33860}}
|-
| align="center" | 1811<ref name=historique/>
| align="right" | {{formatnum:1000000}}
| align="right" | {{formatnum:78498}}
|- 
| align="center" | 1863<ref name=historique/>
| align="right" | {{formatnum:100000000}}
| align="right" | {{formatnum:5761455}}
| align="center" |{{Lien|langue=de|trad=Jakob Philipp Kulik|fr=Jakob Philipp Kulik}}<ref name=historique/>{{,}}<ref>Mathématicien autrichien ([[1793]]-[[1863]]) : {{MacTutor|id=Kulik|title=Jakob Philipp Kulik}}</ref>
|-
|rowspan=3 align="center" |2010<ref name=conditionalcalculationofpi>{{en}} [http://primes.utm.edu/notes/pi(10%5E24).html primes.utm.edu] Conditional Calculation of pi(10^24).</ref>
| align="right" | 2<sup>76</sup> = {{unité|75557863725914323419136}}
| align="right" | {{unité|1462626667154509638735}}
|rowspan=3 align="center"|[[Jens Franke]] {{et al.}}<ref name=conditionalcalculationofpi />
|rowspan=3 align="center" | Évaluation directe de <small><math>\pi(s)</math></small><ref name=conditionalcalculationofpi />
|-
| align="right" | 2<sup>77</sup> = {{unité|151115727451828646838272}}
| align="right" | {{unité|2886507381056867953916}}
|-
| align="right" | 10<sup>24</sup> ≈ {{Nombre|1 000 000 000 000 000 000 000 000}}
| align="right" | {{unité|18435599767349200867866}}
|}

Notes :<br />
<sup>(*)</sup>&nbsp;&nbsp;&nbsp;{{math|π(''s'')}} est la [[Fonction de compte des nombres premiers|quantité totale de nombres premiers situés sous le seuil {{mvar|s}}]] (c'est-à-dire dans l'intervalle d'entiers <math>[\![0, s]\!]</math>).
{{Retrait|La connaissance de {{math|π(''s'')}} par un calcul algorithmique n'implique pas nécessairement que chacun des nombres premiers soit immédiatement identifiable.}}
{{Retrait|La décomposition en facteurs permet au contraire d'identifier les nombres premiers individuellement, mais elle est impraticable pour des nombres supérieurs à 10<sup>40</sup> ; au-delà de cette valeur, on dispose de [[test de primalité|tests de primalité]] rapides.}}

== Structures algébriques, topologiques, et nombres premiers ==
[[Fichier:Prime rectangles.svg|vignette|redresse=1.5|Le nombre 12 n'est pas premier car il est l'aire d'un [[rectangle]] de côtés 3 et 4.]]

La notion de nombre premier est liée à l'étude de la structure multiplicative de l'[[Anneau unitaire|anneau]] des [[Entier relatif|entiers relatifs]]. Le théorème fondamental de l'arithmétique, basé sur le [[lemme d'Euclide]], élucide cette structure en assurant que tout entier strictement positif se factorise en un produit de nombres premiers, de manière unique à l'ordre des facteurs près. Ce théorème permet de déterminer des notions de [[Plus grand commun diviseur|pgcd]], [[Plus petit commun multiple|ppcm]], et de [[nombres premiers entre eux]], qui sont utiles pour la résolution de certaines [[équation diophantienne|équations diophantiennes]], notamment la caractérisation des [[triplet pythagoricien|triplets pythagoriciens]].

D'autres problèmes naturels sont envisagés, comme la détermination de la proportion d'entiers premiers à un entier fixé. L'introduction de [[structure (mathématiques)|structures]] [[structure algébrique|algébriques]] plus avancées permet de résoudre ce problème rapidement dans le cadre de l'[[arithmétique modulaire]]. De nombreux théorèmes classiques de nature arithmétique peuvent être énoncés, comme le [[petit théorème de Fermat]], ou le [[théorème de Wilson]] ; ou des théorèmes de nature plus algébrique comme le [[théorème des restes chinois]].

Le théorème des restes chinois est un premier résultat dans l'étude des [[groupe abélien fini|groupes abéliens finis]]{{sfn|Naudin|Quitté|1992|loc=début du chapitre 3}}. Il met en évidence que la structure de ces groupes est en partie liée à la décomposition en produit de facteurs premiers de leurs cardinaux. Les choses sont plus compliquées pour les groupes non abéliens, cependant, l'étude se base à nouveau sur la décomposition en facteurs premiers de leurs cardinaux, à travers la [[Théorèmes de Sylow|théorie de Sylow]].

Les nombres premiers interviennent aussi dans les [[structure (mathématiques)|structures]] [[topologie|topologiques]]. Le corps des [[Nombre rationnel|nombres rationnels]] admet une structure topologique habituelle, qui donne par complétion le [[nombre réel|corps des nombres réels]]. Pour chaque nombre premier ''p'', une autre structure topologique peut être construite, à partir de la norme suivante : si <math>x=\frac{a}{b}</math> est un nombre rationnel non nul sous forme irréductible et que <math>p^\alpha</math> et <math>p^\beta</math> sont les plus grandes puissances de ''p'' divisant ''a'' et ''b'', la [[Nombre p-adique#Approche analytique|norme p-adique]] de ''x'' est <math>p^{\beta-\alpha}</math>. En complétant le corps des rationnels suivant cette norme, on obtient le [[nombre p-adique|corps des nombres p-adiques]], introduit par [[Kurt Hensel]] au début du {{s|XX}}. Le [[théorème d'Ostrowski]] assure que ces normes p-adiques et la norme habituelle sont les seules sur le corps des nombres rationnels, à équivalence près{{sfn|Gouvêa|1997}}.

== Nombres premiers particuliers ==
{{Article détaillé|Liste de suites de nombres premiers}}
Il existe des types remarquables de nombres premiers, définis par des contraintes particulières. Les quelques cas ci-dessous sont parmi les plus connus.

=== Nombres premiers de Pythagore ===
{{Article détaillé|Nombre premier pythagoricien}}
On appelle parfois nombre premier « de [[Pythagore]] » tout nombre premier de la forme 4''n ''+ 1, où ''n'' est un entier naturel. Par exemple, le nombre premier 5 est de Pythagore. Un nombre premier impair est de Pythagore si et seulement s'il est [[Théorème des deux carrés de Fermat|somme de deux carrés]].

=== Nombres premiers de Mersenne ===
{{Article détaillé|Nombre de Mersenne premier}}
[[Fichier:Marin mersenne.jpg|vignette|redresse|[[Marin Mersenne]].]]

Les nombres premiers de la forme :
{{Retrait|<math>M_p = 2^p - 1</math>}}
où ''p'' est alors nécessairement aussi premier, sont appelés nombres premiers de [[Marin Mersenne|Mersenne]]. Les grands nombres premiers sont souvent recherchés sous cette forme car il existe un test efficace, le [[test de primalité de Lucas-Lehmer]], pour déterminer si un tel nombre est premier ou non.

Entre 2008 et 2012, le plus grand nombre premier connu était ''M''<sub>{{formatnum:43112609}}</sub> = 2<sup>{{formatnum:43112609}}</sup> – 1, qui comporte {{nombre|12978189|chiffres}} en écriture décimale. Il s'agit (chronologiquement) du {{45e|nombre}} premier de Mersenne connu et sa découverte a été annoncée le {{date-|23|août|2008}} par le [[GIMPS]]. Un {{46e|nombre}} premier de Mersenne, 2<sup>{{formatnum:37156667}}</sup> – 1, inférieur au précédent, a été découvert deux semaines plus tard ; le {{date-|12|avril|2009}} était découvert, par le même projet GIMPS, un {{47e|nombre}} premier de Mersenne, 2<sup>{{formatnum:42643801}}</sup> – 1, lui aussi inférieur au premier cité.

Ce record a été battu (toujours par le GIMPS) par la preuve de la primalité de ''M''<sub>{{formatnum:57885161}}</sub> = 2<sup>{{formatnum:57885161}}</sup> – 1 (en janvier 2013) puis à nouveau, le {{Date-|7|janvier|2016}}, par celle de ''M''{{ind|{{nombre|74207281}}}}, puis de ''M''{{ind|77232917}}, et enfin, le {{date|12|octobre|2024}}, de ''M''{{ind|136279841}} ayant {{nombre|41 024 320}} chiffres décimaux. 

=== Nombres premiers de Fermat ===
{{Article détaillé|Nombre de Fermat}}
[[Fichier:Pierre de Fermat.jpg|vignette|redresse|droite|[[Pierre de Fermat]].]]

Les nombres de la forme :
{{Retrait|<math>F_n = 2^{2^n} + 1</math>}}
sont appelés les nombres de Fermat. [[Pierre de Fermat|Fermat]] avait conjecturé que tous ces nombres étaient premiers<ref> Il écrit ainsi à [[Bernard Frénicle de Bessy]] : {{Citation|''Mais voici ce que j'admire le plus : c'est que je suis quasi persuadé que tous les nombres progressifs augmentés de l'unité, desquels les exposants sont des nombres de la progression double, sont nombres premiers, comme 3, 5, 17, 257, 65537, 4 294 967 297 et le suivant de 20 lettres 18 446 744 073 709 551 617 ; etc. Je n'en ai pas la démonstration exacte, mais j'ai exclu si grande quantité de diviseurs par démonstrations infaillibles, et j'ai de si grandes lumières, qui établissent ma pensée, que j'aurois peine à me dédire''.}}, Lettre XLIII, du ? août 1640, dans {{Ouvrage|titre=Œuvres de Fermat|tome=2|lieu=Paris|éditeur=[[Gauthier-Villars]]|année=1894|passage=206|lire en ligne=https://archive.org/details/oeuvresdefermat942ferm}}.</ref>. Cependant, les seuls nombres de Fermat premiers connus sont
:<math>F_0=3</math>, <math>F_1=5</math>, <math>F_2=17</math>, <math>F_3=257</math> et <math>F_4=65\,537</math>.
Le nombre de Fermat ''F''{{ind|5}} est seulement [[Nombre semi-premier|semi-premier]]. Il est divisible par 641.

Il s'agit du premier [[contre-exemple]] à cette conjecture de Fermat, découvert par [[Leonhard Euler|Euler]]<ref>{{Article|lang=la|auteur=L. Euler|titre=Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus|revue=Commentarii academiae scientiarum Petropolitanae|vol=6<!--|year=1738-->|p.=102-103|année=1732|url=https://scholarlycommons.pacific.edu/euler-works/26/}}.</ref> en 1732. Tous les autres nombres de Fermat calculés depuis sont composés, au point que l'objectif s'est transformé en la recherche (sans doute vouée à l'échec<ref>{{Article|langue=en|prénom=Kent D.|nom=Boklan|prénom2=John H.|nom2=Conway|titre=Expect at most one billionth of a new Fermat Prime!|périodique=[[The Mathematical Intelligencer]]|année=2017|doi=10.1007/s00283-016-9644-3|arxiv=1605.01371v2|lire en ligne=https://arxiv.org/pdf/1605.01371v2.pdf|consulté le=8 mai 2016}}.</ref>) d'un autre nombre de Fermat premier.

=== Nombres premiers jumeaux ===
{{article détaillé|Nombres premiers jumeaux}}

Deux nombres premiers sont dits jumeaux s'ils ne diffèrent que de 2. Les trois plus petits couples de nombres premiers jumeaux sont (3, 5), (5, 7) et (11, 13). Le plus grand connu est {{Formatnum:2996863034895}} × 2{{exp|{{Formatnum:21290000}}}} ± 1 ; les deux nombres possèdent {{unité|388342|chiffres}} (septembre 2016).

Il est conjecturé qu'il existe une infinité de nombres premiers jumeaux.

=== Nombres premiers de Sophie Germain ===
{{article détaillé|Nombre premier de Sophie Germain}}

Un nombre premier ''G'' est un nombre premier de [[Sophie Germain]] si 2''G''&nbsp;+&nbsp;1 est aussi un nombre premier, appelé [[nombre premier sûr]].

Les dix premiers nombres premiers de Sophie Germain sont [[2 (nombre)|2]], [[3 (nombre)|3]], [[5 (nombre)|5]], [[11 (nombre)|11]], [[23 (nombre)|23]], [[29 (nombre)|29]], [[41 (nombre)|41]], [[53 (nombre)|53]], [[83 (nombre)|83]], [[89 (nombre)|89]].

Il est conjecturé qu'il existe une infinité de nombres premiers de Sophie Germain.

=== Nombres premiers brésiliens ===
{{article détaillé|Nombre brésilien}}

Un nombre premier [[nombre brésilien|brésilien]] ''p'' est un nombre premier qui est [[répunit]] avec un nombre premier impair de 1 dans une base ''b'' ; la réciproque est fausse comme le montrent 57 = 111<sub>7</sub> = 3 × 19 ou encore 121 = 11111<sub>3</sub> = 11 x 11.

Le plus petit nombre premier brésilien est [[7 (nombre)|7]] = 111<sub>2</sub> ; [[43 (nombre)|43]] = 111<sub>6</sub> et [[127 (nombre)|127]] = 1111111<sub>2</sub> sont d'autres exemples.

La suite des nombres premiers brésiliens commence par [[7 (nombre)|7]], [[13 (nombre)|13]], [[31 (nombre)|31]], [[43 (nombre)|43]], [[73 (nombre)|73]], [[127 (nombre)|127]], [[157 (nombre)|157]], [[211 (nombre)|211]], [[241 (nombre)|241]], [[307 (nombre)|307]], [[421 (nombre)|421]], [[463 (nombre)|463]] {{etc.}} ({{OEIS|id=A085104}}).

Seuls deux nombres premiers brésiliens sont connus pour être brésiliens dans deux bases différentes, ce sont les deux nombres de la [[conjecture de Goormaghtigh]]: [[31 (nombre)|31]] = 11111<sub>2</sub> = 111<sub>5</sub> et [[Nombres 8 000 à 8 999|8191]] = 1111111111111<sub>2</sub> = 111<sub>90</sub>.

On [[conjecture]] qu'il existe une infinité de nombres premiers brésiliens, mais, alors que la [[série des inverses des nombres premiers]] est [[Série divergente|divergente]], la [[Série (mathématiques)|série]] des [[inverse]]s des nombres premiers brésiliens est convergente vers un nombre, appelé « constante des nombres premiers brésiliens », légèrement supérieure à 0,33 et qui est étudiée dans la séquence {{OEIS2C|id=A306759}}.

Tout [[nombre de Mersenne premier]] supérieur ou égal à 7 est brésilien par définition. Par exemple, <math>M_5 = 2^5 - 1 = 31 = 11111_2</math>.

Par contre, tout [[nombre de Fermat]] <math>F_n = 2^{2^n} + 1</math> premier est non brésilien<ref>{{Article|auteur=B. Schott|titre= Les nombres brésiliens|périodique=Quadrature|volume=76|année=2010}}, disponible dans les liens de la {{OEIS|id=A125134}}.</ref>.

Les plus petits nombres des couples de [[nombres premiers jumeaux]] qui sont brésiliens sont plutôt rares (ils figurent dans la suite {{OEIS2C|id=A306849}}), et plus généralement, les nombres premiers brésiliens sont relativement rares ; ainsi, sur les premiers 10{{exp|12}} entiers naturels, il existe {{nombre|37607912018}} nombres premiers dont seulement {{nombre|88285}} sont des premiers brésiliens.

== Algorithmique : calcul des nombres premiers et tests de primalité ==
=== Crible d'Ératosthène et algorithme par essais de division ===
{{Article détaillé|Crible d'Ératosthène}}

Les premiers [[algorithme]]s pour décider si un nombre est premier (appelés [[test de primalité|tests de primalité]]) consistent à essayer de le diviser par tous les nombres qui n'excèdent pas sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Cependant, l'algorithme dérivant de cette formulation peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers n'excédant pas sa racine carrée.

Le [[crible d'Ératosthène]] est une méthode, reposant sur cette idée, qui fournit la liste des nombres premiers inférieurs à une valeur fixée ''n'' (''n'' = 120 dans l'animation ci-contre) :
* on forme la liste des entiers de 2 à ''n'' ;
* on retient comme « nombre premier » le premier nombre de la liste non encore barré (le premier dans ce cas est 2) ;
* on barre tous les entiers multiples du nombre retenu à l'étape précédente, en commençant par son carré (puisque 2 × ''i'', 3 × ''i'', … , (''i ''– 1) × ''i ''ont déjà été barrés en tant que multiples de 2, 3, ...) ;
* on répète les deux dernières opérations (c'est-à-dire : on retient le prochain nombre non barré et on barre ses multiples) ;
* dès qu'on en est à chercher les multiples des nombres excédant la racine carrée de ''n'', on termine l'algorithme.
Ainsi les nombres premiers inférieurs à ''n'' sont les nombres qui restent non barrés à la fin du processus. Cet algorithme est de [[Théorie de la complexité (informatique théorique)|complexité algorithmique]] exponentielle (calculée, comme habituellement, en fonction de la taille de ''n'').

Le crible d'Ératosthène fournit donc plus d'information que la seule primalité de ''n''. Si seule cette information est souhaitée, une variante parfois plus efficace consiste à ne tester la divisibilité de ''n'' que par des petits nombres premiers dans une liste fixée au préalable (par exemple 2, 3 et 5), puis par tous les nombres entiers inférieurs à la racine carrée de ''n'' qui ne sont divisibles par aucun des petits nombres premiers choisis ; cela amène à tester la divisibilité par des nombres non premiers (par exemple 49 si les petits premiers sont 2, 3 et 5 et que ''n'' excède 2500), mais un choix d'un nombre suffisant de petits nombres premiers doit permettre de contrôler le nombre de tests inutiles effectués{{sfn|Cohen|1993|loc=début du chapitre 8, notamment l'algorithme 8.1.1}}.

[[Fichier:Animation Sieb des Eratosthenes.gif|centré|redresse=1.7|Le crible d'Ératosthène : nombres premiers inférieurs à 120.]]

=== Autres algorithmes ===
{{Article détaillé|Test de primalité}}
Une variante du crible d'Ératosthène est le [[crible de Sundaram]] qui consiste à former les produits de nombres impairs. Les nombres qui ne sont pas atteints par cette méthode sont les nombres premiers impairs, c'est-à-dire tous les nombres premiers sauf 2. Par ailleurs, à partir du crible d'Ératosthène, la factorisation de l'entier ''n'' peut facilement être trouvée. D'autres méthodes plus générales concernant ce problème plus difficile que simplement déterminer la primalité sont aussi appelées méthodes de crible, la plus efficace étant actuellement le [[crible général des corps de nombres]]{{sfn|Cohen|1993|loc=chapitre 10, plus particulièrement la section 5}}.

Les algorithmes présentés précédemment ont une complexité trop importante pour pouvoir être menés à terme, même avec les ordinateurs les plus puissants, quand ''n'' devient grand.

Une autre classe d'algorithme consiste à tester l'entier ''n'' pour une famille de propriétés vérifiées par les nombres premiers : si une propriété de cette famille n'est pas vérifiée pour ''n'', alors il est composé ; en revanche, le fait qu'une des propriétés de la famille soit vérifiée pour ''n'' ne suffit pas à assurer la primalité. Toutefois, si cette famille est telle qu'un nombre composé ne vérifie pas au moins la moitié des propriétés en jeu, alors l'utilisateur peut estimer qu'un nombre ''n'' qui vérifie ''k'' propriétés de la famille est premier avec une probabilité supérieure à {{math|1 – 2<sup>–''k''</sup>}} : il est déclaré probablement premier à partir d'une valeur de ''k'' à choisir par l'utilisateur ; un nombre déclaré probablement premier, mais qui n'est pas premier est appelé [[nombre pseudo-premier]]. Un test basé sur ce principe est appelé test probabiliste de primalité. De tels tests reposent souvent sur le [[petit théorème de Fermat]], amenant au [[test de primalité de Fermat]], et à ses raffinements : le [[test de primalité de Solovay-Strassen]] et celui de [[test de primalité de Miller-Rabin|Miller-Rabin]], qui sont des améliorations, car ils admettent moins de nombres pseudo-premiers{{sfn|Naudin|Quitté|1992|loc=chap. 4, section 6}}{{,}}{{sfn|Cohen|1993|loc=chap. 8, section 2}}.

L'algorithme ''[[Test de primalité AKS|AKS]]'' mis au point en 2002 permet de déterminer (avec certitude) si un nombre donné ''N'' est premier en utilisant un temps de calcul polynomial.

== Des formules pour les nombres premiers ==
{{article détaillé|Formules pour les nombres premiers}}
De nombreuses formules ont été cherchées pour générer les nombres premiers. Le plus haut niveau d'exigence serait de trouver une formule qui à un entier {{mvar|n}} associe le ''n''-ième nombre premier. De manière un peu plus souple, on peut se contenter d'exiger une fonction {{mvar|f}} qui à tout entier {{mvar|n}} associe un nombre premier et telle que chaque valeur prise ne le soit qu'une fois.

Enfin, on souhaite que la fonction soit calculable en pratique{{sfn|Ribenboim|1996|loc=introduction du chapitre 3}} (ce qui n'est pas le cas de la [[constante de Mills|formule de Mills]]). {{pertinence contestée|Par exemple, le [[théorème de Wilson]] assure que {{mvar|p}} est un nombre premier si et seulement si {{math|(''p'' -1)! ≡ -1 mod ''p''}}.
Il s'ensuit que la fonction {{math|f(''n'') {{=}} 1 + [((''n'' - 1)!) mod ''n'']|§=f(''n'') {{=}} 1 + [((''n'' - 1)!) mod ''n'']}} vaut
{{mvar|n}} si {{mvar|n}} est un nombre premier ; elle vaut 3 si {{math|''n'' {{=}} 4}} et 1 si {{mvar|n}} est un autre nombre composé. Cependant, le calcul de la [[factorielle]] (même [[arithmétique modulaire|modulo]] <math>n</math>) est rédhibitoire pour de grandes valeurs de {{mvar|n}}, et cette fonction a donc peu d'utilité pour générer des nombres premiers.}}

Il est donc tentant de chercher des [[fonction polynomiale|fonctions polynomiales]] dont les valeurs
sont des nombres premiers. Ceci a conduit au résultat (négatif) suivant : un polynôme (à une ou plusieurs variables) dont les valeurs aux entiers naturels sont des nombres premiers, est un [[polynôme constant]]{{sfn|Ribenboim|1996|loc=chap. 3, section II}}.

La recherche de polynômes vérifiant une propriété plus faible s'est développée à partir de la notion d'[[Diophantien|ensemble diophantien]] de nombres entiers ; de tels ensembles peuvent être caractérisés comme les ensembles de valeurs strictement positives prises par un [[polynôme]] (à plusieurs variables) dont les coefficients et les variables sont des nombres entiers.

Un travail mené dans les années 1960 et 1970, notamment par [[Hilary Putnam|Putnam]], [[Martin Davis|Davis]], [[Julia Robinson|Robinson]] et [[Youri Matiiassevitch|Matiiassevich]] permet de montrer que l'ensemble des nombres premiers est diophantien, conduisant à l'existence de polynômes à coefficients et variables entières dont toutes les valeurs positives sont les nombres premiers. L'écriture de divers polynômes explicites a ensuite été possible, avec différents nombres de variables, et divers degrés. Notamment, Jones, Sato, Wada et Wiens ont déterminé en 1976 [[Formules pour les nombres premiers#Relation diophantienne|un tel polynôme, de degré 25 à 26 variables]]. De même que pour les formules à factorielles, ce polynôme est inutilisable en fait, car il ne donne pratiquement que des valeurs négatives quand on fait varier les 26 variables de 0 à <math>+\infty.</math>

La notion d'ensemble diophantien s'est plus généralement développée à partir de l’étude et de la résolution du [[dixième problème de Hilbert]] sur les [[équation diophantienne|équations diophantiennes]]{{sfn|Ribenboim|1996|loc=chap. 3, section III}}, Matiiassevitch ayant montré que tous les ensembles [[récursivement énumérable]]s sont diophantiens.

== Répartition des nombres premiers ==
=== Infinité des nombres premiers ===
{{Article détaillé|Théorème d'Euclide sur les nombres premiers}}
Euclide a démontré dans ses ''[[Éléments d'Euclide|Éléments]]'' (proposition 20 du [[Livre IX des Éléments d'Euclide|Livre IX]]) que ''les nombres premiers sont en plus grande quantité que toute quantité proposée de nombres premiers''. Autrement dit, il existe [[Ensemble infini|une infinité]] de nombres premiers. La démonstration d'Euclide repose sur la constatation qu'une famille finie ''p''<sub>1</sub>,...,''p<sub>n</sub>'' de nombres premiers étant donnée, tout nombre premier divisant le produit des éléments de cette famille augmenté de 1 est en dehors de cette famille (et un tel diviseur existe, ce qui est aussi prouvé par Euclide){{sfn|Hardy|Wright|texte=Hardy et Wright 2007|loc=section 2.1}}.

D'autres [[démonstration (logique et mathématique)|démonstrations]] de l'infinité des nombres premiers ont été données. La preuve d'[[Leonhard Euler|Euler]]<ref>{{la}} Leonh. Euler, « Variae observationes circa series infinitas », ''Commentarii academiae scientiarum Petropolitanae'', vol. 9, 1744, {{p.|160-188}} ou ''Opera Omnia'', Series 1, vol. 14, {{p.|217-244}}. Téléchargeable à [http://www.math.dartmouth.edu/~euler/docs/originals/E072.pdf]. L'identité y est le théorème 7, p. 172 et l'infinité des nombres premiers y est implicitement rappelée et analysée dans les corollaires qui suivent.</ref> utilise l'identité :
<center><math>\sum_{n=1}^\infin \ \frac1n\ = \ \prod_{p\in\mathcal P} \ \frac1{1-\frac1p}</math>.</center>
Dans la formule précédente, le terme de gauche est la somme de la [[série harmonique]], qui est divergente. Par conséquent, le produit de droite doit contenir une infinité de facteurs.

[[Hillel Furstenberg|Furstenberg]] fournit une preuve utilisant une [[Démonstration de Fürstenberg de l'infinité des nombres premiers|argumentation topologique]]{{sfn|Ribenboim|1996}}.

=== Raréfaction des nombres premiers ===
{{Article détaillé|Fonction de compte des nombres premiers}}
[[Fichier:PrimeNumbersSmall.png|vignette|redresse=1.7|La [[Distribution (mathématiques)|distribution]] des nombres premiers de 1 à 76 800, de gauche à droite et de haut en bas. Un pixel [[noir]] signifie que le nombre est premier alors qu'un [[blanc]] signifie qu'il ne l'est pas.]]

==== {{s|XVIII}} ====
Le premier résultat sur le comportement des nombres premiers à l’infini est dû à Euler :

{|
|{{Théorème|Théorème de raréfaction d’Euler (1737)|La série des inverses des nombres premiers est divergente : <math>\sum_{p \, \text{premier}} \frac{1}{p} \, = \, + \, \infty.</math>}}
|}

Comme la série des inverses de tous les entiers est également divergente, cela indique intuitivement que, si les nombres premiers se raréfient à l’infini, ils ne se raréfient pas très vite<ref>Quand <math>x</math> tend vers l’infini, les inégalités suivantes illustrent le rythme de raréfaction :
<center><math>\begin{alignat}{5}
\sum_{n \, \text{entier}}^{\le x} \frac{1}{n^{1+\varepsilon}} \qquad & < & \sum_{p \, \text{premier}}^{\le x} \frac{1}{p}  \quad & < & \sum_{n \, \text{entier}}^{\le x} \frac{1}{n}. \quad  \\
\overbrace{\qquad \qquad \qquad \qquad \qquad} & & \overbrace{\qquad \qquad \qquad } & &  \overbrace{\qquad \qquad \qquad } \\
\text{convergente vers} \, \zeta (1+\varepsilon) & & \text{divergente} & & \text{divergente} \\
= \frac{1}{\varepsilon} \, + \, \gamma + o(1) & & \sim \ln \ln x  & & \sim \ln x 
\end{alignat}</math></center>
La série de gauche est convergente, alors que la somme porte sur '''tous''' les entiers et que <math>\varepsilon</math> (positif) peut être choisi aussi petit qu’on veut, tandis que la série du milieu, conformément au théorème d’Euler, est divergente et tend vers l’infini, alors que la somme ne porte '''que''' sur les nombres premiers.
</ref>.

Par ailleurs, le résultat sur l'infinité des nombres premiers amène à se demander combien il y a de nombres premiers jusqu’à un nombre donné et à étudier la fonction correspondante. Pour cela, on désigne, pour tout nombre premier <math>p,</math> son rang dans la suite croissante des nombres premiers, comme indiqué dans le tableau suivant pour les 25 nombres premiers inférieurs à 100 :

<center>
{| border=0|class="wikitable" 
|-
| {{nobr|Les 25 nombres premiers inférieurs à 100}} || align=right|<math>p</math> :|| &nbsp; &nbsp;   || largeur=100|[[2 (nombre)|2]], || [[3 (nombre)|3]], || [[5 (nombre)|5]], || [[7 (nombre)|7]], || [[11 (nombre)|11]], || [[13 (nombre)|13]], || [[17 (nombre)|17]], || [[19 (nombre)|19]], || [[23 (nombre)|23]], || [[29 (nombre)|29]], || [[31 (nombre)|31]], || [[37 (nombre)|37]], || [[41 (nombre)|41]], || [[43 (nombre)|43]], || [[47 (nombre)|47]], || [[53 (nombre)|53]], || [[59 (nombre)|59]], || [[61 (nombre)|61]], || [[67 (nombre)|67]], || [[71 (nombre)|71]], || [[73 (nombre)|73]], || [[79 (nombre)|79]], || [[83 (nombre)|83]], || [[89 (nombre)|89]], || [[97 (nombre)|97]].
|-
| Rang ||  align=right|<math>\pi(p)</math> : ||  || <small>1</small>  || <small>2</small>  || <small>3</small>  || <small>4</small>  || align=center|<small>5</small>  || align=center|<small>6</small>  || align=center|<small>7</small>  || align=center|<small>8</small>  || align=center|<small>9</small>  || <small>10</small>  || <small>11</small>  || <small>12</small>  || <small>13</small>  || <small>14</small>  || <small>15</small>  || <small>16</small>  || <small>17</small>  || <small>18</small>  || <small>19</small>  || <small>20</small>  || <small>21</small>  || <small>22</small>  || <small>23</small>  || <small>24</small>  || <small>25</small>  
|}</center>

Pour <math>x</math> une variable réelle, <math>\pi(x)</math> est définie comme le nombre de nombres premiers <math>\le x.</math> Cette fonction réelle à valeurs entières est appelée [[fonction de compte des nombres premiers]]. C’est une fonction en escalier, constante entre deux nombres premiers successifs : <math>\pi(x)</math> est égal à <math>\pi(q)</math>, <math>q</math> étant le plus grand nombre premier <math>\le x.</math>

Restreinte au domaine de définition <math>\mathbb P</math>, la fonction <math>\pi</math> a une fonction réciproque, généralement notée <math>p_n</math>, qui représente le ''n''-<sup>ième</sup> nombre premier, par exemple <math>p_{16}=53</math>.

La fonction <math>\pi(x)</math> est croissante et tend vers l’infini{{sfn|Hardy|Wright|texte=Hardy et Wright 2007|loc=section 2.1}}. C’est une conséquence triviale du théorème de l’infinité des nombres premiers (voir section précédente).

Le premier résultat important sur <math>\pi(x)</math> est obtenu par Legendre :

{|
|{{Théorème|Théorème de raréfaction de Legendre|Le rapport <math>\frac{\pi(x)}{x}</math> tend vers zéro quand <math>x</math> tend vers l’infini.}}
|}

Vers la fin du {{s|XVIII}}, [[Adrien-Marie Legendre|Legendre]] (1797) et [[Carl Friedrich Gauss|Gauss]] (1792) conjecturent que la [[fonction de compte des nombres premiers]] <math>\pi(x)</math> est équivalente à la fonction <math>\frac{x}{\ln(x)}</math> quand <math>x</math> tend vers l'infini. Dit autrement, la proportion de nombres premiers parmi les nombres inférieurs à <math>x,</math> c’est-à-dire <math>\frac{\pi(x)}{x},</math> tend vers 0 à la vitesse de <math>\frac1{\ln x}</math>.

On peut apprécier la pertinence de cette conjecture en examinant le tableau des valeurs de <math>\frac{\pi(x)}{x}</math> et de <math>\frac{\pi(x)}{\frac{x}{\ln(x)}}</math> pour les valeurs de <math>x</math> égales aux premières puissances entières de 10 :
<center>
{| class="wikitable"
|-
! <math>m</math> !! <math>\pi(m)</math> !! <math>\frac{\pi(m)}{m}</math> !! <math>\frac{\pi(m)}{\frac{m}{\ln(m)}}</math>
|-
| align=right|10 ||align=right|4 || align=center|0,400 || align=center|0,921
|-
| align=right|100 || align=right|25 || align=center|0,250 || align=center|1,151
|-
| align=right|{{formatnum:1000}} || align=right|168 || align=center|0,168 || align=center|1,161
|-
| align=right|{{formatnum:10000}} || align=right|{{formatnum:1229}} || align=center|0,123 || align=center|1,132
|-
| align=right|{{formatnum:100000}} || align=right|{{formatnum:9592}} || align=center|0,096 || align=center|1,104
|-
| align=center|… || align=center|… || align=center|… || align=center|…
|-
| align=right|<math>\rightarrow \, \infty</math><br />&nbsp; || align=right|<math>\rightarrow \, \infty</math><br />(Euclide) || align=center|<math>\rightarrow</math> 0<br />(Legendre) || align=center|<math>\rightarrow</math> 1<br />(conjecture)

|}</center>

Il faudra tout le {{s|XIX}} pour que la conjecture soit démontrée (voir section suivante).

==== {{s|XIX}} ====
Une première avancée vers la démonstration de la conjecture de Legendre-Gauss {{sfn|Ribenboim|1996|loc=chap. 4, section I}} est obtenue par [[Pafnouti Tchebychev|Tchebychev]] à partir de 1848 :

{{Théorème|Théorème de [[Pafnouti Tchebychev|Tchebychev]]|Il existe deux constantes C et D telles qu'on ait l'encadrement, pour ''x'' assez grand :
<center><math>\mathrm{C}\leq \frac{\pi(x)}{\frac{x}{\ln x}} \leq \mathrm{D}, </math> (inégalités de Tchebychev),</center>}}
la conjecture de Legendre-Gauss consistant à affirmer la validité de l’énoncé pour n’importe quel <math>\mathrm{C}<1</math> et n’importe quel <math>\mathrm{D}>1.</math>

Il démontre également le théorème suivant sur la raréfaction des nombres premiers :
{{Théorème|Théorème de [[Pafnouti Tchebychev|Tchebychev]]|Si <math>\frac{\pi(x)}{\frac{x}{\ln x}}</math> a une limite quand <math>x \rightarrow \infty,</math> cette limite vaut 1.</center>}}

Comme conséquence des inégalités ci-dessus, Tchebychev peut aussi démontrer le [[postulat de Bertrand]] selon lequel dans tout intervalle d'entiers naturels, entre un entier et son double existe au moins un nombre premier{{sfn|Hardy|Wright|texte=Hardy et Wright 2007|loc=chap. 22, sections 1 à 4}}.

Une nouvelle avancée est due à Riemann dans un article célèbre en 1859 : il étend le [[Ensemble de définition|domaine de définition]] de la fonction <math>\zeta(s)</math> au plan complexe privé du nombre <math>s=1</math> ; il formule sa célèbre [[Hypothèse de Riemann|hypothèse]], selon laquelle les zéros de <math>\zeta (s)</math> situés dans la bande <math>0 \, \, <\operatorname{Re}(s) \, < \, 1</math> ont pour partie réelle <math>\frac12 \, ;</math> son approche constitue une impulsion décisive au développement de la [[théorie analytique des nombres]], source de nombreuses avancées en théorie des nombres.

À la fin du siècle, la conjecture de Legendre et Gauss est démontrée indépendamment par [[Jacques Hadamard]] et [[Charles-Jean de La Vallée Poussin]]{{sfn|Ellison|Mendès France|1975|loc=chap. 2, section 1.2}}, et porte depuis lors le nom de [[théorème des nombres premiers]]. La démonstration s’appuie sur l’observation qu’il suffit de s’assurer que la fonction <math>\zeta</math> ne s'annule pas dans le demi-plan de partie réelle <math>\ge 1</math> et de trouver un domaine qui englobe ce demi-plan dans lequel c’est le cas.
{{Théorème|[[Théorème des nombres premiers]] ([[Jacques Hadamard|Hadamard]] et [[Charles-Jean de La Vallée Poussin|de La Vallée Poussin]], 1896)|Quand <math>x \rightarrow \infty, \; \pi(x) \sim \frac{x}{\ln x}.</math>}}
Les démonstrations utilisent des outils puissants d'[[analyse complexe]] pour démontrer un énoncé d'arithmétique et d'analyse réelle. Une stratégie pour ces démonstrations est l'étude de la [[fonction zêta de Riemann]] sur un domaine du plan complexe plus grand qu'un simple voisinage de <math>z=1</math> : il est nécessaire de la contrôler, c'est-à-dire de majorer son module, au voisinage de la droite verticale des nombres de [[partie réelle]] égale à 1{{sfn|Ellison|Mendès France|1975|loc=chap. 2, théorème 2.4, puis section 4}}. La puissance des outils d'analyse complexe utilisés pour résoudre le théorème des nombres premiers conduit à un développement important d'une branche entière des mathématiques, la [[théorie analytique des nombres]], dans laquelle l'étude de la fonction zêta de Riemann devient un thème central. En particulier l'[[hypothèse de Riemann]], encore non démontrée, sur la localisation de ses zéros, aurait des conséquences fortes sur le comportement de la [[fonction de compte des nombres premiers]].

==== {{s|XX}} ====

Sur la base des résultats de Riemann (article de 1859), on peut déduire l'estimation :
{{Théorème|Théorème (Helge von Koch, 1901)|Sous l’[[hypothèse de Riemann]], on a : <math>\pi(x) = \operatorname{li}(x) + O(x^{1/2} \ln x),</math>}}
où <math>{\rm li} (x) = \int_{0}^{x} \frac{\mathrm dt}{\ln (t)}</math> (Riemann note cette fonction <math>{\rm Li} (x)</math>) et où <math>f = O(g)</math> signifie qu’il existe une constante <math>\mathrm{C} > 0</math> telle que <math>|f(x)| \le \mathrm{C}g(x)</math> pour tout <math>x</math> assez grand.

Les résultats sur la [[fonction de compte des nombres premiers]] permettent d'obtenir des résultats sur le ''n''-ième nombre premier. Par exemple, comme conséquences directes des théorèmes de Tchebychev, Ishikawa établit en 1934 des propriétés de la fonction ''n''-ième nombre premier, désignée par <math>p_n</math> :
<center><math>p_n +p_{n+1} > p_{n+2}, \qquad p_n p_m > p_{n+m}.</math></center>
Ou encore, d'après un résultat de Felgner de 1990{{sfn|Ribenboim|1996|loc=chap. 4, section II, A}} :
<center><math>0,91 \ n \ \ln(n) \ < \ p_n \ < \ 1,7 \ n \ \ln(n).</math></center>

Des démonstrations élémentaires du [[théorème des nombres premiers]] sont trouvées. Par élémentaires, il faut entendre qu’elles ne recourent pas à l'analyse complexe. C’est le cas notamment d’[[Paul Erdős|Erdős]] et de [[Atle Selberg|Selberg]]{{sfn|Ellison|Mendès France|1975|loc=chap. 2, section 1.2}}.

=== Répartition des nombres premiers dans les progressions arithmétiques ===
{{Article détaillé|Théorème de la progression arithmétique}}
En 1838, en reprenant l’étude d’Euler, au moyen d'un outil appelé [[caractère de Dirichlet]], et en utilisant à la place de la fonction zêta de Riemann des fonctions analogues appelées [[série de Dirichlet|fonction L de Dirichlet]], Dirichlet est capable d'adapter la démonstration au cas des nombres premiers dans des progressions arithmétiques : si ''a'' et ''b'' sont premiers entre eux, alors il existe une infinité de nombres premiers de la forme ''aq+b''. Utilisant les techniques de Hadamard, [[Charles-Jean de La Vallée Poussin|La Vallée Poussin]]  démontre ensuite  une version quantitative du théorème;  les nombres premiers sont [[Suite équidistribuée|équirépartis]] entre les différentes progressions arithmétiques de raison ''a'' (c'est-à-dire avec ''a'' fixé, et ''b'' variant parmi les divers restes inversibles dans la [[division euclidienne]] par ''a''){{sfn|Hardy|Wright|texte=Hardy et Wright 2007|loc=théorème 15}}{{,}}{{sfn|Ellison|Mendès France|1975|loc=chap. 7}} : le nombre de nombres premiers inférieurs ou égaux à ''x'', dans la suite ''aq +b'', est donc [[équivalent]] à <math>\frac{x}{\ln x\varphi(a)}</math>, où <math>\varphi</math> est l'[[indicatrice d'Euler]]. Bien que cela montre qu'il y a, par exemple, « autant » de nombres premiers de la forme <math>3n+1</math> que de la forme <math>3n+2</math>, les seconds semblent expérimentalement moins nombreux ; c'est le [[Biais de Tchebychev|biais de Tchevychev]], dont une démonstration rigoureuse dans tous les cas n'est pas encore connu en 2020.

=== Théorème de Green-Tao ===
{{Article détaillé|Théorème de Green-Tao}}
Le [[théorème de Green-Tao]], démontré en 2004 par [[Ben Joseph Green]] et [[Terence Tao]], généralise notamment le théorème de Dirichlet en assurant que pour tout entier ''k'', il existe une infinité de suites de ''k'' nombres premiers en progression arithmétique, c'est-à-dire de la forme :
<center><math>a,\,a+b,\,a+2b,\,\dots,\,a+(k-1)b</math>.</center>
Le théorème de Green-Tao est en fait bien plus fort que cet énoncé seul : par exemple, il établit qu'une telle progression arithmétique existe, avec des entiers tous plus petits que :
<center><math>2^{2^{2^{2^{2^{2^{2^{100k}}}}}}}</math></center>
(expérimentalement, cette borne semble plutôt devoir être de l'ordre de ''k''!). Il assure également que pour tout entier ''k'' et tout réel <math>\delta</math> strictement positif, pour tout ''x'' suffisamment grand, si ''P'' est un ensemble de nombres premiers inférieurs à ''x'' contenant au moins <math>\delta\pi(x)</math> éléments, alors ''P'' contient au moins une progression arithmétique de nombres premiers comptant ''k'' termes.

=== Conjecture de Bateman-Horn ===
{{article détaillé|Conjecture de Bateman-Horn}}
De nombreux résultats et conjectures sur la répartition des nombres premiers sont contenus dans la conjecture générale suivante. Soit ''f<sub>1</sub>'',...,''f<sub>k</sub>'' des polynômes non constants, [[polynôme irréductible|irréductibles]] et vérifiant la propriété que pour tout nombre premier ''p'' il y ait au moins un entier ''n'' parmi ''0'', ..., ''p ''– 1 tel que ''p'' ne divise pas le produit des ''f<sub>i</sub>''(''n''). On note <math>\omega(p)</math> le complémentaire à ''p'' du nombre de tels entiers. Un tel ensemble de polynômes est dit admissible ; on cherche à connaître la proportion d'entiers en lesquels les polynômes prennent simultanément des valeurs premières, et se limiter à des ensembles de polynômes admissibles permet d'éviter des cas triviaux comme ''f''<sub>1</sub>(''t'')=''t'', et ''f''<sub>2</sub>(''t'')=''t''+1. Il est alors conjecturé que le nombre d'entiers ''n'' plus petits qu'un réel ''x'' tels que les valeurs ''f''<sub>1</sub>(''n''),...,''f<sub>k</sub>''(''n'') sont simultanément premières, est, pour ''x'' assez grand, de l'ordre de :
<center><math>\left(\prod_p\frac{1-\frac{\omega(p)}p}{\left(1-\frac1p\right)^k}\right)\frac x{\log|f_1(x)|\dots \log|f_k(x)|}</math>.</center>
Le [[théorème des nombres premiers]] correspond au cas ''k'' = 1 et ''f<sub>t</sub> = t'', le [[théorème de la progression arithmétique|théorème de Dirichlet]] à ''k'' = 1 et ''f<sub>t</sub> = at'' + ''b'', et pour ''k'' = 2, ''f''<sub>1</sub>(''t'') = ''t'' et ''f''<sub>2</sub>(''t'') = ''t'' + 2, on obtient une version quantitative (et donc plus générale) de la conjecture des [[#Nombres premiers jumeaux|nombres premiers jumeaux]].

== Applications ==
La [[décomposition en facteurs premiers]] est utile pour simplifier les calculs fractionnaires, et de manière générale simplifier des formules. Elle n'est raisonnablement applicable que pour de petits nombres. Les [[sciences physiques]] ont de nombreuses formules comportant des nombres entiers petits, soit qu'il s'agisse de coefficients provenant de la dérivation ou de l'intégration de monômes, soit qu'il s'agisse de coefficients choisis volontairement entiers pour une application.

Les nombres premiers, et plus généralement la [[théorie des nombres]], ont longtemps été vus comme un sujet purement mathématique, avec peu ou pas d'applications extérieures. Cela changea rapidement dans les années 1970, quand de nouveaux systèmes de [[cryptographie]] basés sur les propriétés des nombres premiers furent conçus.

=== Cryptographie à clé publique ===
{{article détaillé|Cryptographie à clé publique}}

Jusque dans les années 1970, les systèmes de chiffrement connus étaient basés sur le principe de la [[cryptographie symétrique]], où une même clé (secrète) est utilisée pour chiffrer et déchiffrer un message. En 1978, [[Ronald Rivest]], [[Adi Shamir]] et [[Leonard Adleman]] décrivent le premier système public de [[cryptographie asymétrique]] (nommé d'après leurs initiales [[Rivest Shamir Adleman|RSA]]), basé sur les propriétés des nombres premiers et de la factorisation. Dans un tel système, deux clés sont utilisées : l'une sert à chiffrer, l'autre à déchiffrer. La clé permettant de chiffrer est accompagnée d'un grand nombre entier, le produit de deux grands nombres premiers gardés secrets (de l'ordre de {{nobr|200 chiffres}}). Pour calculer la clé de déchiffrement, la seule méthode connue nécessite de connaître les deux facteurs premiers. La sécurité du système est basée sur le fait qu'il est facile de trouver deux grands nombres premiers (en utilisant des tests de primalité) et de les multiplier entre eux, mais qu'il serait difficile pour un attaquant de retrouver ces deux nombres. Ce système permet également de créer des signatures numériques, et a révolutionné le monde de la cryptographie.

== Généralisations des nombres premiers ==
[[Fichier:Gaussian primes.svg|vignette|Nombres premiers de Gauss avec une norme inférieure à 500]]
La notion de nombre premier s'est vue généralisée au cours du {{s-|XIX}} dans d'autres structures algébriques que l'anneau des entiers relatifs. Pour résoudre des problèmes arithmétiques tels que le [[théorème des deux carrés]], le [[théorème des quatre carrés]], ou encore la [[loi de réciprocité quadratique]] (dont la première preuve est due à [[Carl Friedrich Gauss]] dans ses ''[[Disquisitiones arithmeticae]]''), les mathématiciens ont été amenés à mener des raisonnements sur la divisibilité analogues à ceux qui impliquent les nombres entiers dans d'autres anneaux, par exemple celui des [[entier de Gauss|entiers de Gauss]] ou celui des [[entier d'Eisenstein|entiers d'Eisenstein]].

Le point de vue moderne trouve sa source dans les travaux d'[[Ernst Kummer]], qui introduit la notion de « nombre premier idéal », dans sa tentative de démontrer le [[grand théorème de Fermat]]. Cette notion est à l'origine de la théorie moderne des anneaux d'entiers algébriques, découlant des travaux de Dedekind et Kronecker<ref>[[Nicolas Bourbaki]], ''[[Éléments d'histoire des mathématiques]]'', chapitre ''Algèbre commutative. Théorie des nombres algébriques.''</ref> : en termes modernes, on dit que ces anneaux ont une structure d'[[anneau de Dedekind|anneaux de Dedekind]] ; notamment, le théorème sur la factorisation des nombres premiers y est remplacé par un résultat de factorisation des idéaux de l'anneau (c'est-à-dire les sous-groupes absorbants pour la multiplication, qui dans ce contexte sont en rapport avec ce que Kummer appelait « nombres idéaux ») en produit d'idéaux premiers. L'arithmétique dans ces anneaux a en général des liens profonds et difficiles avec l'arithmétique des nombres premiers classiques : par exemple, dans ses travaux sur le théorème de Fermat, Kummer parvient à démontrer l'impossibilité de trouver des solutions non triviales (c'est-à-dire avec ''x'', ''y'' et ''z'' non nuls) à l'équation ''x<sup>p</sup> + y<sup>p</sup> = z<sup>p</sup>'' si ''p'' est un [[nombre premier régulier]] (il s'agit d'une condition portant sur la nature de l'anneau des [[Entier algébrique|entiers algébriques]] engendré par une racine primitive ''p''-ième de l'unité).

Sur la seule base de quelques expériences statistiques, certaines conjectures sur les nombres premiers ont été transposées aux [[Nombre chanceux|nombres chanceux]] (construits par une variante du [[#Crible d'Ératosthène et algorithme par essais de division|crible d'Ératosthène]])<ref>{{Ouvrage|langue=en|auteur1=David Wells|titre=Prime Numbers|sous-titre=The Most Mysterious Figures in Math|éditeur=[[John Wiley & Sons]]|année=2011|passage=147–148|isbn=}}.</ref>.

== Conjectures et questions ouvertes ==
Il y a beaucoup de [[conjecture]]s et de questions ouvertes sur les nombres premiers. Par exemple :
* Les quatre [[problèmes de Landau]] :
** [[conjecture de Goldbach]] : tout nombre pair strictement supérieur à 2 peut s'écrire comme somme de deux nombres premiers ;
** conjecture des [[#Nombres premiers jumeaux|nombres premiers jumeaux]] : il existe une infinité de jumeaux premiers ;
** [[conjecture de Legendre]] : il existe toujours au moins un nombre premier entre ''n''{{2}} et (''n'' + 1){{2}} ; cette conjecture est liée à l'[[hypothèse de Riemann]] et, comme cette dernière, reste non démontrée à ce jour ;
** existence d'une infinité de nombres premiers de la forme ''n''{{2}} + 1.
* L'existence d'une infinité de [[Nombre premier de Sophie Germain|nombres premiers de Sophie Germain]].
* La [[conjecture de Polignac]] (dont celle des nombres premiers jumeaux est le cas particulier ''n'' = 2) : tout entier naturel pair ''n'' peut s'écrire comme différence de deux nombres premiers consécutifs et cela d'une infinité de manières.
* L'[[hypothèse H de Schinzel]] : elle englobe la conjecture des nombres premiers jumeaux et le quatrième problème de Landau ; elle stipule que si l'on a une famille finie de polynômes à coefficients entiers, alors il existe une infinité d'entiers ''n'' tels que tous les polynômes de la famille donnent des nombres premiers quand on les évalue en ''n'' (à condition qu'il n'y ait pas d'obstruction évidente pour que ce soit le cas : par exemple, si un des polynômes est ''n''(''n'' + 1) ou 2''n'', ce n'est clairement pas possible).
* La [[#Conjecture de Bateman-Horn|conjecture de Bateman-Horn]] : elle précise l'hypothèse de Schinzel en donnant une valeur approchée du nombre des ''n'' < ''x'' ayant cette propriété.
* Y a-t-il une infinité de nombres premiers [[#Nombres premiers de Fermat|de Fermat]] ou [[#Nombres premiers de Mersenne|de Mersenne]] ou [[Nombre premier de Fibonacci|de Fibonacci]] ?
* Y a-t-il une infinité de [[nombre premier factoriel|nombres premiers factoriels]] ou [[nombre premier primoriel|primoriels]] ?
* Une conjecture de [[Daniel Shanks]] : soit la [[Théorème d'Euclide sur les nombres premiers#Démonstration d'Euclide|suite, dite d'Euclide-Mullin]], de premier terme ''u''<sub>1</sub> = 2 et telle que le terme ''u<sub>n</sub>'' soit le plus petit diviseur premier du [[Entier naturel|successeur]] du produit des termes ''u<sub>i</sub>'' pour {{nobr|''i < n''.}} La conjecture énonce que tous les nombres premiers apparaissent dans cette suite.
* La [[spirale d'Ulam]] (ou horloge d'Ulam) n'est à ce jour pas encore pleinement expliquée.

== Notes et références ==
{{Références nombreuses|taille=24}}

== Voir aussi ==
{{Autres projets
|commons=Category:Prime numbers
|wikt=nombre premier}}
{{catégorie principale}}
=== Bibliographie ===
==== Ouvrages cités ====
* {{Ouvrage|langue=en|prénom1=Henri|nom1=Cohen|lien auteur1=Henri Cohen (mathématicien)|titre=A Course in Computational Algebraic Number Theory|éditeur=|année=1993|isbn=|libellé=Cohen 1993|référence=Référence:Computational algebraic number theory (Cohen)}}. {{commentaire biblio SRL|Référence moderne sur les méthodes effectives en théorie des nombres.}}
* {{EllisonMendesFrance|libellé=Ellison et Mendès France 1975}}. {{commentaire biblio SRL|Livre très clair, comme introduction à la théorie analytique des nombres.}}
* {{Ouvrage|langue=en|auteur1=[[Fernando Q. Gouvêa]]|titre=P-adic Numbers|sous-titre=An Introduction|éditeur=|année=1997|isbn=|libellé=Gouvêa 1997|référence simplifiée=Référence:p-adic numbers (Gouvea)}}. {{commentaire biblio SRL|Introduction aux nombres p-adiques à la portée d'un large public, tournée vers des objectifs analytiques.}}
* {{HardyWrightFr|libellé=Hardy et Wright 2007}}. {{commentaire biblio SRL|Un grand classique d'introduction à la théorie des nombres, qui couvre les sujets de base (congruences), introduit les méthodes algébriques par l'exemple (entiers de Gauss, de Kronecker), et donne une démonstration du théorème des nombres premiers.}}
* {{NaudinQuitté|libellé=Naudin et Quitté 1992}}.
* {{Ouvrage|langue=en|auteur1=[[Paulo Ribenboim]]|titre=The New Book of Prime Number Records|éditeur=Springer|année=1996|numéro d'édition=3|isbn=|lire en ligne={{Google Livres|2VTSBwAAQBAJ}}|libellé=Ribenboim 1996}}.

=== Autres ouvrages ===
* {{Ouvrage|auteur1=[[Pierre Colmez]]|titre=Éléments d'analyse et d'algèbre (et de théorie des nombres)|éditeur=Éditions de l'École Polytechnique|année=2009|isbn=}}.
* {{Merveilleux nombres premiers}}.
* {{Ouvrage|auteur1=[[Michel Demazure]]|titre=Cours d'algèbre. Primalité, divisibilité, codes|éditeur=Cassini|année=1997|isbn=}}.{{commentaire biblio SRL|Ce livre contient de nombreux algorithmes écrits en [[Caml Light]].}}
* {{Ouvrage|auteur1=Michel Demazure|titre=Cours d'algèbre. Primalité, divisibilité, codes|éditeur=Cassini|année=2008|isbn=}}.{{commentaire biblio SRL|Version étendue (en particulier sur les [[code correcteur|codes correcteurs]]) de la première édition, la plupart des algorithmes ont été réécrits en [[Ruby]].}}
* Plusieurs ouvrages avec le même titre, mais des contenus très différents, ont paru aux [[Presses universitaires de France]] dans la collection « [[Que sais-je ?]] » :
** {{Ouvrage|auteur1=[[Émile Borel]]|titre=Les Nombres premiers|éditeur=PUF|collection=Que sais-je ?|numéro dans collection=571|année=1953}}.
** {{Ouvrage|auteur1=[[Jean Itard (1902-1979)|Jean Itard]]|titre=Les Nombres premiers|éditeur=PUF|collection=Que sais-je ?|numéro dans collection=571|année=1969}}.
** {{Ouvrage|auteur1=[[Gérald Tenenbaum]]|auteur2=[[Michel Mendès France]]|titre=Les Nombres premiers|éditeur=PUF|collection=[[Que sais-je ?]]|numéro dans collection=571|année=2000|année première édition=1997|pages totales=127|isbn=2-13-048399-2}}.
* {{Ouvrage|langue=fr|auteur1=Gérald Tenenbaum|auteur2=Michel Mendès France|titre=Les Nombres premiers, entre l'ordre et le chaos|lieu=Paris|éditeur=[[Éditions Dunod|Dunod]]|année=2014|numéro d'édition=2|pages totales=170|isbn=978-2-10-070656-3}}{{commentaire biblio SRL|Version étendue et mise à jour du précédent, avec par exemple des références au [[#Théorème de Green-Tao|théorème de Green-Tao]], ou aux résultats de [[Zhang Yitang]].}}

=== Articles connexes ===
* [[Inégalité de Bonse]]
* [[Primalité dans un anneau]]
* [[Problème de Lehmer]]
* [[Nombres premiers entre eux]]

=== Liens externes ===
{{Liens}}

==== Sites ====
* [[Pierre Colmez]], [http://www.math.jussieu.fr/~colmez/premiers.pdf « Les nombres premiers »] sur ''math.jussieu.fr''
* {{en}} [http://www.dms.umontreal.ca/~andrew/ Page d'Andrew Granville] sur ''dms.umontreal.ca''
* {{en}} {{langue|en|The prime numbers}} : {{OEIS|id=A000040}}
* [http://nombrespremiersliste.free.fr/ Une grande liste des nombres premiers (jusqu'à {{nombre|1000000000}})]
* {{Lien web|url=https://www.math93.com/index.php/histoire-des-maths/histoire-des-nombres/les-nombres-remarquables/167-premiers-les-nombres|titre=Les nombres premiers|site=math93.com}}
* [https://primenumbers.info/fr/ Test de primalité] sur ''primenumbers.info''


{{Palette|Classes de nombres premiers|Notion de nombre}}
{{Portail|théorie des nombres|cryptologie}}

[[Catégorie:Nombre premier|*]]
[[Catégorie:Arithmétique élémentaire]]