Nombre premier

Ensembles d'entiers base divisibilité- Vue d'ensemble Factorisation Entier Diviseur Diviseur unitaire Fonction diviseur Premier facteur Théorème fondamental de l'arithmétique Les formes de factorisation Nombre premier Numéro Composite Nombre semi-premier numéro Nombre oblong Nombre sphénique Numéro sans Square- Nombre puissant Puissance parfaite Numéro d'Achille Nombre lisse Nombre régulier Chiffre approximatif Nombre inhabituel Sommes contraints de diviseurs Nombre parfait Nombre presque parfait Nombre quasi parfait Nombre parfait multiple numéro de Hemiperfect Nombre hyperparfait Numéro Superperfect Nombre parfait unitaire Nombre semi-parfait Numéro Pratique Avec de nombreux diviseurs Nombre abondant Nombre abondant Primitive Nombre hautement abondant Nombre superabondant Nombre colossalement abondant Nombre hautement composé Nombre hautement composé Supérieur Nombre étrange Relatif à séquences aliquotes Nombre intouchable Numéro amiable Nombre sociable Numéro fiancée Autres séries Nombre déficient Numéro bienvenus Numéro solitaire Nombre sublime Numéro de diviseur harmonique Nombre frugal Nombre équidigital Nombre extravagant

En mathématiques , un nombre premier (ou un premier) est un nombre naturel (plus d'un), qui a exactement deux distincts nombre naturel diviseurs : 1 et lui-même. Une infinité de nombres premiers existe, comme démontré par Euclid autour 300 BC. Les trente premiers nombres premiers 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, 97, 101, 103, 107, 109, 113
(Séquence A000040 dans OEIS )

Voir la liste des nombres premiers pour une liste plus longue. Le numéro un est, par définition, pas un nombre premier; voir la discussion ci-dessous en vertu de primalité d'un .

La propriété d'être un premier est appelé primalité, et le mot Premier est également utilisé comme un adjectif. Depuis deux est le seul nombre premier, le terme premier impair se réfère à ne importe quel nombre premier supérieur à deux.

L'étude des nombres premiers est partie de la théorie des nombres , la branche des mathématiques qui englobe l'étude des nombres naturels. Les nombres premiers ont fait l'objet d'intenses recherches, mais certaines questions fondamentales, telles que le Hypothèse de Riemann et de la conjecture de Goldbach , ont été en suspens pendant plus d'un siècle. Le problème de la modélisation de la distribution des nombres premiers est un sujet populaire d'investigation pour les théoriciens des nombres: quand on regarde des numéros individuels, les nombres premiers semblent être distribués de façon aléatoire, mais la répartition "globale" des nombres premiers suit lois bien définies.

La notion de nombre premier a été généralisé dans de nombreuses branches différentes des mathématiques.

• En la théorie des anneaux, une branche de l'algèbre abstraite , le terme «élément principal» a une signification particulière. Ici, une valeur non nulle, non-unité d'un élément annulaire est défini pour être premier si chaque fois qu'un divise bc pour les éléments de l'anneau B et C, puis a divise au moins l'un des b ou c. Avec ce sens, l'inverse additif de tout nombre premier est aussi premier. En d'autres termes, lorsque l'on considère l'ensemble des nombres entiers comme anneau, -7 est un élément primordial. Sans autre précision, cependant, "nombre premier" signifie toujours un premier entier positif. Parmi anneaux de complexe entiers algébriques, Eisenstein amorce, et Nombres premiers gaussiennes peuvent aussi être d'intérêt.
• Dans la théorie des nœuds , un Premier noeud est un noeud qui ne peut être écrit comme la somme de nœud de deux nœuds moins triviaux.

Histoire de nombres premiers

Le Crible d'Ératosthène est une simple, ancienne algorithme pour trouver tous les nombres premiers jusqu'à un entier spécifié. Il est le prédécesseur de la moderne Crible d'Atkin, qui est plus rapide mais plus complexe. Le crible d'Eratosthène éponyme a été créée dans le 3ème siècle avant JC par Eratosthène, un grec ancien mathématicien .

Il ya des indices dans les dossiers survivants des anciens Egyptiens qu'ils avaient une certaine connaissance des nombres premiers: la Expansions fraction égyptiens dans le Papyrus Rhind, par exemple, ont des formes très différentes de nombres premiers et pour les composites. Cependant, les premiers enregistrements de survivants de l'étude explicite des nombres premiers viennent des Grecs de l'Antiquité . Éléments d'Euclide (circa 300 BC) contient théorèmes importants sur les nombres premiers, y compris l'infinité de nombres premiers et théorème fondamental de l'arithmétique . Euclide a également montré comment construire un nombre parfait d'un Premier de Mersenne. Le Crible d'Ératosthène, attribué à Eratosthène, est une méthode simple pour calculer les nombres premiers, bien que les grands nombres premiers trouvés aujourd'hui avec les ordinateurs ne sont pas générés de cette façon.

Après les Grecs, peu se est passé avec l'étude des nombres premiers jusqu'à ce que le 17ème siècle. En 1640, Pierre de Fermat a déclaré (sans preuve) Le petit théorème de Fermat (plus tard prouvé par Leibniz et Euler ). Un cas particulier du théorème de Fermat peut avoir été connu beaucoup plus tôt par les Chinois. Fermat conjecturé que tous les numéros de la forme 2 ^{2 n} + 1 sont premiers (ils sont appelés Fermat numéros) et il a vérifié ce jusqu'à n = 4. Cependant, le lendemain nombre de Fermat 2 ³² 1 est composite (l'un de ses facteurs premiers est de 641), comme Euler découvrit plus tard, et en fait pas plus loin nombres de Fermat sont connus d'être premier. Le moine français Marin Mersenne regarda premiers de la forme 2 ^p - 1, avec p un nombre premier. Ils s'appellent Nombres premiers de Mersenne dans son honneur.

