Nombre premier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
7 est un nombre 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 (qui sont alors 1 et lui-même). Ainsi, 1 n'est pas premier car il n'a qu'un seul diviseur entier positif ; 0 non plus car il est divisible par tous les entiers positifs. Par opposition, un nombre non nul produit de deux nombres entiers différents de 1 est dit composé. Par exemple 6 = 2 × 3 est composé, tout comme 21 = 3 × 7 ou 7 × 3, mais 11 est premier car 1 et 11 sont les seuls diviseurs de 11.

Les nombres 0 et 1 ne sont ni premiers ni composés.

Les vingt-cinq nombres premiers inférieurs à 100 sont :

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

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 n'existe pas de liste exhaustive (finie) de nombres premiers, car on sait depuis l'Antiquité qu'il existe une infinité de 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 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 ; par exemple 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 « 257 885 161 – 1 », qui comporte 17 425 170 chiffres en écriture décimale. On le doit à l'équipe de Curtis Cooper, à l'université du Central Missouri, dans le cadre de la grande chasse aux nombres premiers de Mersenne (GIMPS). Écrits les uns à la suite des autres, ses chiffres occuperaient plus de 4 000 pages en police Times New Roman taille 12.

Sommaire

Éléments historiques[modifier | modifier le code]

Les entailles retrouvées sur l’os d'Ishango daté à plus de 20 000 ans avant notre ère, mis au jour par l'archéologue Jean de Heinzelin de Braucourt[1] et antérieur à l'apparition de l'écriture (antérieur à 3 200 ans avant J.-C.), 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[2].

Des tablettes d'argile séchées attribuées aux civilisations qui se sont succédé en Mésopotamie durant le IIe millénaire av. J.-C. 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 et décaler de deux places le rang. Leur connaissance nécessitait une bonne compréhension de la multiplication, de la division et de la factorisation d'entiers. On peut alors légitiment penser qu'ils avaient remarqué la présence de nombre particulier : les nombres premiers. Mais il n'existe pas de preuve attestant de leur connaissance véritable.

Dans les mathématiques égyptiennes, le calcul fractionnaire demandait aussi des connaissances sur les opérations, les divisions d’entiers et les factorisations. Les Égyptiens ne notaient que les inverses d’entiers (1/2, 1/3, 1/4, 1/5, ...) ; l’écriture des fractions se faisait en additionnant des inverses d'entiers, si possible sans répétition (1/2 + 1/6 au lieu de 1/3 + 1/3). Disposer d’une liste des premiers nombres premiers devait être nécessaire.

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 (tomes VII à IX). Euclide donne la 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. Les connaissances présentées lui sont toutefois bien antérieures.

Jalons symboliques[modifier | modifier le code]

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 dans leur développement en base 10. Parmi ces records, battus ou à battre, on notera en particulier :

  • les nombres premiers titanesques (titanic primes), au delà de 1 000 chiffres (mille chiffres).
  • les nombres premiers géants (gigantic primes), au delà d'une longueur de 10 000 chiffres (dix mille chiffres).
  • les mega nombres premiers (megaprimes), au delà de 1 000 000 chiffres (un million de chiffres).
  • les beva nombres premiers (bevaprimes), au dela de 1 000 000 000 chiffres (un milliard de chiffres)

À fin 2012, 60 mega nombres premiers étaient connus[utm 1]. Le premier à être découvert fut le nombre de Mersenne « 26 972 593−1 » avec ses 2 098 960 chiffres, trouvé en 1999 par Nayan Hajratwala, participant à un projet GIMPS[mer 1],[utm 2].

L'Electronic Frontier Foundation offre des récompenses pour le franchissement de certains de ces jalons.

Historique du plus grand nombre premier connu[modifier | modifier le code]

Le record du plus grand nombre premier connu a presque toujours été trouvé parmi les nombres de Mersenne[utm 2].

Dans la littérature et dans le tableau ci-dessous, les nombres de Mersenne sont identifiés par les notations :

  • « Mn », où le nombre « n » accolé représente le rang dans la suite des nombres de Mersenne ;
  • « Mp », où l'indice « p » indique le nombre premier exposant de « 2 » dans l'expression « 2p - 1 » du nombre de Mersenne.
