Eine Primzahl (oder eine Blüte) ist eine natürliche Zahl, die größer ist als 1, der keine positiven Teiler außer 1 und es hat. Eine natürliche Zahl, die größer ist als 1, der nicht eine Primzahl ist, wird eine zerlegbare Zahl genannt. Zum Beispiel, 5 ist erst, weil nur 1 und 5 es teilt, wohingegen 6 zerlegbar ist, da es die Teiler 2 und 3 zusätzlich zu 1 und 6 hat. Der Hauptsatz der Arithmetik gründet die Hauptrolle der Blüte in der Zahlentheorie: Jede ganze Zahl, die größer ist als 1, kann als ein Produkt der Blüte ausgedrückt werden, das bis zur Einrichtung einzigartig ist. Dieser Lehrsatz verlangt, 1 als eine Blüte ausschließend.

Das Eigentum, erst zu sein, wird primality genannt. Eine einfache, aber langsame Methode, den primality einer gegebenen Nummer n nachzuprüfen, ist als Probe-Abteilung bekannt. Es besteht aus der Prüfung, ob n ein Vielfache einer ganzer Zahl zwischen 2 ist und. Algorithmen, die viel effizienter sind als Probe-Abteilung, sind ausgedacht worden, um den primality der großen Anzahl zu prüfen. Besonders schnelle Methoden sind für die Blüte von speziellen Formen wie Blüte von Mersenne verfügbar., die größte bekannte Primzahl hat fast 13 Millionen dezimale Ziffern.

Es gibt ungeheuer viele Blüte, wie demonstriert, durch Euklid ungefähr 300 v. Chr. Es gibt keine bekannte nützliche Formel, die alle Primzahlen und keine Zusammensetzungen nachgibt. Jedoch kann der Vertrieb der Blüte, das heißt, das statistische Verhalten der Blüte im großen, modelliert werden. Die ersten laufen auf diese Richtung hinaus ist der Primzahl-Lehrsatz, der am Ende des 19. Jahrhunderts bewiesen ist, das sagt, dass die Wahrscheinlichkeit dass ein gegebener, zufällig gewählte Zahl erst ist, ist zu seiner Zahl von Ziffern oder dem Logarithmus von n umgekehrt proportional.

Viele Fragen um Primzahlen bleiben offen wie die Vermutung von Goldbach, die behauptet, dass jede gleiche ganze Zahl, die größer ist als 2, als die Summe von zwei Blüte und der Zwilling Hauptvermutung ausgedrückt werden kann, die sagt, dass es ungeheuer viele Paare der Blüte gibt, deren Unterschied 2 ist. Solche Fragen haben die Entwicklung von verschiedenen Zweigen der Zahlentheorie gespornt, sich auf analytische oder algebraische Aspekte von Zahlen konzentrierend. Blüte wird in mehreren Routinen in der Informationstechnologie wie Geheimschrift des öffentlichen Schlüssels verwendet, die von Eigenschaften wie die Schwierigkeit der großen Factoring-Anzahl in ihre Hauptfaktoren Gebrauch macht. Primzahlen verursachen verschiedene Generalisationen in anderen mathematischen Gebieten, hauptsächlich Algebra, wie Hauptelemente und Hauptideale.

Definition und Beispiele

Eine natürliche Zahl (d. h. 1, 2, 3, 4, 5, 6, usw.) wird eine Blüte oder eine Primzahl genannt, wenn es größer ist als 1 und genau zwei Teiler, 1 und die Zahl selbst hat. Natürliche Zahlen, die größer sind als 1, die nicht erst sind, werden zerlegbar genannt.

Unter den Nummern 1 bis 6 sind die Nummern 2, 3, und 5 die Primzahlen, während 1, 4, und 6 nicht erst sind. 1 wird als eine Primzahl aus Gründen ausgeschlossen, die unten erklärt sind. 2 ist eine Primzahl, da die einzigen natürlichen Zahlen, die sie teilen, 1 und 2 sind. Dann 3 ist auch erst: 1 und 3 teilen sich wirklich 3 ohne Rest, aber 3 geteilte durch 2 geben Rest 1. So, 3 ist erst. Jedoch, 4 ist zerlegbar, seitdem 2 ist eine andere Zahl (zusätzlich zu 1 und 4) das Teilen 4 ohne Rest:

:4 = 2 · 2.