Le travail d'Euler en théorie des nombres inclus de nombreux résultats sur les nombres premiers. Il a montré la série infinie _^1/2 + _^1/3 + _^1/5 + _^1/7 + _^1/11 + ... est divergente. En 1747, il a montré que les nombres même parfaits sont précisément les entiers de la forme 2 ^{p -1} (2 ^p -1) où le deuxième facteur est un nombre premier de Mersenne. On croit pas nombres parfaits impairs existent, mais il ya encore aucune preuve.

Au début du 19ème siècle, Legendre et Gauss indépendamment conjecturé que x tend vers l'infini, le nombre de nombres premiers jusqu'à x est asymptotique à x / log (x), où log (x) est le logarithme naturel de x. Idées de Riemann dans son document de 1859 sur la fonction zeta esquissé un programme qui conduirait à une preuve du théorème des nombres premiers. Ce schéma a été complété par Hadamard et de la Vallée Poussin, qui a prouvé indépendamment théorème des nombres premiers en 1896.

Prouver un nombre est premier ne est pas fait (pour un grand nombre) par division de procès. Beaucoup de mathématiciens ont travaillé sur tests de primalité pour un grand nombre, souvent limités à des formes numériques spécifiques. Ceci comprend Le test de Pépin pour nombres de Fermat (1877), Théorème de Proth (environ 1 878), le Test de Lucas-Lehmer pour les nombres de Mersenne (origine 1856), et de la généralisation Test de Lucas-Lehmer. Algorithmes plus récents comme APRT-CL, ECPP et AKS travaillent sur un nombre arbitraire mais restent beaucoup plus lent.

Pendant longtemps, les nombres premiers étaient considérés comme ne ayant aucune application possible à l'extérieur de mathématiques pures; cela a changé dans les années 1970 lorsque les concepts de cryptographie à clé publique ont été inventés, dans lequel les nombres premiers forment la base des premiers algorithmes tels que le Algorithme de cryptage RSA.

Depuis 1951, tous les plus grands nombres premiers connus ont été trouvés par les ordinateurs . La recherche de plus en plus grands nombres premiers a suscité un intérêt en dehors des cercles mathématiques. Le Great Internet Mersenne Prime Search et d'autres projets de calcul distribué pour trouver grands nombres premiers sont devenus populaires dans les dix à quinze dernières années, tandis que les mathématiciens continuent de lutter avec la théorie des nombres premiers.

Primalité d'un

Jusqu'au 19ème siècle, la plupart des mathématiciens considéré comme le numéro 1 un premier, et il ya encore un grand corps de travail mathématique qui est valide malgré l'étiquetage 1 un premier, comme le travail de Stern et Zeisel. Liste de Derrick Lehmer Norman de nombres premiers jusqu'à 10006721, réimprimé aussi tard que 1956 ,, a commencé avec une comme son premier premier. Henri Lebesgue est dit être le dernier mathématicien professionnel d'appeler une prime. Le changement de l'étiquette produit de sorte que le théorème fondamental de l'arithmétique , comme indiqué, est valide, ce est à dire, "chaque numéro a une unique factorisation en facteurs premiers"

Prime diviseurs

Illustration montrant que 11 est un nombre premier alors que 12 ne est pas.

Le théorème fondamental de l'arithmétique stipule que tout nombre entier positif supérieur à 1 peut être écrit comme un produit d'un ou plusieurs nombres premiers d'une manière qui est unique, sauf peut-être pour la commande des premiers facteurs . Le même facteur principal peut se produire plusieurs fois. Primes peut donc être considéré comme les «blocs de construction de base" des nombres naturels. Par exemple, nous pouvons écrire

et tout autre factorisation de 23 244 comme le produit de nombres premiers sera identique à l'exception de l'ordre des facteurs. Il y a beaucoup de algorithmes de factorisation en nombres premiers pour ce faire dans la pratique pour un plus grand nombre.

L'importance de ce théorème est l'une des raisons de l'exclusion de l'une de l'ensemble des nombres premiers. Si une ont été admis en tant que premier, la déclaration précise du théorème serait exiger des qualifications supplémentaires.

Propriétés de nombres premiers