Tableau des records du mondes de taille de nombre premiers connus
Date Découvreur Machine Type Désignation Valeur Longueur en base 10 Source
Avant le XVIe siècle, il n'est pas possible de déterminer de manière précise les records de calcul du plus grand nombre premier.
Les documents qui nous sont parvenus permettant de justifier les calculs sont inexistants ou incomplets[3].
1588 Pietro Cataldi - Nombre de Mersenne M6 ou
M17
217 - 1 = 131 071 6 chiffres[utm 3] UTM - Caldwell[utm 3]
1588 Pietro Cataldi - Nombre de Mersenne M7 ou
M19
219 - 1 = 524 287 6 chiffres[utm 3] UTM - Caldwell[utm 3]
1750[Note 1] Leonhard Euler - Nombre de Mersenne M8 ou
M31
231 - 1 = 2 147 483 647 10 chiffres[utm 3] UTM - Caldwell[utm 3]
1867 Fortuné Landry - Diviseur de nombre de Mersenne M59 /
179 951
(259 - 1) / 179 951 = 3 203 431 780 337 13 chiffres[utm 3] UTM - Caldwell[utm 3]
1876 Édouard Lucas - Nombre de Mersenne M12 ou
M127
(2127 - 1) =
170 141 183 460 469 231 731 687 303 715 884 105 727
39 chiffres[utm 3] UTM - Caldwell[utm 3]
1951 Aimé Ferrier - Diviseur de nombre de Mersenne M148 /
17
(2148 - 1) / 17 =
20 988 936 657 440 586 486 151 264 256 610 222 593 863 921
44 chiffres[utm 3],[4] UTM - Caldwell[utm 3]
1951[mer 2] Miller et Wheeler[mer 2] EDSAC1[mer 2] Polynôme de nombre de Mersenne 180(M127)2 + 1 180 * (2127 - 1)2 + 1 79 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Robinson[mer 2] SWAC (en)[mer 2] Nombre de Mersenne M13 ou
M521
2521 - 1 157 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Robinson[mer 2] SWAC[mer 2] Nombre de Mersenne M14 ou
M607
2607 - 1 183 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Robinson[mer 2] SWAC[mer 2] Nombre de Mersenne M15 ou
M1279
21 279 - 1 386 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Robinson[mer 2] SWAC[mer 2] Nombre de Mersenne M16 ou
M2203
22 203 - 1 664 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Robinson[mer 2] SWAC[mer 2] Nombre de Mersenne M17 ou
M2281
22 281 - 1 687 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Riesel[mer 2] BESK (en)[mer 2] Nombre de Mersenne M18 ou
M3217
23 217 - 1 969 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Hurwitz[mer 2] IBM7090[mer 2] Nombre de Mersenne M20 ou
M4423
24 423 - 1 1 332 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Gillies[mer 2] ILLIAC 2[mer 2] Nombre de Mersenne M21 ou
M9689
29 689 - 1 2 917 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Gillies[mer 2] ILLIAC 2[mer 2] Nombre de Mersenne M22 ou
M9941
29 941 - 1 2 993 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Gillies[mer 2] ILLIAC 2[mer 2] Nombre de Mersenne M23 ou
M11213
211 213 - 1 3 376 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Tuckerman[mer 2] IBM360/91[mer 2] Nombre de Mersenne M24 ou
M19937
219 937 - 1 6 002 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Noll et Nickel[mer 2] CDC Cyber 174[mer 2] Nombre de Mersenne M25 ou
M21701
221 701 - 1 6 533 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Noll[mer 2] CDC Cyber 174[mer 2] Nombre de Mersenne M26 ou
M23209
223 209 - 1 6 987 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Nelson (en) et Slowinski (en)[mer 2] Cray-1[mer 2] Nombre de Mersenne M27 ou
M44497
244 497 - 1 13 395 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski[mer 2] Cray-1[mer 2] Nombre de Mersenne M28 ou
M86243
286 243 - 1 25 962 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski[mer 2] Cray X-MP[mer 2] Nombre de Mersenne M30 ou
M132049
2132 049 - 1 39 751 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski[mer 2] Cray X-MP/24[mer 2] Nombre de Mersenne M31 ou
M216091
2216 091 - 1 65 050 chiffres[mer 2] UTM - Caldwell[utm 4]
1989[mer 2] Amdahl 6[mer 2],[lcn 1] Amdahl 1200[mer 2] Polynôme de nombre de Mersenne 391581 × (M756839) + 391580 391581 × (2756 839) - 1 65 087 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski, Gage et al. [mer 2] Cray-2[mer 2] Nombre de Mersenne M32 ou
M756839
2756 839 - 1 227 832 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski & Gage[mer 2] Cray C90[mer 2] Nombre de Mersenne M33 ou
M859433
2859 433 - 1 258 716 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Slowinski et Gage[mer 2] Cray T94[mer 2] Nombre de Mersenne M34 ou
M1257787
21 257 787 - 1 378 632 chiffres[mer 2] UTM - Caldwell[utm 4]
[mer 2] Joël Armengaud, Woltman, et al.[mer 2],
(Projet GIMPS)
Pentium (90 Mhz)[mer 2] Nombre de Mersenne M35 ou
M1398269
21 398 269 - 1 420 921 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Gordon Spence, Woltman, et al.[mer 2],
(Projet GIMPS)
Pentium (100 Mhz)[mer 2] Nombre de Mersenne M36 ou
M2976221
22 976 221 - 1 895 932 chiffres[mer 2] GIMPS[mer 3]
[CS 1] Clarkson, Woltman, Kurowski, et al.[mer 2]
(Projet GIMPS)
Pentium (200 Mhz)[mer 2] Nombre de Mersenne M37 ou
M3021377
23 021 377 - 1 909 526 chiffres[CS 1] GIMPS[mer 3]
[mer 2] Hajratwala, Woltman, Kurowski, et al.[mer 2],
(Projet GIMPS)
Pentium (350 Mhz)[mer 2] Nombre de Mersenne M38 ou
M6972593
26 972 593 - 1 2 098 960 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Michael Cameron, Woltman, Kurowski, et al.[mer 2],
(Projet GIMPS)
AMD T-Bird (800 Mhz)[mer 2] Nombre de Mersenne M39 ou
M13466917
213 466 917 - 1 4 053 946 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Shafer, Woltman, Kurowski, et al.[mer 2],
(Projet GIMPS)
Pentium (2GHz)[mer 2] Nombre de Mersenne M40 ou
M20996011
220 996 011 - 1 6 320 430 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Findley, Woltman, Kurowski, et al.[mer 2],
(Projet GIMPS)
Pentium 4 (2,4GHz)[mer 2] Nombre de Mersenne M41[Note 2] ou
M24036583
224 036 583 - 1 7 235 733 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Nowak, Woltman, Kurowski, et al.[mer 2],
(Projet GIMPS)
Pentium 4 (2,4GHz)[mer 2] Nombre de Mersenne M42 [Note 3] ou
M25964951
225 964 951 - 1 7 816 230 chiffres[mer 2] GIMPS[mer 3]
[mer 2] Curtis Cooper et Steven Boone[mer 2],
University of Central Missouri
(Projet GIMPS)
Pentium 4
(2GHz upgraded to 3GHz)[mer 2]
Nombre de Mersenne M43 ??[Note 3] ou
M30402457
230 402 457 - 1 9 152 052 chiffres[mer 2] GIMPS[mer 3]
[mer 4] Curtis Cooper et Steven Boone[mer 2],
University of Central Missouri
(Projet GIMPS)
Pentium 4 (3 GHz)[mer 2] Nombre de Mersenne M44 ??[Note 3] ou
M32582657
232 582 657 - 1 9 808 358 chiffres[mer 4] GIMPS[mer 3]
Edson Smith[utm 5], Woltman, Kurowski et al.[mer 2],
UCLA (Projet GIMPS)
Intel Core 2 Duo E6600 CPU
(2.4 GHz)[mer 2]
Nombre de Mersenne M47 ??[Note 3] ou
M43112609
243 112 609 - 1 12 978 189 chiffres[lcn 2] GIMPS[mer 3]
Curtis Cooper, G. Woltman, S. Kurowski, et al. [mer 2],
University of Central Missouri
(Projet GIMPS)
Nombre de Mersenne M57885161 257 885 161 - 1 17 425 170 chiffres GIMPS[mer 3]