5 ist wieder erst: Keine der Nummern 2, 3, oder 4 teilt sich 5. Dann 6 ist durch 2 oder 3, seitdem teilbar

:6 = 2 · 3.

Folglich, 6 ist nicht erst. Das Image am Recht illustriert, dass 12 nicht erst ist: 12 = 3 · 4. Im Allgemeinen ist keine gerade Zahl, die größer ist als 2, erst: Jede solche Zahl hat mindestens drei verschiedene Teiler, nämlich 1, 2, und. Das deutet an, dass das nicht erst ist. Entsprechend bezieht sich der Begriff sonderbare Blüte auf jede Primzahl, die größer ist als 2. In einer ähnlichen Ader, alle Primzahlen, die größer sind als 5, geschrieben im üblichen dezimalen System, Ende in 1, 3, 7, oder 9, da sind gerade Zahlen Vielfachen 2, und Zahlen, die in 0 oder 5 enden, sind Vielfachen 5.

Wenn eine natürliche Zahl ist, dann 1 und teilen sich ohne Rest. Deshalb kann die Bedingung, eine Blüte zu sein, auch als neu formuliert werden: Eine Zahl ist erst, wenn es größer ist als eines und wenn keiner von

:

teilt sich (ohne Rest). Und doch ist eine andere Weise, dasselbe zu sagen: Eine Zahl ist erst, wenn sie als ein Produkt von zwei ganzen Zahlen nicht geschrieben werden kann und, von denen beide größer sind als 1:

:.

Mit anderen Worten, ist erst, wenn Sachen in kleinere Gruppen der gleichen Größe von mehr als einem Artikel nicht zerteilt werden können.

Die kleinsten 168 Primzahlen (alle Primzahlen unter 1000) sind:

: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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.

Der Satz der ganzen Blüte wird häufig angezeigt.

Hauptsatz der Arithmetik

Die entscheidende Wichtigkeit von Primzahlen zur Zahlentheorie und Mathematik in allgemeinen Stämmen vom Hauptsatz der Arithmetik, die feststellt, dass jede positive ganze Zahl, die größer ist als 1, als ein Produkt von einer oder mehr Blüte in einem Weg geschrieben werden kann, der abgesehen von der Ordnung der Hauptfaktoren einzigartig ist. Blüte kann so als die "grundlegenden Bausteine" der natürlichen Zahlen betrachtet werden. Zum Beispiel:

:

Als in diesem Beispiel kann derselbe Hauptfaktor mehrmals vorkommen. Eine Zergliederung:

:

einer Zahl in (begrenzt viele) Hauptfaktoren... dazu wird ersten factorization dessen genannt. Der Hauptsatz der Arithmetik kann umformuliert werden, um zu sagen, dass jeder factorization in die Blüte abgesehen von der Ordnung der Faktoren identisch sein wird. Also, obgleich es viele factorization Hauptalgorithmen gibt, um das in der Praxis für größere Zahlen zu tun, müssen sie alle dasselbe Ergebnis nachgeben.

Wenn eine Primzahl ist und ein Produkt von ganzen Zahlen teilt, sich dann teilt oder sich teilt. Dieser Vorschlag ist als das Lemma von Euklid bekannt. Es wird in einigen Beweisen der Einzigartigkeit von erstem factorizations verwendet.

Primality von einem

Frühste Griechen haben 1 nicht sogar gedacht, eine Zahl zu sein, so hat es als eine Blüte nicht betrachtet. Im 19. Jahrhundert jedoch haben viele Mathematiker wirklich die Nummer 1 als eine Blüte betrachtet. Zum Beispiel die Liste von Derrick Norman Lehmer der Blüte haben bis zu 10,006,721, nachgedruckt erst 1956, mit 1 als seine erste Blüte angefangen. Wie man sagt, ist Henri Lebesgue der letzte Berufsmathematiker, um 1 ersten zu nennen. Obwohl ein großer Körper der mathematischen Arbeit auch gültig ist, wenn er 1 eine Blüte ruft, hält der obengenannte Hauptsatz der Arithmetik, wie festgesetzt, nicht. Zum Beispiel kann die Nummer 15 factored als sein oder. Wenn 1 als eine Blüte zugelassen würden, würden diese zwei Präsentationen als verschiedener factorizations 15 in Primzahlen betrachtet, so würde die Behauptung dieses Lehrsatzes modifiziert werden müssen. Außerdem haben die Primzahlen mehrere Eigenschaften, an denen die Nummer 1, wie die Beziehung der Zahl zu seinem entsprechenden Wert der Totient-Funktion von Euler oder der Summe der Teiler-Funktion Mangel hat.