• Lorsque écrit en base 10 , tous les nombres premiers, sauf deux et cinq fin en 1, 3, 7 ou 9. (numéros se terminant par 0, 2, 4, 6 ou 8 représentent des multiples de deux et les numéros se terminant par 0 ou 5 représentent des multiples de 5.)

• Si p est un nombre premier et p divise un produit ab des entiers, alors p divise a ou p divise b. Cette proposition a été prouvé par Euclide et est connu comme Lemme d'Euclide. Il est utilisé dans quelques preuves de l'unicité de facteurs premiers.

• Le anneau Z / n Z (voir arithmétique modulaire ) est un domaine si et seulement si n est un nombre premier. En d'autres termes: n est premier si et seulement si φ (n) = n - 1.

• Si p est premier et un est tout entier, puis un ^p - a est divisible par p ( Le petit théorème de Fermat).

• Si p est un nombre premier différent de 2 et 5, ¹ / _p est toujours décimal périodique dont la période est p - 1, ou un diviseur de p - 1. Ceci peut être déduit directement de Le petit théorème de Fermat. ¹ / _p exprimé également dans q de base (autre que la base 10) a un effet similaire, à condition que p ne est pas un facteur premier de q. L'article sur décimales récurrentes montre quelques-unes des propriétés intéressantes.

• Un entier p> 1 est premier si et seulement si la factorielle (p - 1)! + 1 est divisible par p ( Théorème de Wilson). A l'inverse, un nombre entier n> 4 est composite si et seulement si (n - 1)! est divisible par n.

• Si n est un nombre entier positif supérieur à 1, alors il n'y a toujours un nombre premier p avec n <p <2 n ( Le postulat de Bertrand).

• Ajout inverses de tous les nombres premiers ensemble des résultats dans un divergent série infinie ( la preuve). Plus précisément, si S (x) représente la somme des inverses de tous les nombres premiers p, avec p ≤ x, alors S (x) = ln ln x + O (1) pour x → ∞.

• Dans chaque progression arithmétique a, a q +, a + 2 q, a + 3 q, ... où les entiers a et q sont positifs premiers entre eux, il existe une infinité de nombres premiers ( Théorème de la progression arithmétique).

• Le caractéristique de chaque champ est soit zéro, soit un nombre premier.

• Si G est un fini groupe p et ⁿ est le plus grande puissance du nombre premier p qui divise l'ordre de G, alors G a un sous-groupe d'ordre p ^n. ( Théorèmes de Sylow.)

• Si G est un groupe fini et p est un nombre premier divisant l'ordre de G, alors G contient un élément d'ordre p. ( Cauchy Théorème)

• Le nombre premier théorème dit que la proportion des nombres premiers de moins de x est asymptotique à ¹ / _{x ln} (en d'autres termes, lorsque x devient très grande, la probabilité qu'un nombre inférieur à x est un nombre premier est inversement proportionnelle au nombre de chiffres de x ).

• Le Copeland-Erdős constante 0,235711131719232931374143 ..., obtenu par concaténation des nombres premiers en base dix , est connu pour être un nombre irrationnel .

• La valeur de la Fonction zêta de Riemann à chaque point dans le plan complexe est donné comme un prolongement méromorphe d'une fonction, définie par un produit sur l'ensemble de tous les nombres premiers pour Re (s)> 1:

Évaluer cette identité à différents entiers fournit un nombre infini de produits au cours des nombres premiers dont les valeurs peuvent être calculés, les deux premiers étant

• Si p> 1, le polynôme est irréductible sur Z / p Z si et seulement si p est premier.

Classification des nombres premiers

Deux façons de classer les nombres premiers, la classe et la classe n + n -, ont été étudiés par Paul Erdős et John Selfridge.

Détermination de la classe n + d'un nombre premier p implique regardant le plus grand facteur premier de p + 1. Si ce plus grand facteur premier est 2 ou 3, alors p est la classe 1+. Mais si ce grand facteur premier est un autre premier q, alors la classe n + p est un de plus que la classe n + q. Séquences A005105 travers A005108 liste classe 1+ à travers les nombres premiers de la classe.

La classe n - est presque la même que la classe n +, sauf que la factorisation de p - 1 est regardé à la place.

Le nombre des nombres premiers

Il existe une infinité de nombres premiers

La plus ancienne preuve de la déclaration qu'il ya infiniment de nombres premiers est donnée par le mathématicien grec Euclide dans ses Éléments (Livre IX, Proposition 20). Euclid indique le résultat comme "il ya plus de ne importe quel nombre [finis] donné des nombres premiers", et sa preuve est essentiellement la suivante:

Considérons un ensemble fini de nombres premiers. Multipliez tous ensemble et ajouter une (voir Nombre d'Euclide). Le nombre obtenu ne est pas divisible par aucun des nombres premiers dans l'ensemble fini nous avons considéré, parce divisant par l'un de ces donnerait un reste d'un. Parce que tous les numéros non-prime peut être décomposé en un produit de nombres premiers sous-jacentes, alors soit ce nombre est premier résultante elle-même, ou se il ya un nombre premier ou nombres premiers dont le nombre résultante peut être décomposée en, mais ne sont pas dans l'ensemble fini d'origine des nombres premiers. De toute façon, il ya au moins un plus de choix qui ne était pas dans l'ensemble fini nous avons commencé avec. Cet argument se applique peu importe ce que nous avons commencé ensemble fini avec. Donc, il ya plus de primes que ne importe quel nombre fini donné.

Cet argument précédente explique pourquoi le produit P de fini de nombres premiers plus 1 doit être divisible par certains Premier pas parmi ces fini de nombres premiers (peut-être lui-même).

La preuve est parfois formulée dans un chemin qui mène à l'étudiant de conclure que P + 1 doit lui-même être premier, et je pense que la preuve d'Euclide dit le produit préférentiel majoré de 1 est toujours premier. L'exemple simple (2 · 3 · 5 · 7 · 11 · 13) + 1 = 30 031 = 59 509 · (deux nombres premiers) montre que ce ne est pas le cas. En fait, ne importe quel ensemble de nombres premiers qui ne inclut pas deux aura un produit étrange. Ajout de 1 à ce produit sera toujours produire un nombre pair, qui sera divisible par 2 (et donc ne pas être premier).

Autres mathématiciens ont donné d'autres preuves. L'un d'eux (en raison d' Euler ) montre que la somme des inverses des nombres premiers diverge. Autre la preuve sur la base Nombres de Fermat a été donnée par Goldbach. Kummer est particulièrement élégant et Harry Furstenberg fournit en utilisant une topologie générale.

Compter le nombre des nombres premiers en dessous d'un nombre donné

Même si le nombre total de nombres premiers est infinie, on pouvait encore se demander «Environ combien de nombres premiers sont là ci-dessous 100 000?", Ou "Quelle est la probabilité d'un numéro à 20 chiffres au hasard pour être premier?".

Le Premier comptage fonction π (x) est défini comme le nombre de nombres premiers jusqu'à x. Il ya connus algorithmes pour calculer les valeurs exactes de π (x) plus vite que ce serait possible de calculer chaque premier à x. Les valeurs aussi grandes que π (10 ²⁰⁾ peuvent être calculés rapidement et avec précision avec les ordinateurs modernes. Ainsi, par exemple, π (100 000) = 9,592, et π (10 ²⁰⁾ = 2.220.819.602.560.918.840.

Pour les plus grandes valeurs de x, au-delà de la portée de l'équipement moderne, le théorème des nombres premiers fournit une bonne estimation: π (x) est d'environ x / ln (x). Même meilleures estimations sont connus.

Lieu de nombres premiers

Trouver nombres premiers

L'ancien Crible d'Ératosthène est un moyen simple de calculer tous les nombres premiers jusqu'à une limite donnée, en faisant une liste de tous les entiers et à plusieurs reprises la suppression des multiples de nombres premiers déjà trouvé. Le moderne Crible d'Atkin est plus compliqué, mais plus rapide lorsqu'il est correctement optimisé.

