vignette|Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge. vignette|Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts.
Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et 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é , 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 = 2 × 2 qui en possède 3 (à savoir 1, 2 et 4), 9 = 3 × 3 qui en possède 3 (à savoir 1, 3 et 9) et 12 = 2 × 2 × 3 qui en possède 6 (à savoir 1, 2, 3, 4, 6 et 12).
Selon cette définition, les nombres 0 et 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 , certains mathématiciens, grâce à une définition légèrement différente des nombres premiers, ont considéré que 1 était premier. Mais au début du , un consensus a abouti à la définition donnée ici, qui exclut 1 des nombres premiersC. 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. , en particulier pour garantir un énoncé simple du théorème fondamental de l'arithmétique.
Les vingt-cinq nombres premiers inférieurs à 100 sont :
De telles 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 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 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 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 cryptographiques et des méthodes de transmission de l'information. Les nombres premiers sont aussi utilisés pour construire des tables de hachage et pour constituer des générateurs de nombres pseudo-aléatoires.
Découvert le , le plus grand nombre premier connu est le nombre premier de Mersenne , qui comporte plus de de chiffres en écriture décimale.
Éléments historiques Les entailles retrouvées sur l'os d'Ishango daté à plus de avant notre ère, mis au jour par l'archéologue Jean de Heinzelin de BraucourtVoir Marcus du Sautoy, La Symphonie des nombres premiers, . et antérieur à l'apparition de l'écriture (antérieur à ), 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..
Des tablettes d'argile séchées attribuées aux civilisations qui se sont succédé en Mésopotamie durant le 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 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), puisque . Leur connaissance nécessitait une bonne compréhension de la multiplication, de la division. Dans les 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 () ; l’écriture des fractions se faisait en additionnant ces « inverses d'entiers », si possible sans répétition ( au lieu de ).. Mais il n'y a pas de trace de factorisation d'entiers ou de nombres premiers dans ces textesKawai Lui remarque aussi dans sa thèse qu'en dépit de compétences techniques bien supérieures, il ne semble pas que les nombres premiers (ni d'ailleurs les coniques) aient été remarqués en Chine avant le , lorsque les missionnaires occidentaux les firent connaître..
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 d’Euclide (livres VII à 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.
Jalons symboliques L'esprit ludique et l'émulation ont amené des mathématiciens à définir des seuils de gigantisme pour les nombres premiers, exprimés en nombre de chiffres en base dix. Parmi ces records, battus ou à battre, on notera en particulier : les nombres premiers titanesques (), au-delà de mille chiffres, les nombres premiers gigantesques (), au-delà de dix mille chiffres, les méga-nombres premiers (), au-delà d'un million de chiffres.
En , premiers étaient connus Chris Caldwell, The Largest Known Primes at The Prime Pages.. Le premier à être découvert fut, en 1999, le nombre de Mersenne 2 − 1 avec ses GIMPS press release, GIMPS Finds First Million-Digit Prime. Chris Caldwell, 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., grâce aux efforts du projet collaboratif de calcul distribué (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 pour sa découverte en 2008 du premier nombre premier d'au moins dix millions de chiffres décimaux. L'EFF offre encore et respectivement pour la découverte du premier nombre premier de cent millions et un milliard de chiffres décimaux EFF Cooperative Computing Awards..
Historique du plus grand nombre premier connu
Le record du plus grand nombre premier connu a presque toujours été trouvé parmi les nombres de Mersenne, comme le dernier en date, 2136.279.841 – 1, un nombre découvert le , ayant 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.
Date Seuil Quantité (*) Vérificateurs Méthode Antiquité 168 Ératosthène, Euclidevillemin.gerard.free.fr Nombres premiers : Historique. Essais par division 1746 ? 1797 1811 1863 Mathématicien autrichien (1793-1863) : 2010 primes.utm.edu Conditional Calculation of pi(10^24). 276 = Jens Franke Évaluation directe de 277 = 1024 ≈
Notes : (*) est la quantité totale de nombres premiers situés sous le seuil (c'est-à-dire dans l'intervalle d'entiers ).
Structures algébriques, topologiques, et nombres premiers 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 des 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 pgcd, ppcm, et de nombres premiers entre eux, qui sont utiles pour la résolution de certaines équations diophantiennes, notamment la caractérisation des 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 structures 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 groupes abéliens finis. 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éorie de Sylow.
Les nombres premiers interviennent aussi dans les structures topologiques. Le corps des nombres rationnels admet une structure topologique habituelle, qui donne par complétion le corps des nombres réels. Pour chaque nombre premier p, une autre structure topologique peut être construite, à partir de la norme suivante : si est un nombre rationnel non nul sous forme irréductible et que et sont les plus grandes puissances de p divisant a et b, la norme p-adique de x est . En complétant le corps des rationnels suivant cette norme, on obtient le corps des nombres p-adiques, introduit par Kurt Hensel au début du . 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.
Nombres premiers particuliers
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
On appelle parfois nombre premier « de Pythagore » tout nombre premier de la forme 4n + 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 somme de deux carrés.
Nombres premiers de Mersenne
vignette|redresse|Marin Mersenne.
Les nombres premiers de la forme :
où p est alors nécessairement aussi premier, sont appelés nombres premiers de 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.