Geschichte

Es gibt Hinweise in den überlebenden Aufzeichnungen der alten Ägypter, dass sie einige Kenntnisse von Primzahlen hatten: Die ägyptischen Bruchteil-Vergrößerungen im Papyrus von Rhind haben zum Beispiel ziemlich verschiedene Formen für die Blüte und für Zusammensetzungen. Jedoch kommen die frühsten überlebenden Aufzeichnungen der ausführlichen Studie von Primzahlen aus den Alten Griechen. Die Elemente von Euklid (um 300 v. Chr.) enthalten wichtige Lehrsätze über die Blüte, einschließlich der Unendlichkeit der Blüte und des Hauptsatzes der Arithmetik. Euklid hat auch gezeigt, wie man eine vollkommene Zahl von erstem Mersenne baut. Das Sieb von Eratosthenes, der Eratosthenes zugeschrieben ist, ist eine einfache Methode, Blüte zu schätzen, obwohl die große Blüte gefunden heute mit Computern dieser Weg nicht erzeugt wird.

Nach den Griechen, die wenig mit der Studie von Primzahlen bis zum 17. Jahrhundert zufällig sind. 1640 hat Pierre de Fermat (ohne Beweis) den kleinen Lehrsatz von Fermat (später bewiesen von Leibniz und Euler) festgesetzt. Ein spezieller Fall des Lehrsatzes von Fermat kann viel früher von den Chinesen bekannt gewesen sein. Fermat hat vermutet, dass alle Zahlen der Form 2 + 1 erst sind (sie werden Zahlen von Fermat genannt), und er hat das bis zu n = 4 (oder 2 + 1) nachgeprüft. Jedoch ist der sehr folgende Fermat Nummer 2 + 1 zerlegbar (einer seiner Hauptfaktoren ist 641), weil Euler später entdeckt hat, und tatsächlich, wie man bekannt, keine weiteren Zahlen von Fermat erst sind. Der französische Mönch Marin Mersenne hat auf die Blüte der Form 2  1, mit p eine Blüte geschaut. Sie werden Blüte von Mersenne in seiner Ehre genannt.

Die Arbeit von Euler in der Zahlentheorie hat viele Ergebnisse über die Blüte eingeschlossen. Er hat gezeigt, dass die unendliche Reihe auseinander gehend ist.

1747 hat er gezeigt, dass die gleichen vollkommenen Zahlen genau die ganzen Zahlen der Form 2 sind (2  1), wo der zweite Faktor erster Mersenne ist.

Am Anfang des 19. Jahrhunderts haben Legendre und Gauss unabhängig vermutet, dass weil x zur Unendlichkeit neigt, ist die Zahl der Blüte bis zu x zu x/ln (x) asymptotisch, wo ln (x) der natürliche Logarithmus von x ist. Ideen von Riemann in seiner 1859-Zeitung auf der Zeta-Funktion haben ein Programm skizziert, das zu einem Beweis des Primzahl-Lehrsatzes führen würde. Dieser Umriss wurde von Hadamard und de la Vallée Poussin vollendet, der unabhängig den Primzahl-Lehrsatz 1896 bewiesen hat.

Beweis einer Zahl ist erst wird (für die große Anzahl) von der Probe-Abteilung nicht getan. Viele Mathematiker haben an Primality-Tests auf die große Anzahl gearbeitet, die häufig auf spezifische Zahl-Formen eingeschränkt ist. Das schließt den Test von Pépin auf Zahlen von Fermat (1877), der Lehrsatz von Proth (1878), der Lucas-Lehmer primality Test (hervorgebrachter 1856), und der verallgemeinerte Lucas primality Test ein. Neuere Algorithmen wie APRT-KL-., ECPP und AKS arbeiten an beliebigen Zahlen, aber bleiben viel langsamer.

Seit langem, wie man dachte, hatten Primzahlen Anwendung außerhalb der reinen Mathematik äußerst beschränkt; das hat sich in den 1970er Jahren geändert, als die Konzepte der Geheimschrift des öffentlichen Schlüssels erfunden wurden, in dem Primzahlen die Basis der ersten Algorithmen wie der RSA cryptosystem Algorithmus gebildet haben.