Historique des nombres premiers tous connus ou dénombrés en dessous d'un seuil[modifier | modifier le code]

Découvrir un nouveau nombre premier plus grand que tous les autres n'implique pas de connaître tous les nombres premiers plus petit que ce dernier.

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.

Ce défi fut notamment relevé, jusqu'au seuil de 100 000 000, par le mathématicien autrichien Jakob Philipp Kulik (de) (1793-1863), au XIXe siècle[gv 1] :

Date Seuil s Quantité \pi(s)(*) Proportion \pi(s) / s Vérificateurs Méthode
Antiquité[gv 1] 10    4 0,400 ou 40 % Ératosthène, Euclide Essais par division[gv 1]
Antiquité[gv 1] 100    25 0,250 ou 25 % Ératosthène, Euclide Essais par division[gv 1]
Antiquité[gv 1] 1 000    168 0,168 ou 16,8 % Ératosthène, Euclide Essais par division[gv 1]
 ? 7 919[U 1] 1 000 0,126 ou 12,6 %  ? Essais par division[gv 1]
 ? 10 000     1 229 0,123 ou 12,29 %  ? Essais par division[gv 1]
1746[gv 1] 100 000[gv 1] 9 592 0,096 ou 9,59 %  ? Essais par division[gv 1]
1996[U 2] 104 729[U 2] 10 000 0,095 ou 9,55 %  ? Autre calcul automatisé
1797[gv 1] 400 000[gv 1]  ?  ?  ? Essais par division[gv 1]
1996[CS 2] 611 953[CS 2] 50 000 0,082 ou 8,17 %  ? Autre calcul automatisé
1811[gv 1] 1 000 000[gv 1] 78 498 0,078 ou 7,85 %  ? Essais par division[gv 1]
 ? 15 485 863[utm 6] 1 000 000[utm 6] 0,065 ou 6,46 % Chris Caldwell[utm 6] Autre calcul automatisé
1863[gv 1] 100 330 200[gv 1]  ?  ? Jakob Philipp Kulik (de)[gv 1] Essais par division[gv 1]
 ? 179 424 673[utm 6] 10 000 000[utm 6] 0,056 ou 5,57 % Chris Caldwell[utm 6] Autre calcul automatisé
 ? 982 451 653[utm 6] 50 000 000[utm 6] 0,051 ou 5,09 % Chris Caldwell[utm 6] Autre calcul automatisé