Dans la pratique, on veut souvent pour vérifier si un nombre donné est premier, plutôt que de générer une liste de nombres premiers. En outre, il est souvent satisfaisante pour connaître la réponse avec une forte probabilité . Il est possible de vérifier rapidement si un grand nombre donné (disons, jusqu'à quelques milliers de chiffres) est premier en utilisant probabiliste tests de primalité. Ces choisissent généralement un nombre aléatoire appelé un «témoin» et vérifier une formule impliquant le témoin et le premier N potentiel. Après plusieurs itérations, ils déclarent que N soit «certainement composite» ou «probablement premier". Certains de ces tests ne sont pas parfaits: il peut y avoir certains nombres composés, appelés pseudopremiers pour le test respective, qui sera déclaré «probablement premier" peu importe ce témoin est choisi. Cependant, les tests les plus populaires probabilistes ne souffrent pas de cet inconvénient.

Un procédé pour déterminer si un nombre est premier est de diviser par tous les nombres premiers inférieur ou égal à la racine carrée de ce nombre. Si l'une des divisions venus, comme un entier, puis le numéro d'origine ne est pas un nombre premier. Sinon, ce est un nombre premier. On n'a pas vraiment calculer la racine carrée; une fois on voit que la quotient est inférieur au dénominateur, on peut arrêter. Ceci est connu comme division de première instance; ce est le test de primalité simple et il devient rapidement impraticable pour tester de grands entiers parce que le nombre de facteurs possibles croît de façon exponentielle le nombre de chiffres dans les augmentations numéro à-être-testés.

tests de primalité

Un algorithme de test de primalité est un algorithme qui teste un certain nombre de primalité, à savoir si le nombre est un nombre premier.

• Test de primalité AKS
• Test de primalité de Fermat
• Test de Lucas-Lehmer
• Test de primalité Solovay-Strassen
• Test de primalité de Miller-Rabin
• Courbe elliptique primalité proving

Un Premier probable est un entier qui, en vertu d'avoir passé un certain test, est considéré comme probablement premier. Nombres premiers probables qui sont en fait composite (tels que Nombres de Carmichael) sont appelés pseudopremiers.

En 2002, des scientifiques indiens à IIT Kanpur découvert un nouvel algorithme déterministe connu sous le nom AKS algorithme. La quantité de temps que cela prend algorithme pour vérifier si un nombre N est premier dépend d'un fonction polynomiale du nombre de chiffres du N (c. du logarithme de N).

Formules rendement nombres premiers

Il ne est pas connue formule de nombres premiers qui est plus efficace de trouver des nombres premiers que les méthodes mentionnées ci-dessus sous la rubrique «Trouver des nombres premiers".

Il ya un ensemble de Équations diophantiennes en 9 variables et un paramètre avec la propriété suivante: le paramètre est premier si et seulement si le système d'équations résultant a une solution sur les nombres naturels. Ceci peut être utilisé pour obtenir une formule simple avec la propriété que toutes ses valeurs positives sont premiers.

Il n'y a pas polynomiale , même dans plusieurs variables, qui ne prend que des valeurs de premier ordre. Par exemple, le polynôme f curieux dans une variable (n) = n ² - n + 41 cède nombres premiers pour n = 0, ..., 40,43 mais f (41) et f (42) sont composite. Cependant, il ya des polynômes en plusieurs variables, dont les valeurs positives que les variables prendre toutes les valeurs entières positives sont exactement les nombres premiers.

Une autre formule est basée sur le théorème de Wilson mentionné ci-dessus, et génère le nombre deux plusieurs fois et toutes les autres primes exactement une fois. Il existe d'autres formules similaires qui produisent également des nombres premiers.

Les types particuliers de nombres premiers de formules de nombres premiers

Un nombre premier p est appelé primorial ou premier-factorielle si elle a la forme p = n # ± 1 pour un certain nombre n, où n # désigne le produit 2 · 3 · 5 · 7 · 11 · ... de tous les nombres premiers ≤ n. Un premier est appelé factorielle si elle est de la forme ! n ± 1. Les premiers nombres premiers factoriels sont:

n! - 1 est un nombre premier pour n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, ... (séquence A002982 dans OEIS )

n! + 1 est premier pour n = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, ... (séquence A002981 dans OEIS )

Le plus grand nombre premier connu est primorial Π (392 113) + 1, trouvé par Heuer en 2001. Le plus grand nombre premier connu est factorielle 34790! - 1, trouvé par Marchal, Carmody et Kuosa en 2002. On ne sait pas se il existe une infinité de nombres premiers primorial ou factoriels.

Premiers de la forme 2 ^p - 1, où p est un nombre premier, sont connus comme Nombres premiers de Mersenne, tandis que les nombres premiers de la forme sont connus comme Fermat amorce. Nombres premiers p où 2 p + 1 est aussi premier sont connus comme Sophie Germain amorce. La liste suivante est d'autres types spéciaux de nombres premiers qui viennent de formules:

Certains nombres premiers sont classés en fonction des propriétés de leurs chiffres en décimal ou d'autres bases. Par exemple, des nombres dont les chiffres forment un séquence palindromique sont appelés palindromiques nombres premiers, et un nombre premier est appelé Premier truncatable si la suppression successivement le premier chiffre à la droite seulement les rendements de nouveaux nombres premiers gauche ou.

• Pour une liste des classes spéciales de nombres premiers Voir Liste des nombres premiers

La distribution des nombres premiers

La répartition de l'ensemble des nombres premiers dans la plage de 1 à 76 800, de gauche à droite et de haut en bas, dans laquelle chaque pixel représente un nombre. Les pixels noirs signifient que nombre est premier et blanc signifie qu'il ne est pas premier.

Le problème de la modélisation de la distribution des nombres premiers est un sujet populaire d'investigation pour les théoriciens des nombres. Les nombres premiers sont répartis entre les nombres naturels d'une manière (à ce jour) imprévisible, mais il ne semble y avoir des lois régissant leur comportement. Leonhard Euler commenté

Les mathématiciens ont tenté en vain de cette journée pour découvrir un peu d'ordre dans la séquence des nombres premiers, et nous avons raison de croire que ce est un mystère dans lequel l'esprit ne sera jamais pénétrer. (Havil 2003, p. 163)

Paul Erdős dit

Dieu ne peut pas jouer aux dés avec l'univers, mais quelque chose d'étrange qui se passe avec les nombres premiers. [Se référant à Albert Einstein célèbre la conviction de que «Dieu ne joue pas aux dés avec l'univers."]

Dans une conférence 1975, Don Zagier commenté

Il ya deux faits sur la répartition des nombres premiers dont je espère vous convaincre si massivement qu'ils seront gravés en permanence dans vos cœurs. La première est que, en dépit de leur définition simple et le rôle que les blocs de construction des nombres naturels, les nombres premiers poussent comme des mauvaises herbes entre les nombres naturels, semblant obéir à aucune autre loi que celle du hasard, et personne ne peut prédire où la prochaine va germer. Le deuxième fait est encore plus étonnant, car il affirme tout le contraire: que les nombres premiers présentent une régularité étonnante, qu'il ya des lois régissant leur comportement, et qu'ils obéissent à ces lois avec une précision quasi militaire.

(Havil 2003, p. 171)

Image supplémentaires avec 2310 colonnes est liée ici, la préservation des multiples de 2,3,5,7,11 dans les colonnes respectives.

Les écarts entre les nombres premiers

Soit p _n le n-ième nombre premier (p-à-dire ₁ = 2, p = ₂ 3, etc.). L'écart entre la _n g consécutive nombres premiers p et _n p _{n + 1} est la différence entre eux, à savoir

g _n = p _{n + 1} - P _n.

Nous avons g ₁ = 3-2 = 1, g ₂ = 5-3 = 2, ₃ g = 7-5 = 2, ₄ g = 11-7 = 4, et ainsi de suite. La séquence (g _n) de premiers espaces a été largement étudiée.

Pour tout nombre naturel N supérieur à 1, la séquence (pour la notation N! Lire factorielle )

N! + 2, N! + 3, ..., N! + N

est une séquence de N - 1 composites entiers consécutifs. Par conséquent, il existe des écarts entre les nombres premiers qui sont arbitrairement grand, à savoir pour ne importe quel nombre entier naturel N, y est un nombre entier avec n g _n> N. (Choisissez n sorte que p _n est le plus grand nombre premier inférieur à N! + 2.)

D'autre part, les écarts se arbitrairement petit en proportion des nombres premiers: le quotient g _n / _n p se approche de zéro lorsque n tend vers l'infini. Notez également que le conjecture des nombres premiers jumeaux affirme que g _n = 2 pour une infinité d'entiers n.

Lieu de la plus grand nombre premier connu

Wikinews a des nouvelles liées: Équipe informatique CMSU découvre un autre record taille Premier

Wikinews a des nouvelles liées: L'informatique distribuée découvre plus grand nombre premier connu

Le plus grand nombre premier connu, à partir de Août 2007, est 2 ^32582657 - 1 (ce nombre est 9,808,358 chiffres); ce est la 44e connu Premier de Mersenne. M _32582657 a été trouvé sur 4 septembre 2006 par Curtis Cooper et Steven Boone, professeurs à la Université du Missouri Central (anciennement Central Missouri State University) et les membres d'un effort de collaboration appelé GIMPS. Avant de trouver le premier, Cooper et Boone ont couru le logiciel GIMPS sur un pic de 700 ordinateurs universitaires pendant 9 ans.

Les deux prochains grands nombres premiers connus sont également Mersenne Primes: M = _30402457 ^30402457 2 - 1 (43e Mersenne premier connu, 9.152.052 chiffres) et M = _25964951 ^25964951 2 - 1 (42e Mersenne premier connu, 7.816.230 chiffres). Historiquement, le premier plus grand connu a presque toujours été un premier de Mersenne depuis l'aube des ordinateurs électroniques, car il existe un test de primalité particulièrement rapide pour les numéros de cette forme, le Test de Lucas-Lehmer pour les nombres de Mersenne.

Le plus grand nombre premier connu qui ne est pas un premier de Mersenne est 19249 × 2 ^13018586 + 1 (3.918.990 chiffres), un Nombre de Proth. Ce est aussi le septième plus grand nombre premier connu de toute forme. Il a été constaté sur 26 mars 2007 par le Dix-sept ou un projet de poitrine et il les rapproche un peu plus pour résoudre le Problème de Sierpinski.

Certains des plus grands nombres premiers pas connu pour avoir une forme particulière (ce est pas de formule simple comme celle des nombres premiers de Mersenne) ont été trouvés en prenant un morceau de données binaires semi-aléatoires, le convertissant en un nombre n, multipliant par 256 ^k pour un entier positif k, et la recherche de nombres premiers possibles dans l'intervalle [256 ^k n + 1, 256 ^k (n + 1) - 1].

Prix pour trouver des nombres premiers

Le Electronic Frontier Foundation (EFF) a offert un US $ 100 000 prix aux premiers découvreurs d'un premier avec au moins 10 millions de chiffres. Ils offrent également 150.000 dollars pour 100 millions de chiffres, et 250.000 $ pour 1 milliard de chiffres. En 2000, ils payés $ 50 000 pour 1 millions de chiffres.

Le Factorisation RSA a offert des prix jusqu'à US $ 200 000 pour trouver les facteurs premiers de certains semiprimes jusqu'à 2048 bits. Cependant, le défi a été fermé en 2007 après beaucoup de petits prix pour les petits semiprimes avaient été versés.

Généralisations du concept Premier

Le concept de nombre premier est si important qu'il a été généralisé de différentes manières dans diverses branches des mathématiques.

Premiers éléments dans les anneaux

On peut définir éléments premiers et éléments irréductibles à toute intègre. Pour toute domaine de factorisation unique, comme l'anneau Z des entiers, l'ensemble des éléments premiers égale l'ensemble des éléments irréductibles, qui pour Z est {..., -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, ...}.

A titre d'exemple, nous considérons le Entiers de Gauss Z [i], ce est-à nombres complexes de la forme a + bi avec a et b dans Z. Ce est un domaine intégrante, et ses éléments principaux sont la Nombres premiers gaussienne. Notez que la figure 2 est un premier pas gaussienne, car il Facteurs dans le produit des deux nombres premiers de Gauss (1 + i) et (1 - i). L'élément 3, cependant, reste premier dans les entiers de Gauss. En général, les nombres premiers rationnels (ie des éléments fondamentaux dans l'anneau Z des entiers) de la forme 4 k + 3 nombres premiers sont gaussiennes, alors que nombres premiers rationnels de la forme 4 k + 1 ne sont pas.

Prime idéaux

En la théorie des anneaux, une remplace généralement la notion de nombre avec celui de idéal. Prime idéaux sont un outil et objet d'étude dans importante algèbre commutative, théorie algébrique des nombres et géométrie algébrique. Les idéaux premiers de l'anneau des entiers sont les idéaux (0), (2), (3), (5), (7), (11), ...

Un problème central en théorie algébrique des nombres est de savoir comment un idéal premier de facteurs quand il se est levé à un champ d'extension. Par exemple, dans l'exemple entier gaussien ci-dessus, (2) ramifie en une puissance motrice (1 + i et 1 - i générer le même idéal premier), idéaux premiers de la forme (4 k + 3) sont inertes (rester Premier) , et les idéaux premiers de la forme (4 k + 1) split (sont le produit de deux idéaux premiers distincts).

Primes en théorie d'évaluation

En la théorie du champ de classe encore une autre généralisation est utilisé. Compte tenu d'un arbitraire corps K, on considère évaluations sur K, certaines fonctions de K à la R nombres réels. Chaque telle évaluation donne un topologie sur K, et deux évaluations sont appelés équivalents se ils donnent la même topologie. Un premier de K (parfois appelé un lieu de K) est une classe d'équivalence des valorisations. Avec cette définition, les nombres premiers de la zone de Q des nombres rationnels sont représentés par la norme valeur absolue fonction (connu sous le nom "prime infini") ainsi que par la p valorisations -adiques sur Q, pour tout nombre premier p.

Prime noeuds

Dans la théorie des nœuds , un nœud est un Premier noeud qui est, dans un certain sens, indécomposable. Plus précisément, il en est une qui ne peut être écrite comme la noeud somme de deux noeuds non triviaux.

Questions ouvertes

Il ya beaucoup de questions ouvertes sur les nombres premiers. Une très importante est le Hypothèse de Riemann, qui dit essentiellement que les nombres premiers sont aussi régulièrement distribués que possible. D'un point de vue physique, il déclare à peu près que l'irrégularité dans la distribution des nombres premiers vient seulement de bruit aléatoire. D'un point de vue mathématique, il déclare à peu près que la distribution asymptotique des nombres premiers (environ 1 / log x des nombres inférieurs à x sont des nombres premiers, les théorème des nombres premiers) vaut aussi pour des intervalles beaucoup plus courtes de longueur sur la racine carrée de x (pour des intervalles près de x). Cette hypothèse est généralement considérées comme correctes, en particulier, l'hypothèse la plus simple est que les nombres premiers ne devraient pas avoir d'importantes irrégularités sans bonne raison.

Beaucoup de conjectures célèbres semblent avoir une très forte probabilité d'être vrai (dans un sens formel, beaucoup d'entre eux suivent des arguments probabilistes heuristiques simples):

• Premier Numéros Euclide: On ne sait pas si oui ou non il ya un nombre infini de nombres premiers Euclide.

• Forte conjecture de Goldbach : Chaque entier pair supérieur à 2 peut être écrit comme une somme de deux nombres premiers.

• Faible conjecture de Goldbach: Chaque entier impair supérieur à 5 peut être écrit comme une somme de trois nombres premiers.

• Conjecture des nombres premiers jumeaux: Il ya une infinité de nombres premiers jumeaux, des paires de nombres premiers avec la différence 2.

• La conjecture de Polignac: Pour tout entier positif n, il existe une infinité de nombres premiers consécutifs paires de qui diffèrent par 2 n. Lorsque n = 1 ce est la conjecture des nombres premiers jumeaux.

• Une forme plus faible de la conjecture de Polignac: Chaque même nombre est la différence de deux nombres premiers.

• Il est largement admis, il ya une infinité de Nombres premiers de Mersenne, mais pas Fermat amorce.

• On suppose qu'il ya une infinité de nombres premiers de la forme n ² + 1.

• Beaucoup de conjectures bien connus sont des cas particuliers de la large Hypothèse de H. de Schinzel

• On suppose qu'il existe une infinité de nombres Fibonacci amorce.

• Legendre de la conjecture: Il est un nombre premier entre ² et n (n + 1) ² pour tout entier positif n.

• De Cramer la conjecture: . Cette conjecture implique Legendre, mais son statut est plus incertain.

• Conjecture de Brocard: Il ya toujours au moins quatre premiers entre les carrés de nombres premiers consécutifs supérieurs à 2.

Tous les quatre Problèmes de Landau de 1912 sont énumérés ci-dessus et encore non résolu: Goldbach, nombres premiers jumeaux, Legendre, n ² 1 nombres premiers.

Applications

Pendant longtemps, la théorie des nombres en général, et l'étude des nombres premiers en particulier, a été considérée comme l'exemple canonique de mathématiques pures, sans applications en dehors de l'intérêt d'étudier le sujet. En particulier, les théoriciens des nombres tels que la Colombie- mathématicien GH Hardy se vantait de faire un travail qui ne avait absolument aucune importance militaire. Cependant, cette vision a été brisée dans les années 1970, quand il a été annoncé publiquement que les nombres premiers pourraient être utilisés comme base pour la création de algorithmes de cryptographie à clé publique. Les nombres premiers sont également utilisés pour Les tables de hachage et des générateurs de nombres pseudo-aléatoire.

Certains machines à rotor ont été conçus avec un nombre différent de broches sur chaque rotor, le nombre de broches sur l'un ou l'autre premier rotor, ou premier avec le nombre de broches sur tout autre rotor. Cela a permis de générer le cycle complet des positions de rotor possibles avant de répéter ne importe quelle position.

Cryptographie à clé publique

Plusieurs algorithmes de cryptographie à clé publique, comme RSA, sont basées sur des grands nombres premiers (par exemple avec 512 bits).

Les nombres premiers dans la nature

Beaucoup de numéros se produisent dans la nature, et, inévitablement, certains d'entre eux sont premiers. Il ya, cependant, relativement peu d'exemples de nombres qui apparaissent dans la nature parce qu'ils sont premiers. Par exemple, la plupart étoiles de mer ont cinq bras, et 5 est un nombre premier. Cependant, il ne existe aucune preuve pour suggérer que les étoiles de mer ont cinq bras parce 5 est un nombre premier. En effet, certaines étoiles de mer ont des nombres différents de bras. Echinaster luzonicus a normalement six bras, Luidia senegalensis a neuf bras, et Solaster endeca peut avoir jusqu'à vingt bras. Pourquoi la majorité des étoiles de mer (et la plupart des autres échinodermes) ont cinq symétrie reste un mystère.

Un exemple de l'utilisation de nombres premiers dans la nature est aussi une stratégie évolutionniste utilisée par cigales du genre Magicicada. Ces insectes passent la plupart de leur vie souterrain larves. Ils ne se transforment en pupes puis sortent de leurs terriers après 13 ou 17 ans, à quel point ils volent, race, puis meurent au bout de quelques semaines tout au plus. La logique de cette méthode semble être que les intervalles de nombres premiers entre émergences, il est très difficile pour les prédateurs d'évoluer qui pourrait se spécialiser en tant que prédateurs sur Magicicadas . Si Magicicadas apparu à un non-premiers intervalles de numéros, dire tous les 12 ans, puis tous les prédateurs apparaissent 2, 3, 4, 6, ou 12 ans serait sûr de les rencontrer. Sur une période de 200 ans, les populations de prédateurs moyenne pendant les flambées hypothétiques de 14 et 15 ans cigales seraient jusqu'à 2% de plus que pendant les épidémies de cigales de 13 et 17 ans. Bien que petit, cet avantage semble avoir été suffisant pour conduire la sélection naturelle en faveur d'un cycle de vie-prime-numérotée pour ces insectes.

Il ya des spéculations que les zéros de la fonction zêta sont reliés aux niveaux de systèmes quantiques complexes d'énergie.

Les nombres premiers dans les arts et la littérature

Les nombres premiers ont influencé de nombreux artistes et écrivains. Le Français compositeur Olivier Messiaen utilisé nombres premiers à créer de la musique grâce à ametrical "phénomènes naturels". Dans des œuvres comme La Nativité du Seigneur (1935) et Quatre études de rythme (1949-1950), il emploie simultanément motifs avec des longueurs données par différents nombres premiers pour créer des rythmes imprévisibles: les nombres premiers 41, 43, 47 et 53 apparaissent dans un des études. Selon Messiaen cette façon de composer a été "inspiré par les mouvements de la nature, les mouvements de durées libres et inégaux».

Dans son roman de science fiction contacter, plus tard transformé en unfilm du même nom, laNASAscientifiqueCarl Sagana suggéré que les nombres premiers pourraient être utilisés comme un moyen de communiquer avec des extraterrestres, une idée qu'il avait d'abord mis au point de façon informelle avec l'astronome américainFrank Drake en 1975.

Primé 1993 jeu de Tom Stoppard Arcadia était une tentative consciente de discuter des idées mathématiques sur la scène. Dans la scène d'ouverture, les 13 années vieilles énigmes de l'héroïne sur le dernier théorème de Fermat , impliquant un théorème des nombres premiers.

Beaucoup de films reflètent une fascination populaire avec les mystères de nombres premiers et la cryptographie: des films tels que Le Cube, Sneakers, The Mirror Has Two Faceset A Beautiful Mind, basé sur la biographie du mathématicien et lauréat du prix NobelJohn Forbes Nash parSylvia Nasar.