Seit 1951 ist die ganze größte bekannte Blüte durch Computer gefunden worden. Die Suche auf immer größere Blüte hat Interesse außerhalb mathematischer Kreise erzeugt. Hauptsuche des Mersenne des Großen Internets und andere verteilte Rechenprojekte, große Blüte zu finden, sind populär in den letzten zehn bis fünfzehn Jahren geworden, während Mathematiker fortsetzen, mit der Theorie der Blüte zu kämpfen.

Zahl von Primzahlen

Es gibt ungeheuer viele Primzahlen. Eine andere Weise, das zu sagen, besteht dass die Folge darin

:2, 3, 5, 7, 11, 13...

Primzahlen endet nie. Diese Behauptung wird den Lehrsatz von Euklid zu Ehren vom alten griechischen Mathematiker Euklid genannt, da der erste bekannte Beweis für diese Behauptung ihm zugeschrieben wird. Noch viele Beweise der Unendlichkeit der Blüte, sind einschließlich eines analytischen Beweises von Euler, der Beweis von Goldbach bekannt, der auf Zahlen von Fermat, der Beweis von Fürstenberg mit der allgemeinen Topologie und dem eleganten Beweis von Kummer gestützt ist.

Der Beweis von Euklid

Der Beweis von Euklid (Buch IX, Vorschlag 20) beginnt mit der Definition der Blüte und denkt dann jeden begrenzten Satz der Blüte, die wir p, p bis zu p anzeigen. Die Schlüsselidee ist, das Produkt aller dieser Zahlen plus eine zu denken (diese Zahl wird eine Zahl von Euklid genannt):

:P = p · p ·... · p + 1.

Wie jede natürliche Zahl kann P als ein Produkt von Primzahlen geschrieben werden; das wird durch den Hauptsatz der Arithmetik gesichert:

:P = q · q ·... · q

(es ist möglich, dass P selbst, in welchem Fall M = 1 erst ist).

Keine der Blüte p, p, usw., zu p kann P, weil teilen, sich P durch einige dieser Blätter ein Rest 1 teilend. Deshalb ist die Blüte q, q..., q zusätzliche Blüte außer denjenigen wir haben damit angefangen. So kann jeder begrenzte Satz der Blüte zu einem größeren begrenzten Satz der Blüte erweitert werden.

Der Euklid Nummer P, braucht zum Beispiel nicht erst

zu sein

:2 · 3 · 5 · 7 · 11 · 13 + 1 = 30,031 = 59 · 509 (beide Blüte).

Es wird häufig falsch berichtet, dass Euklid die Unendlichkeit der Blüte durch den Widerspruch bewiesen hat, beginnend in der Annahme, dass der am Anfang betrachtete Satz alle Primzahlen enthält, oder dass es genau die n kleinste Blüte, aber nicht jeden willkürlichen begrenzten Satz der Blüte enthält.

Der analytische Beweis von Euler

Der Beweis von Euler verwendet die Summe der Gegenstücke der Blüte,

:

Diese Summe wird größer als jede willkürliche reelle Zahl vorausgesetzt, dass p groß genug ist. Das zeigt, dass es ungeheuer viele Blüte gibt, da sonst diese Summe nur wachsen würde, bis der größte erste p erreicht wird. Das Wachstum von S (p) wird durch den zweiten Lehrsatz von Mertens gemessen. Zum Vergleich, die Summen

:

wachsen Sie zur Unendlichkeit nicht, wenn n wächst. In diesem Sinn kommen Primzahlen öfter vor als Quadrate von natürlichen Zahlen. Der Lehrsatz von Brun stellt dass die Summe der Gegenstücke der Zwillingsblüte, fest

:ist

begrenzt.

Die Prüfung primality und ganze Zahl factorization

Es gibt verschiedene Methoden zu bestimmen, ob eine gegebene Nummer n erst ist. Die grundlegendste Routine, Probe-Abteilung ist von wenig praktischem Nutzen wegen seiner Langsamkeit. Eine Gruppe von modernen Primality-Tests ist auf beliebige Zahlen anwendbar, während effizientere Tests für besondere Zahlen verfügbar sind. Die meisten solche Methoden erzählen nur, ob n erst ist oder nicht. Routinen, die auch eine (oder alle) Hauptfaktoren von n nachgeben, werden factorization Algorithmen genannt.

Probe-Abteilung