2010[utm 7] 276 =
75 557 863 725 914 323 419 136[utm 7]
1 462 626 667 154 509 638 735[utm 7] 0,019 ou 1,94 % Jens Franke et al.[utm 7] Évaluation directe de \pi(s)
2010[utm 7] 277 =
151 115 727 451 828 646 838 272[utm 7]
2 886 507 381 056 867 953 916[utm 7] 0,019 ou 1,91 % Jens Franke et al.[utm 7] Évaluation directe de \pi(s)
2010[utm 7] 1024 =
1 000 000 000 000 000 000 000 000[utm 7]
18 435 599 767 349 200 867 866[utm 7] 0,018 ou 1,84 % Jens Franke et al.[utm 7] Évaluation directe de \pi(s)

Notes :
(*)   \pi(s) est la quantité totale de nombres premiers situés sous le seuil s (c'est-à-dire dans l'intervalle d'entiers [0, s]).

La connaissance de \pi(s) par un calcul algorithmique n'implique pas nécessairement que chacun des nombres premiers soit immédiatement identifiable.
La décomposition en facteurs permet au contraire d'identifier les nombres premiers individuellement.

Structures algébriques, topologiques, et nombres premiers[modifier | modifier le code]

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[5]. 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 x=\frac{a}{b} est un nombre rationnel non nul sous forme irréductible et que p^\alpha et p^\beta sont les plus grandes puissances de p divisant a et b, la norme p-adique de x est p^{\beta-\alpha}. 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 XXe siècle. 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[6].

Nombres premiers particuliers[modifier | modifier le code]

Il existe plusieurs types remarquables de nombres premiers, issus de modèles et formules mathématiques particuliers.

Article détaillé : Liste de nombres premiers.

Les quelques cas rappelés ci-dessous font état des catégories connues de longue date.

Aucune de ces catégories ne contient la totalité des nombres premiers. Inversement, aucune de ces catégories n'est incluse dans l'ensemble des nombres premiers.

Nombres premiers de Pythagore[modifier | modifier le code]

Page d'aide sur l'homonymie Ne doit pas être confondu avec Nombre de Pythagore ni Constante de Pythagore.

On appelle usuellement nombre premier de Pythagore (en) tout nombre premier de la forme 4n + 1, où n est un entier naturel. Par exemple, 5, 13, 17 sont des nombres premiers de Pythagore (suite A002144 de l'OEIS). Selon le théorème des deux carrés, ces nombres premiers sont les seuls nombres premiers impairs que l'on peut écrire comme somme de deux carrés.

Nombres premiers d'Euclide[modifier | modifier le code]

Article détaillé : Nombre d'Euclide.

Les nombres d'Euclide sont des entiers de la forme E_n = p_n# + 1, où p_n# est la primorielle de p_n, qui est lui-même le nième nombre premier. Leur nom provient du mathématicien grec de l'Antiquité Euclide, qui les utilisa dans sa preuve originale de l'existence d'une infinité de nombres premiers. Tous les nombres d'Euclide ne sont pas premiers.

Nombres premiers de Mersenne[modifier | modifier le code]

Article détaillé : Nombre premier de Mersenne.

Les nombres premiers de la forme :

M_p = 2^p - 1

p est lui-même un nombre 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.

Entre 2008 et 2012, le plus grand nombre premier connu était M43 112 609 = 243 112 609 – 1, qui comporte 12 978 189 chiffres en écriture décimale. Il s'agit (chronologiquement) du 45e nombre premier de Mersenne connu (noté « M45 ») et sa découverte a été annoncée le grâce aux efforts du projet collaboratif de calcul distribué « Great Internet Mersenne Prime Search » (GIMPS). Le 46e nombre premier de Mersenne (noté « M46 »), 237 156 667 – 1, qui est inférieur au précédent a été découvert deux semaines plus tard ; le était découvert, par le même projet GIMPS, le 47e nombre premier de Mersenne (noté « M47 »), 242 643 801 – 1, lui aussi inférieur au premier cité.

Le , ce record a été battu par la preuve (toujours par GIMPS) de la primalité de M57 885 161 = 257 885 161 – 1, nombre qui comporte plus de 17 millions de chiffres en écriture décimale[mer 3].

L'Electronic Frontier Foundation offre un prix de calcul coopératif d'un montant de 100 000 dollars pour la découverte d'un nombre premier d'au moins 10 millions de chiffres décimaux, afin d'encourager les internautes à contribuer à la résolution de problèmes scientifiques par le calcul distribué ; ce prix devrait donc à nouveau être attribué à GIMPS ; l'EFF offre également des prix plus importants (de 150 000 et 250 000 dollars respectivement) pour la découverte de nombres premiers de 100 millions et 1 milliard de chiffres décimaux[7].

Nombres premiers de Fermat[modifier | modifier le code]

Article détaillé : Nombre de Fermat.

Les nombres de la forme :

F_n = 2^{2^n} + 1

sont appelés les nombres de Fermat. Fermat avait conjecturé que tous ces nombres devaient être premiers. Cependant, les seuls nombres de Fermat premiers connus sont F_0, F_1, F_2, F_3 et F_4. Le calcul donne :

  • F_0 = 2^{1} + 1 = 3\,
  • F_1 = 2^{2} + 1 = 5\,
  • F_2 = 2^{4} + 1 = 17\,
  • F_3 = 2^{8} + 1 = 257\,
  • F_4 = 2^{16} + 1 = 65\,537\,

Le nombre de Fermat F_5 n’est pas premier

  • F_5 = 2^{32} + 1 = 4\,294\,967\,297\,

En effet, il est divisible par 641.

4\,294\,967\,297\, / 641\, = 6\,700\,417\,

Il s'agit du premier contre-exemple à cette conjecture de Fermat, découvert par Euler en 1732.

Nombres premiers de De Polignac[modifier | modifier le code]

Les nombres premiers de Polignac sont des couples de nombres premiers consécutifs dont la différence est égal à un nombre pair donné.

Selon la valeur du nombre pair n, les couples de nombres premier concernés portent des noms différents.

Il est conjecturé qu'il existe une infinité de nombres premiers associés, pour chaque valeur de n.

Article détaillé : Conjecture de De Polignac.

Nombres premiers jumeaux[modifier | modifier le code]

Article détaillé : Nombres premiers jumeaux.

Deux nombres premiers sont dits jumeaux s'ils ne diffèrent que de 2. Hormis pour le couple (2, 3), cette distance de deux est la plus petite distance possible entre deux nombres premiers.

Les plus petits nombres premiers jumeaux sont 3 et 5, 5 et 7, 11 et 13.

Nombres premiers cousins[modifier | modifier le code]

Ils correspondent à un écart de 4.

Article détaillé : Nombres premiers cousins.

Nombres premiers sexy[modifier | modifier le code]

Ils correspondent à un écart de 6. Leur nom vient d'une proximité phonétique entre "six" et "sex".

Article détaillé : Nombres premiers sexy.

Algorithmique : calcul des nombres premiers et tests de primalité[modifier | modifier le code]

Crible d'Ératosthène et algorithme par essais de division[modifier | modifier le code]

Article détaillé : Crible d'Ératosthène.

Les premiers algorithmes pour décider si un nombre est premier (appelés tests de primalité) consistent à essayer de le diviser par tous les nombres inférieurs à 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éduit 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 inférieurs à 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 complexité algorithmique exponentielle.

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[8].

Le crible d'Ératosthène : nombres premiers inférieurs à 120.

Autres algorithmes[modifier | modifier le code]

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[9].

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 à 1-2-k : 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 Miller-Rabin, qui sont des améliorations, car ils admettent moins de nombres pseudo-premiers[10].

L'algorithme AKS mis au point en 2002 permet de déterminer si un nombre donné N est premier en utilisant un temps de calcul polynomial.

Des formules sur les nombres premiers[modifier | modifier le code]

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 n associe le ne nombre premier. De manière un peu plus souple, on peut se contenter d'exiger une fonction f qui à tout entier 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[11]. Par exemple, le théorème de Wilson assure que p est un nombre premier si et seulement si (p-1)! \equiv -1 \mod p. Il s'ensuit que la fonction f\left( n\right) = 2 + \left( {2 \left((n-1)! \right)} \mod {\left( n\right)} \right)\, vaut n si n est un nombre premier et vaut 2 sinon. Cependant, le calcul de la factorielle (même modulo n) est rédhibitoire pour de grandes valeurs de n, et cette fonction a donc peu de valeur pour générer les nombres premiers.

Il est donc tentant de chercher des fonctions polynômes 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[12].

La recherche de polynômes vérifiant une propriété plus faible s'est développée à partir de la notion d'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 Putnam, Matiyasevich, Davis et Robinson, 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, le polynôme suivant, de degré 25 à 26 variables (de a à z), a été déterminé par Jones, Sato, Wada et Wiens en 1976 :

(k+2)[1 – (wz+h+j–q)2 – [(gk+2g+k+1)(h+j) + h – z]2– (2n+p+q+z–e)2 – [16(k+1)3(k+2)(n+1)2 + 1 –f2]2– [e3(e+2)(a+1)2 + 1 – o2]2 – [(a2–1)y2 + 1–x2]2– [16r2y4(a2–1) + 1 – u2]2

– [((a+u2(u2–a))2–1)(n+4dy)2 + 1 – (x+cu)2]2 –[n+l+v–y]2– [(a2–1)l2 + 1 – m2]2 – [ai+k+1–l–i]2 – [p + l(a–n–1) + b(2an+2a–n2–2n–2) – m]2 – [q+ y(a–p–1) + s(2ap + 2a – p2 – 2p – 2) – x]2

– [z + pl(a–p) + t(2ap – p2 – 1) – pm]2]

De même que pour les formules à factorielles, l'exploitation de ce polynôme ne donne aucun résultat en pratique car il ne donne pratiquement que des valeurs négatives quand on fait varier les variables a à z de 0 à l'infini.

La notion d'ensemble diophantien s'est plus généralement développée à partir des problèmes posés par le dixième problème de Hilbert sur les équations diophantiennes[13].

Répartition des nombres premiers[modifier | modifier le code]

Infinité des nombres premiers[modifier | modifier le code]

Euclide a démontré dans ses Éléments (proposition 20 du Livre IX) que les nombres premiers sont en plus grande quantité que toute quantité proposée de nombres premiers. Autrement dit, il existe une infinité de nombres premiers. La démonstration d'Euclide repose sur la constatation qu'une famille finie p1,...,pn 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)[14].

D'autres démonstrations de l'infinité des nombres premiers ont été données. La preuve d'Euler[15] utilise l'identité :

\sum_{n=1}^\infin \ \frac{1}{n} \ = \ \prod_{p\in\mathcal{P}} \ \frac{1}{1-1/p}.

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.

Furstenberg fournit une preuve utilisant une argumentation topologique[16].

Les avancées du XIXe siècle[modifier | modifier le code]

La 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.

Le résultat sur l'infinité des nombres premiers amène des questions plus précises concernant la fonction qui à un nombre réel x associe \pi (x), le nombre de nombres premiers inférieurs à x, et qui tend donc vers l'infini [14]. Une conjecture importante au XIXe siècle, formulée par Adrien-Marie Legendre et Carl Friedrich Gauss, était que cette fonction de compte des nombres premiers est équivalente à la fonction x \mapsto \frac{x}{\ln(x)} quand x tend vers l'infini, c'est-à-dire que la proportion de nombres premiers parmi les nombres inférieurs à x (soit \frac{\pi(x)}{x}) tend vers 0 à la vitesse de \frac{1}{\ln(x)}. Avant la démonstration de la conjecture à la fin du siècle, un résultat partiel[17] avait été démontré par Pafnouti Tchebychev, l'existence de deux constantes explicites C et D telles qu'on ait l'encadrement, pour x assez grand :

C\leq\pi(x)\frac{\ln(x)}{x}\leq D.

L'inégalité de Tchebychev permettait notamment de 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[18]. Plus généralement, les résultats sur la fonction de compte des nombres premiers permettent d'obtenir des résultats sur le ne nombre premier ; par exemple les résultats d'Ishikawa de 1934 sont des conséquences directes des théorèmes de Tchebychev : pn + pn + 1 > pn + 2 et pnpm > pn + m, où pn désigne le ne nombre premier (avec p1=2) ; ou encore, d'après un résultat de Felgner de 1990 : 0,91 n ln(n) < pn < 1,7 n ln(n)[19].

La démonstration analytique d'Euler sur l'infinité des nombres premiers peut être vue comme un premier pas vers la résolution de problèmes plus avancés. Elle consiste essentiellement à étudier le comportement de la fonction zêta de Riemann en 1 au moyen de ce qu'il est convenu d'appeler un produit eulérien, et d'en déduire la divergence de la série des inverses des nombres premiers. En reprenant cette étude, 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 fonction L de Dirichlet, Dirichlet a été capable d'adapter la démonstration aux 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. Plus précisément, les nombres premiers sont é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)[20].