Die grundlegendste Methode, den primality einer gegebenen ganzen Zahl n zu überprüfen, wird Probe-Abteilung genannt. Diese Routine besteht daraus, n durch jede ganze Zahl M zu teilen, die größer als 1 und weniger als oder der Quadratwurzel von n gleich ist. Wenn das Ergebnis von einigen dieser Abteilungen eine ganze Zahl ist, dann ist n nicht eine Blüte, sonst ist es eine Blüte. Tatsächlich, wenn (mit a und b  1) dann zerlegbar ist, ist einer der Faktoren a oder b notwendigerweise am grössten Teil von . Zum Beispiel, weil die Probe-Abteilungen durch Keine dieser Zahlen sind, teilt sich 37, so 37 ist erst. Diese Routine kann effizienter durchgeführt werden, wenn eine ganze Liste der Blüte bis zu  — dann bekannt ist, müssen Probe-Abteilungen nur für diejenigen M überprüft werden, die erst sind. Zum Beispiel, um den primality 37 zu überprüfen, sind nur drei Abteilungen notwendig (M = 2, 3, und 5), vorausgesetzt, dass 4 und 6 zerlegbar sind.

Während eine einfache Methode, Probe-Abteilung schnell unpraktisch wird, um große ganze Zahlen zu prüfen, weil die Zahl von möglichen Faktoren zu schnell als n Zunahmen wächst. Gemäß dem Primzahl-Lehrsatz, der unten erklärt ist, wird durch die Zahl von Primzahlen weniger als  ungefähr gegeben, so muss der Algorithmus eventuell bis zu dieser Zahl von Probe-Abteilungen den primality von n überprüfen. Da diese Zahl 450 Millionen — zu groß für viele praktische Anwendungen ist.

Siebe

Ein Algorithmus, der die ganze Blüte bis zu einer vorgeschriebenen Grenze, solcher, wie erforderlich, in der Probe-Abteilungsmethode nachgibt, wird ein Sieb genannt. Das älteste Beispiel, das Sieb von Eratosthenes (sieh oben), sind für die relativ kleine Blüte nützlich. Das moderne Sieb von Atkin, ist aber schneller wenn richtig optimiert, mehr kompliziert. Vor dem Advent von Computern wurden Listen der Blüte bis zu Grenzen wie 10 auch verwendet.

Prüfung von Primality gegen den Primality-Beweis

Moderne Primality-Tests auf allgemeine Zahlen n können in zwei Hauptklassen, probabilistic (oder "Monte Carlo") und deterministische Algorithmen geteilt werden. Der erstere "prüft" bloß, ob n im Sinn erst ist, dass sie n erklären (bestimmt) zerlegbar oder wahrscheinlich", das letzte Meinen "erst zu sein, dass n kann oder keine Primzahl sein kann. Zerlegbare Zahlen, die wirklich einen gegebenen Primality-Test bestehen, werden Pseudoblüte genannt. Zum Beispiel verlässt sich der Primality-Test von Fermat auf den kleinen Lehrsatz von Fermat. Dieser Lehrsatz sagt, dass für jede Primzahl p und jede ganze Zahl nicht teilbar durch p, durch p teilbar ist. So, wenn durch n nicht teilbar ist, kann n nicht erst sein. Jedoch kann n zerlegbar sein, selbst wenn diese Teilbarkeit hält. Tatsächlich gibt es ungeheuer viele zerlegbare Zahlen n, die den Test von Fermat primality für jede Wahl bestehen, der coprime mit n (Zahlen von Carmichael) zum Beispiel ist.

Deterministische Algorithmen melden zerlegbare Zahlen als erst nicht falsch. In der Praxis ist das schnellste solche Methode als elliptische Kurve primality Beweis bekannt. Das Analysieren seiner Durchlaufzeit basiert auf heuristischen Argumenten, im Vergleich mit der streng bewiesenen Kompliziertheit des neueren AKS primality Test. Deterministische Methoden sind normalerweise langsamer als probabilistic, so werden die letzten normalerweise zuerst angewandt, bevor eine zeitraubendere deterministische Routine verwendet wird.

Der folgende Tisch verzeichnet mehrere Haupttests. Die Laufzeit wird in Bezug auf n, die Zahl gegeben, die zu prüfen ist und, für probabilistic Algorithmen, die Nummer k von durchgeführten Tests. Außerdem ist ε eine willkürlich kleine positive Zahl, und Klotz ist der Logarithmus zu einer unangegebenen Basis. Die große O Notation bedeutet, dass, zum Beispiel, elliptische Kurve primality Beweis eine Zeit verlangt, die durch einen Faktor (nicht je nachdem n, aber auf ε) Zeitklotz (n) begrenzt wird.

Algorithmen des speziellen Zwecks und die größte bekannte Blüte

Zusätzlich zu den oben erwähnten Tests, die für jede natürliche Zahl n gelten, prüfen mehrere viel effizientere primality ist für spezielle Zahlen verfügbar. Zum Beispiel, den primality Test von Lucas durchzuführen, verlangt die Kenntnisse der Hauptfaktoren dessen, während der Lucas-Lehmer primality Test die Hauptfaktoren, wie eingegeben, braucht. Zum Beispiel können diese Tests auf die Kontrolle ob angewandt werden

:n! ± 1 = 1 · 2 · 3 ·... · n ± 1

sind

erst. Primzahlen dieser Form sind als factorial Blüte bekannt. Andere Blüte, wo entweder p + 1 oder p  1 einer besonderen Gestalt sind, schließt die Blüte von Sophie Germain ein (Blüte der Form 2 Punkte + 1 mit der p Blüte), primorial Blüte, Blüte von Fermat und Blüte von Mersenne, d. h. Primzahlen, die der Form sind, wo p eine willkürliche Blüte ist. Der Test von Lucas-Lehmer ist für Zahlen dieser Form besonders schnell. Das ist, warum die größte bekannte Blüte fast immer seit der Morgendämmerung von elektronischen Computern erster Mersenne gewesen ist.

Blüte von Fermat ist von der Form, mit k eine willkürliche natürliche Zahl. Sie werden nach Pierre de Fermat genannt, der vermutet hat, dass alle diese Zahlen F erst sind. Das hat auf den Beweisen der ersten fünf Zahlen in dieser Reihe — 3, 5, 17, 257, und 65,537 basiert — erst zu sein. Jedoch ist F zerlegbar und ist auch alle anderen Zahlen von Fermat, die bezüglich 2011 nachgeprüft worden sind. Ein regelmäßiger n-gon ist constructible das Verwenden des Haarlineals und Kompasses wenn und nur wenn

:n = 2 · M

wo M ein Produkt jeder Zahl der verschiedenen Blüte von Fermat ist und ich jede natürliche Zahl einschließlich der Null bin.

Der folgende Tisch gibt die größte bekannte Blüte der erwähnten Typen. Etwas von dieser Blüte ist mit der verteilten Computerwissenschaft gefunden worden. 2009 wurde das Große Internet Mersenne Hauptsuchprojekt einem Preis von 100,000 US$ für das erste Entdecken einer Blüte mit mindestens 10 Millionen Ziffern zuerkannt. Das Elektronische Grenzfundament bietet auch 150,000 $ und 250,000 $ für die Blüte mit mindestens 100 Millionen Ziffern und 1 Milliarde Ziffern beziehungsweise an. Etwas von der größten Blüte, die nicht bekannt ist, jede besondere Form (d. h. keine einfache Formel wie die der Blüte von Mersenne) zu haben, ist durch die Einnahme eines Stückes von halbzufälligen binären Daten, das Umwandeln davon zu einer Zahl, das Multiplizieren davon durch 256 für eine positive ganze Zahl und das Suchen nach möglicher Blüte innerhalb des Zwischenraums [256n + 1, 256 (n + 1)  1] gefunden worden.

Ganze Zahl factorization

In Anbetracht einer zerlegbaren ganzen Zahl n wird die Aufgabe, eine (oder alle) Hauptfaktoren zur Verfügung zu stellen, factorization von n genannt. Elliptische Kurve factorization ist ein Algorithmus, der sich auf die Arithmetik auf einer elliptischen Kurve verlässt.

Vertrieb

1975 hat Zahl-Theoretiker Don Zagier das Blüte beide kommentiert

Der Vertrieb der Blüte im großen, wie die Frage, wie viele Blüte kleiner ist als eine gegebene, große Schwelle, wird durch den Primzahl-Lehrsatz beschrieben, aber keine effiziente Formel für die n-te Blüte ist bekannt.

Es gibt willkürlich lange Folgen der Konsekutivnichtblüte bezüglich jeder positiven ganzen Zahl die aufeinander folgenden ganzen Zahlen von zu (einschließlichem) sind die ganze Zusammensetzung (wie durch für zwischen und teilbar ist).