La conjecture de Legendre et Gauss a été démontrée indépendamment par Jacques Hadamard et Charles-Jean de La Vallée Poussin en 1896[21], et porte le nom de théorème des nombres premiers. Ces démonstrations nécessitent 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 plus grand qu'un simple voisinage de 1 : 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 1 dans le plan complexe[22]. La puissance des outils d'analyse complexe a conduit au développement 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 est devenu 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.

Ultérieurement, au cours du XXe siècle, des démonstrations du théorème des nombres premiers ont été trouvées qui ne recourent pas à l'analyse complexe, notamment par Erdős et Selberg [21].

Théorème de Green-Tao[modifier | modifier le code]

Le théorème de Green-Tao, démontré en 2004 par Ben Joseph Green et Terence Tao, généralise notamment un 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 :

a,\,a+b,\,a+2b,\,\dots,\,a+(k-1)b.

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 :

2^{2^{2^{2^{2^{2^{2^{100k}}}}}}}

(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 \delta strictement positif, pour tout x suffisamment grand, si P est un ensemble de nombres premiers inférieurs à x contenant au moins \delta\pi(x) éléments, alors P contient au moins une progression arithmétique de nombres premiers comptant k termes[23].

Conjecture de Bateman-Horn[modifier | modifier le code]

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 f1,...,fk des polynômes de degré 1, 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 fi(n). On note \omega(p) 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 f1(t)=t, et f2(t)=t+1. Il est alors conjecturé que le nombre d'entiers n plus petits qu'un réel x tels que les valeurs f1(n),...,fk(n) sont simultanément premières, est, pour x assez grand, de l'ordre de :

\left(\prod_{p}\frac{1-\frac{\omega(p)}{p}}{\left(1-\frac{1}{p}\right)^k}\right)\frac{x}{\log|f_1(x)|\dots \log|f_k(x)|}.

Le théorème des nombres premiers correspond au cas k=1 et ft=t, le théorème de Dirichlet à k=1 et ft=at+b, et pour k=2, f1(t)=t et f2(t)=t+2, on obtient une version quantitative (et donc plus générale) de la conjecture des nombres premiers jumeaux.

Applications[modifier | modifier le code]

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 choisi volontairement entiers pour une application.

Les nombres premiers, et la théorie des nombres en particulier, ont longtemps été vus comme un sujet purement mathématique, avec peu ou pas d'applications extérieures. Cela changea d'un seul coup dans les années 1970, quand des nouveaux systèmes de cryptographie basés sur les propriétés des nombres premiers furent découverts.

Cryptographie à clé publique[modifier | modifier le code]

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 RSA), basé sur les propriétés des nombres premiers et de la factorisation[24]. 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 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.