Der Lehrsatz von Dirichlet auf arithmetischen Fortschritten, in seiner grundlegenden Form, behauptet dass geradlinige Polynome

:

mit coprime ganzen Zahlen nehmen a und b ungeheuer viele Hauptwerte. Stärkere Formen des Lehrsatzes stellen fest, dass die Summe der Gegenstücke dieser Hauptwerte abweicht, und dass verschieden solche Polynome mit demselben b ungefähr dieselben Verhältnisse der Blüte haben.

Die entsprechende Frage für quadratische Polynome wird weniger gut verstanden.

Formeln für die Blüte

Es gibt keine bekannte effiziente Formel für die Blüte. Zum Beispiel behaupten der Lehrsatz von Mühlen und ein Lehrsatz von Wright, dass es echte Konstanten A> 1 und solcher μ dass gibt

:sind

für jede natürliche Zahl n erst. Hier vertritt die Fußboden-Funktion, d. h., größte ganze Zahl, die nicht größer ist als die fragliche Zahl. Die letzte Formel kann mit dem Postulat von Bertrand gezeigt werden (bewiesen zuerst von Tschebyscheff), der feststellt, dass dort immer mindestens eine Primzahl p mit n besteht

Es gibt kein nichtunveränderliches Polynom sogar in mehreren Variablen, der nur Hauptwerte nimmt. Jedoch gibt es eine Reihe von Gleichungen von Diophantine in 9 Variablen und einem Parameter mit dem folgenden Eigentum: Der Parameter ist erst, wenn, und nur wenn das resultierende Gleichungssystem eine Lösung über die natürlichen Zahlen hat. Das kann verwendet werden, um eine einzelne Formel mit dem Eigentum zu erhalten, dass alle seine positiven Werte erst sind.

Zahl von Primzahlen unter einer gegebenen Zahl

Die zählende Hauptfunktion π (n) wird als die Zahl der Blüte bis zu n definiert. Zum Beispiel π (11) = 5 da gibt es fünf Blüte weniger als oder gleich 11. Es gibt bekannte Algorithmen, um genaue Werte von π (n) schneller zu schätzen, als es möglich sein würde, jede Blüte bis zu n zu schätzen. Der Primzahl-Lehrsatz stellt fest, dass π (n) durch ungefähr gegeben wird

:

im Sinn, dass sich das Verhältnis von π (n) und der Bruchteil der rechten Hand 1 nähert, wenn n zur Unendlichkeit wächst. Das deutet an, dass die Wahrscheinlichkeit, dass eine Zahl weniger als n erst ist, zur Zahl von Ziffern in n (ungefähr) umgekehrt proportional ist. Eine genauere Schätzung für π (n) wird durch den Ausgleich logarithmischer integrierter gegeben

:

Der Primzahl-Lehrsatz bezieht auch Schätzungen für die Größe der n-ten Primzahl p (d. h., p = 2, p = 3, usw.) ein: Bis zu einem begrenzten Faktor wächst p wie. Insbesondere die Hauptlücken, d. h. die Unterschiede von zwei Konsekutivblüte, werden willkürlich groß. Diese letzte Behauptung kann auch auf eine elementarere Weise durch die Anmerkung dass die Folge gesehen werden (für die Notation n! lesen Sie factorial) besteht aus zerlegbaren Zahlen, für jede natürliche Zahl n.

Arithmetische Fortschritte

Ein arithmetischer Fortschritt ist der Satz von natürlichen Zahlen, die denselben Rest, wenn geteilt, durch eine festgelegte Zahl q genannt Modul geben. Zum Beispiel,

:3, 12, 21, 30, 39...,

ist ein arithmetischer Fortschritt modulo. Abgesehen von 3 ist keine dieser Zahlen seitdem erst, so dass die restlichen Zahlen in diesem Fortschritt die ganze Zusammensetzung sind. (Allgemein sind alle Primzahlen über q der Form q#·n + M, wo 0

Ein sonderbarer erster p ist expressible als die Summe von zwei Quadraten genau, wenn p 1 modulo 4 (der Lehrsatz von Fermat auf Summen von zwei Quadraten) kongruent ist.

Hauptwerte quadratischer Polynome

Euler hat dass die Funktion bemerkt

:

gibt Primzahlen dafür