Nombres déduits de nombres premiers[modifier | modifier le code]

Des séquences de nombres peuvent être à leur tour construites à partir de séquences de nombres premiers.

Nombre interpremier[modifier | modifier le code]

Un nombre interpremier est la moyenne de deux nombres premiers consécutifs[MathWorld 1]. Aucun de ces nombres interpremiers ne peut être premier, sans quoi il existerait un nombre premier entre deux nombres premiers consécutifs, ce qui est impossible.

Ils peuvent être pairs ou impairs.

Les plus petits nombres interpremiers sont : 4, 6, 9, 12, 15, 18, 21, 26, 30, 34, etc.

Voir suite A024675 de l'OEIS pour davantage d'exemples.

Généralisations des nombres premiers[modifier | modifier le code]

La notion de nombre premier s'est vue généralisée au cours du dix-neuvième siècle 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 entiers de Gauss ou celui des 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, suite aux travaux de Dedekind et Kronecker[25] : en termes modernes, on dit que ces anneaux ont une structure d'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 xp+yp=zp si p est un nombre premier vérifiant une condition portant sur la nature de l'anneau des entiers algébriques engendré par une racine primitive p-ème de l'unité ; c'est-à-dire si p est ce qu'on appelle un nombre premier régulier.

Conjectures et questions ouvertes[modifier | modifier le code]

Il y a beaucoup de conjectures et de questions ouvertes sur les nombres premiers. Par exemple :

  • La conjecture de Goldbach : tout nombre pair strictement supérieur à 2 peut s'écrire comme somme de deux nombres premiers.
  • La conjecture de De Polignac : tout entier naturel pair peut s'écrire comme différence de deux nombres premiers consécutifs et cela d'une infinité de manières.
  • La conjecture des nombres premiers jumeaux : il existe une infinité de jumeaux premiers (cas particulier de la conjecture de De Polignac pour n=2).
  • Toute suite de Fibonacci généralisée dont les deux termes initiaux sont premiers entre eux contient-elle une infinité de nombres premiers ?
  • Existe-t-il une infinité de nombres premiers de Fermat ou de Mersenne ?
  • Y a-t-il une infinité de nombres premiers de la forme n² + 1 ?
  • Y a-t-il une infinité de nombres premiers factoriels ?
  • Y a-t-il une infinité de nombres premiers primoriels ?
  • Une conjecture de Daniel Shanks : soit la suite, dite d'Euclide-Mullin, de premier terme u1=2 et telle que le terme un soit le plus petit nombre premier diviseur du produit des termes ui, pour i<n augmenté de 1. La conjecture énonce que tous les nombres premiers apparaissent dans cette suite.
  • La conjecture de Legendre : il existe toujours au moins un nombre premier entre n² et (n+1)² ; cette conjecture est liée à l'hypothèse de Riemann et, comme cette dernière, reste non démontrée à ce jour.
  • L'hypothèse H de Schinzel : elle englobe la conjecture des nombres premiers jumeaux ; elle stipule que si 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ôme est n(n+1) ou 2n, ce n'est clairement pas possible).
  • La conjecture de Bateman-Horn : elle précise l'hypothèse de Schinzel en donnant une valeur approchée du nombre de n ayant cette propriété.
  • L'existence d'une infinité de nombres premiers de Sophie Germain.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Le huitième nombre de Mersenne (M8) fut trouvé en 1750 mais publié en 1772.
  2. M41 prouvé le premier décembre 2011 comme étant bien le 41e. Voir http://mersenne.org/report_milestones/.
  3. a, b, c et d On ne sait pas s'il existe ou non un ou plusieurs autres nombres premiers de Mersenne entre le 41e (M24 036 583) et le 47e (M43 112 609). Dans cet intervalle, le classement est donc provisoire. Déjà le 29e nombre premier de Mersenne fut découvert après le 30e et le 31e, de même que M43 112 609 fut découvert quinze jours avant M37 156 667, plus petit. De même le 46e (M42 643 801) a été découvert neuf mois après le 47e (M43 112 609).

Site de l'OEIS[modifier | modifier le code]

Site mersenne.org du GIMPS[modifier | modifier le code]

  1. (en)GIMPS press release, GIMPS Finds First Million-Digit Prime.
  2. a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, aa, ab, ac, ad, ae, af, ag, ah, ai, aj, ak, al, am, an, ao, ap, aq, ar, as, at, au, av, aw, ax, ay, az, ba, bb, bc, bd, be, bf, bg, bh, bi, bj, bk, bl, bm, bn, bo, bp, bq, br, bs, bt, bu, bv, bw, bx, by, bz, ca, cb, cc, cd, ce, cf, cg, ch, ci, cj, ck, cl, cm, cn, co, cp, cq, cr, cs, ct, cu, cv, cw, cx, cy, cz, da, db, dc, dd, de, df, dg, dh, di, dj, dk, dl, dm, dn, do, dp, dq, dr, ds, dt, du, dv et dw (en)mersenne.org GIMPS : Finding World Record Primes Since 1996.
  3. a, b, c, d, e, f, g, h, i, j, k, l et m (en)[1]; UCLA, Projet GIMPS.
  4. a et b (en)www.mersenne.org GIMPS : Project Discovers Largest Known Prime Number, 232 582 657 - 1.

Site de l'University of Arizona[modifier | modifier le code]

  1. a et b (en)www.cs.arizona.edu The University of Arizona : A Large Prime Number.
  2. a et b (en) www.cs.arizona.edu The University of Arizona : List of 50000 Primes.

Site de l'University of Tennessee in Martin[modifier | modifier le code]

  1. (en)Chris Caldwell, The Largest Known Primes at The Prime Pages.
  2. a et b (en)Chris Caldwell, The Largest Known Prime by Year: A Brief History at The Prime Pages.
  3. a, b, c, d, e, f, g, h, i, j, k et l (en)primes.utm.edu The Largest Known Prime by Year: A Brief History - Part One: Before Electronic Computers.
  4. a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u et v (en)primes.utm.edu The Largest Known Prime by Year: A Brief History - Part Two: The Age of Electronic Computers.
  5. (en)primes.utm.edu Titan : Edson Smith.
  6. a, b, c, d, e, f, g, h et i (en) primes.utm.edu The first fifty million primes (Prof. Chris K. Caldwell).
  7. a, b, c, d, e, f, g, h, i, j, k et l (en) primes.utm.edu Conditional Calculation of pi(10^24).

Site de l'University of Utah[modifier | modifier le code]

  1. (en)www.math.utah.edu The University of Utah : The 1,000 smallest prime numbers.
  2. a et b (en) www.math.utah.edu The University of Utah : The 10,000 smallest prime numbers.

Site de Gérard Villemin[modifier | modifier le code]

  1. a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u et v villemin.gerard.free.fr Nombres premiers : Historique.

Site de Landon Curt Noll[modifier | modifier le code]

  1. (en)www.isthe.com Site de Landon Curt Noll : Amdahl 6.
  2. (en)prime.isthe.com Site de Landon Curt Noll : 243 112 609 - 1 is prime.

Site MathWorld de Eric Weisstein[modifier | modifier le code]

  1. (en)mathworld.wolfram.com MathWorld : Interprimes.

Autres références[modifier | modifier le code]

  1. Voir Marcus du Sautoy, La symphonie des nombres premiers, p. 42.
  2. Préhistoire de la géométrie : le problème des sources, article d'Olivier Keller.
  3. Delahaye, p. 166-167.
  4. zabaque.uqac.ca Zabaque.net : Les nombres premiers.
  5. Naudin Quitté, début du chapitre 3.
  6. Gouvêa 1997.
  7. Récompenses offertes par l'EFF (en).
  8. Cohen 1993, début du chapitre 8, notamment l'algorithme 8.1.1.
  9. Cohen 1993, chapitre 10, plus particulièrement la section 5.
  10. Voir Naudin Quitté, chap. 4, section 6 ou Cohen 1993, chap. 8, section 2.
  11. Ribenboim 1996, introduction du chapitre 3.
  12. Ribenboim 1996, chap. 3, section II.
  13. Ribenboim 1996, chap. 3, section III.
  14. a et b Hardy Wright, section 2.1.
  15. (la) Léonard Euler, Variae observationes circa series infinitas, Commentarii academiae scientiarum Petropolitanae 9, (1744), 160-188, ou Opera Omnia, Series 1, Volume 14, 217 - 244. Téléchargeable à [2]. 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.
  16. Ribenboim 1996 recense par ailleurs de nombreuses autres preuves.
  17. Ribenboim 1996, chap. 4, section I.
  18. Hardy Wright, chap. 22, sections 1 à 4.
  19. Ribenboim 1996, chap. 4, section II, A.
  20. Hardy Wright, théorème 15 ; Ellison&Mendès France, chap. 7.
  21. a et b Ellison&Mendès France, chap. 2, section 1.2.
  22. Ellison&Mendès France, chap. 2, théorème 2.4, puis section 4.
  23. Tous ces résultats proviennent de (en) Andrew Granville, Prime Number Patterns, document de vulgarisation qui contient de nombreuses autres conséquences amusantes du résultat de Green et Tao.
  24. (en) Ronald Rivest, Adi Shamir et Leonard Adleman, « A Method for Obtaining Digital Signatures and Public-Key Cryptosystems », Communications of the ACM, vol. 21, no 2,‎ 1978, p. 120-126 (lire en ligne).
  25. Nicolas Bourbaki, Éléments d'histoire des mathématiques, chapitre Algèbre commutative. Théorie des nombres algébriques.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie[modifier | modifier le code]

Version étendue et mise à jour du précédent, avec par exemple des références au théorème de Green-Tao, ou aux résultats de Zhang Yitang.

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]