Primzahl

Eine Primzahl (oder kurz Primzahl ) ist eine natürliche Zahl größer als 1, die nicht das Produkt zweier kleinerer natürlicher Zahlen ist. Eine natürliche Zahl größer als 1, die keine Primzahl ist, wird als zusammengesetzte Zahl bezeichnet . Beispielsweise ist 5 eine Primzahl, da sie sich nur als Produkt darstellen lässt ( 1 × 5 oder 5 × 1) , wobei 5 selbst enthalten ist. 4 hingegen ist eine zusammengesetzte Zahl, da sie ein Produkt (2 × 2) ist, in dem beide Zahlen kleiner als 4 sind. Primzahlen sind in der Zahlentheorie von zentraler Bedeutung , da der Fundamentalsatz der Arithmetik besagt : Jede natürliche Zahl größer als 1 ist entweder selbst eine Primzahl oder lässt sich als Produkt von Primzahlen faktorisieren , wobei die Faktorisierung bis auf die Primzahlordnung eindeutig ist.

Die Eigenschaft, eine Primzahl zu sein, wird als Primzahleigenschaft bezeichnet . Eine einfache, aber langsame Methode zur Überprüfung der Primzahleigenschaft einer gegebenen Zahl, die sogenannte Probedivision, prüft, ob die Zahl ein Vielfaches einer ganzen Zahl zwischen 2 und 1/2 ist . Schnellere Algorithmen sind der${\displaystyle n}$ Miller - Rabin - Primzahltest${\displaystyle n}$ , der${\displaystyle {\sqrt {n}}}$ zwar schnell ist, aber eine geringe Fehlerwahrscheinlichkeit aufweist, und der AKS-Primzahltest , der in Polynomialzeit immer das richtige Ergebnis liefert , aber für die Praxis zu langsam ist. Besonders schnelle Methoden existieren für Zahlen spezieller Formen, wie beispielsweise Mersenne-Zahlen , und diese wurden zur Bestimmung großer Primzahlen verwendet .

Es gibt unendlich viele Primzahlen, wie Euklid um 300 v. Chr. bewies . Es gibt keine bekannte einfache Formel, die Primzahlen von zusammengesetzten Zahlen trennt. Die Verteilung der Primzahlen innerhalb der natürlichen Zahlen im Großen lässt sich jedoch statistisch modellieren. Der erste Beweis in diese Richtung ist der Primzahlsatz , der Ende des 19. Jahrhunderts bewiesen wurde. Er besagt grob gesagt, dass die Wahrscheinlichkeit , dass eine zufällig gewählte große Zahl eine Primzahl ist, umgekehrt proportional zu ihrer Ziffernzahl, also zu ihrem Logarithmus , ist .

Einige historische Fragen zu Primzahlen sind noch immer ungelöst. Dazu gehören die Goldbachsche Vermutung , dass jede gerade Zahl größer als 2 als Summe zweier Primzahlen dargestellt werden kann, und die Zwillingsprimzahlvermutung , dass es unendlich viele Paare von Primzahlen gibt, die sich um zwei unterscheiden. Solche Fragen beflügelten die Entwicklung verschiedener Zweige der Zahlentheorie, die sich mit analytischen oder algebraischen Aspekten von Zahlen befassen. Primzahlen werden in verschiedenen Verfahren der Informationstechnologie verwendet , beispielsweise in der Public-Key-Kryptographie , die auf der Schwierigkeit beruht, große Zahlen in ihre Primfaktoren zu zerlegen . In der abstrakten Algebra gibt es Objekte wie Primelemente und Primideale , die sich verallgemeinert wie Primzahlen verhalten .

Eine natürliche Zahl (1, 2, 3, 4, 5, 6 usw.) heißt Primzahl , wenn sie größer als 1 ist und nicht als Produkt zweier kleinerer natürlicher Zahlen dargestellt werden kann. Zahlen größer als 1, die keine Primzahlen sind, heißen zusammengesetzte Zahlen . ^{[ 1 ]} Anders ausgedrückt: Eine Zahl ist eine Primzahl, wenn sie nicht in kleinere , gleich große Gruppen von mehr als einer Zahl unterteilt werden kann ^{[ 2 ]} oder wenn es nicht möglich ist, Punkte in einem Rechteck anzuordnen , das breiter und höher als ein Punkt ist. ^{[ 3 ]} Beispielsweise sind unter den Zahlen 1 bis 6 die Zahlen 2, 3 und 5 Primzahlen, ^{[ 4 ]} da es keine anderen Zahlen gibt, die sie ohne Rest teilen. Die Zahl 1 ist keine Primzahl, da sie in der Definition ausdrücklich ausgeschlossen ist. 4 = 2 × 2 und 6 = 2 × 3 sind beides zusammengesetzte Zahlen. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

Die Teiler einer natürlichen Zahl sind die${\displaystyle n}$ natürlichen Zahlen, die diese Zahl${\displaystyle n}$ ohne Rest teilen. Jede natürliche Zahl hat sowohl 1 als auch sich selbst als Teiler. Hat sie einen anderen Teiler, kann sie keine Primzahl sein. Daraus ergibt sich eine äquivalente Definition von Primzahlen: Sie sind die Zahlen mit genau zwei positiven Teilern . Diese beiden sind 1 und die Zahl selbst. Da 1 nur einen Teiler hat, nämlich sich selbst, ist sie nach dieser Definition keine Primzahl. ^{[ 5 ]} Eine andere Möglichkeit, dasselbe auszudrücken, ist, dass eine Zahl prim ist${\displaystyle n}$ , wenn sie größer als 1 ist und keine ihrer natürlichen Teiler sie ohne Rest teilt . ^{[ 6 ]}${\displaystyle 2,3,\dots ,n-1}$${\displaystyle n}$

Die ersten 25 Primzahlen (alle Primzahlen kleiner als 100) sind: ^{[ 7 ]}

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 (Sequenz A000040 in der OEIS ).

Keine gerade Zahl größer als 2 ist eine Primzahl , da sich jede solche Zahl als Produkt darstellen lässt . Daher ist jede Primzahl außer 2 eine ungerade Zahl und wird als ungerade Primzahl bezeichnet . ^{[ 8 ]} Analog dazu enden im üblichen Dezimalsystem alle Primzahlen größer als 5 auf 1, 3, 7 oder 9. Die Zahlen, die auf andere Ziffern enden, sind zusammengesetzt: Dezimalzahlen, die auf 0, 2, 4, 6 oder 8 enden, sind gerade, und Dezimalzahlen, die auf 0 oder 5 enden, sind durch 5 teilbar. ^{[ 9 ]}${\displaystyle n}$${\displaystyle 2\times n/2}$

Die Menge aller Primzahlen wird manchmal mit (einem fettgedruckten Großbuchstaben P) ^{[ 10 ]} oder mit (einem fettgedruckten Großbuchstaben P auf der Tafel) ^{[ 11 ] bezeichnet.}${\displaystyle \mathbf {P} }$${\displaystyle \mathbb {P} }$

Ab etwa 1550 v. Chr. enthält der Rhind-Papyrus (Mathematisches Buch) ägyptische Bruchdarstellungen verschiedener Formen für Brüche mit Prim- und zusammengesetzten Nennern. ^{[ a ] [ 12 ]} Die frühesten erhaltenen Aufzeichnungen zur Erforschung von Primzahlen stammen jedoch von den antiken griechischen Mathematikern , die sie „prōtos arithmòs“ ( πρῶτος ἀριθμὸς ) nannten . Euklids „ Elemente “ (um 300 v. Chr.) beweisen die Unendlichkeit der Primzahlen und den Fundamentalsatz der Arithmetik und zeigen, wie man aus einer Mersenne-Primzahl eine vollkommene Zahl konstruiert . ^{[ 13 ]} Eine weitere griechische Erfindung, das Sieb des Eratosthenes , wird noch heute zur Erstellung von Primzahllisten verwendet . ^{[ 14 ] [ 15 ]}

Um 1000 n. Chr. fand der islamische Mathematiker Ibn al-Haytham (Alhazen) den Satz von Wilson , der die Primzahlen als diejenigen Zahlen charakterisiert, die n ${\displaystyle n}$ohne${\displaystyle (n-1)!+1}$ Rest teilen . Er vermutete außerdem, dass alle geraden vollkommenen Zahlen auf Euklids Konstruktion mit Mersenne-Primzahlen beruhen, konnte dies aber nicht beweisen. ^{[ 16 ]} Ein anderer islamischer Mathematiker, Ibn al-Banna' al-Marrakushi , bemerkte, dass sich das Sieb des Eratosthenes beschleunigen lässt, indem man nur die Primteiler bis zur Quadratwurzel der oberen Grenze betrachtet. ^{[ 15 ]} Fibonacci brachte die Innovationen der islamischen Mathematik nach Europa. Sein Buch Liber Abaci (1202) beschrieb als erstes die Probedivision zum Nachweis von Primzahlen, wobei er wiederum nur Teiler bis zur Quadratwurzel verwendete. ^{[ 15 ]}

1640 formulierte Pierre de Fermat (ohne Beweis) den kleinen Fermatschen Satz (später von Leibniz und Euler bewiesen ). ^{[ 17 ]} Fermat untersuchte auch die Primzahleigenschaft der Fermat-Zahlen [ 18 ${\displaystyle 2^{2^{n}}+1}$^] , und Marin Mersenne befasste sich mit den Mersenne-Primzahlen, Primzahlen der Form 1/2, wobei 1 ^selbst eine Primzahl ^ist . ^{[ 19 ]} Christian Goldbach formulierte 1742 in einem Brief an Euler die Goldbachsche Vermutung , dass jede gerade Zahl die Summe zweier Primzahlen ist. ^{[ 20 ]} Euler bewies die Alhazensche Vermutung (heute der Satz von Euklid-Euler ), dass alle geraden vollkommenen Zahlen aus Mersenne-Primzahlen konstruiert werden können. ^{[ 13 ]} In seinen Beweisen für die Unendlichkeit der Primzahlen und die Divergenz der Summe der Kehrwerte der Primzahlen führte er Methoden der mathematischen Analysis auf dieses Gebiet ein . ^{[ 21 ]} Zu Beginn des 19. Jahrhunderts vermuteten Legendre und Gauß, dass die Anzahl der Primzahlen bis zu für gegen unendlich asymptotisch gegen konvergiert , wobei der natürliche Logarithmus von ist . Eine schwächere Konsequenz dieser hohen Primzahldichte war Bertrands Postulat , dass es zu jedem eine Primzahl zwischen und gibt , das 1852 von Pafnuty Tschebyscheff bewiesen wurde . ^{[ 22 ]} Bernhard Riemanns Ideen in seiner 1859 erschienenen Arbeit über die Zetafunktion skizzierten einen Beweisansatz für die Vermutung von Legendre und Gauß. Obwohl die eng verwandte Riemannsche Vermutung bis heute unbewiesen ist, wurde Riemanns Ansatz 1896 von Hadamard und de la Vallée Poussin vervollständigt , und das Ergebnis ist heute als Primzahlsatz bekannt . ^{[ 23 ]} Ein weiteres wichtiges Ergebnis des 19. Jahrhunderts war der Satz von Dirichlet über arithmetische Folgen , der besagt, dass bestimmte arithmetische Folgen unendlich viele Primzahlen enthalten. ^{[ 24 ]}${\displaystyle 2^{p}-1}$${\displaystyle p}$${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$${\displaystyle x}$${\displaystyle x}$${\displaystyle x/\log x}$${\displaystyle \log x}$${\displaystyle x}$${\displaystyle n>1}$${\displaystyle n}$${\displaystyle 2n}$^]

Viele Mathematiker haben Primzahltests für Zahlen entwickelt , die größer sind als jene, bei denen die Probedivision praktisch anwendbar ist. Zu den Methoden, die auf bestimmte Zahlenformen beschränkt sind, gehören Pépins Test für Fermat-Zahlen (1877), ^{[ 25 ]} der Satz von Proth (ca. 1878), ^{[ 26 ]} der Lucas-Lehmer-Primzahltest (ursprünglich 1856 entwickelt) und der verallgemeinerte Lucas-Primzahltest . ^{[ 15 ]}

Seit 1951 wurden alle größten bekannten Primzahlen mithilfe dieser Tests auf Computern gefunden . ^{[ b ]} Die Suche nach immer größeren Primzahlen hat durch die Great Internet Mersenne Prime Search und andere verteilte Rechenprojekte auch außerhalb mathematischer Kreise Interesse geweckt. ^{[ 7 ] [ 28 ]} Die Vorstellung, dass Primzahlen außerhalb der reinen Mathematik kaum Anwendung finden, ^{[ c ]} wurde in den 1970er Jahren durch die Erfindung der Public-Key-Kryptographie und des RSA- Kryptosystems, die auf Primzahlen basieren, widerlegt. ^{[ 31 ]}

Die zunehmende praktische Bedeutung computergestützter Primzahltests und Faktorisierung führte zur Entwicklung verbesserter Methoden, die große Zahlen unbeschränkter Form verarbeiten können. ^{[ 14 ] [ 32 ] [ 33 ]} Auch die mathematische Theorie der Primzahlen entwickelte sich weiter, beispielsweise mit dem Satz von Green-Tao (2004), der die Existenz beliebig langer arithmetischer Folgen von Primzahlen belegt, und Yitang Zhangs Beweis von 2013, der die Existenz unendlich vieler Primzahllücken beschränkter Größe zeigt. ^{[ 34 ]}

Die meisten frühen Griechen betrachteten die 1 nicht einmal als Zahl ^{[ 35 ] [ 36 ]} , daher konnten sie auch nicht über ihre Primzahleigenschaft nachdenken. Einige Gelehrte der griechischen und späteren römischen Tradition, darunter Nikomachos , Iamblichos , Boethius und Cassiodorus , sahen die Primzahlen ebenfalls als Unterteilung der ungeraden Zahlen an und betrachteten die 1 daher auch nicht als${\displaystyle 2}$ Primzahl. Euklid und die Mehrheit der anderen griechischen Mathematiker hingegen betrachteten die ${\displaystyle 2}$1 als Primzahl. Die mittelalterlichen islamischen Mathematiker folgten weitgehend den Griechen in ihrer Auffassung, dass die 1 keine Zahl sei. ^{[ 35 ]} Im Mittelalter und in der Renaissance begannen Mathematiker, die 1 als Zahl zu behandeln, und im 17. Jahrhundert zählten einige von ihnen sie zur ersten Primzahl. ^{[ 37 ]} Mitte des 18. Jahrhunderts führte Christian Goldbach die 1 in seinem Briefwechsel mit Leonhard Euler als Primzahl auf . ^{[ 38 ]} Euler selbst betrachtete 1 jedoch nicht als Primzahl. ^{[ 39 ]} Viele Mathematiker des 19. Jahrhunderts hielten 1 dennoch für eine Primzahl, ^{[ 40 ]} und Derrick Norman Lehmer führte 1 in seiner 1914 veröffentlichten Liste von Primzahlen mit weniger als zehn Millionen Einträgen auf. ^{[ 41 ]} Listen von Primzahlen, die 1 enthielten, wurden noch bis 1956 veröffentlicht. ^{[ 42 ] [ 43 ]} Zu Beginn des 20. Jahrhunderts einigten sich Mathematiker jedoch darauf, dass 1 nicht als Primzahl, sondern als „ Einheit “ in einer eigenen Kategorie geführt werden sollte . ^{[ 40 ]}

Würde man 1 als Primzahl betrachten, müssten viele Aussagen über Primzahlen umständlich umformuliert werden. Beispielsweise müsste der Fundamentalsatz der Arithmetik in Bezug auf die Primfaktorzerlegung in Zahlen größer als 1 neu formuliert werden, da jede Zahl mehrere Faktorisierungen mit beliebig vielen Kopien von 1 hätte. ^{[ 40 ] [ 44 ]} Ebenso würde das Sieb des Eratosthenes nicht korrekt funktionieren, wenn es 1 als Primzahl behandeln würde, da es alle Vielfachen von 1 (also alle anderen Zahlen) aussortieren und nur die Zahl 1 ausgeben würde. ^{[ 43 ]} Einige andere, eher technische Eigenschaften von Primzahlen gelten ebenfalls nicht für die Zahl 1: Beispielsweise unterscheiden sich die Formeln für die Eulersche Phi-Funktion oder die Summe der Teiler für Primzahlen von denen für 1. ^{[ 45 ]}

Schreibt man eine Zahl als Produkt von Primzahlen, so nennt man das die Primfaktorzerlegung der Zahl. ^{[ 46 ]} Zum Beispiel:

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

Die Terme im Produkt werden Primfaktoren genannt . Derselbe Primfaktor kann mehrfach vorkommen; in diesem Beispiel kommt der Primfaktor zweimal vor. Wenn eine Primzahl mehrfach auftritt, kann man durch Potenzieren mehrere Kopien derselben Primzahl zusammenfassen: Beispielsweise bezeichnet in der zweiten Schreibweise des obigen Produkts das Quadrat oder die zweite ^Potenz von . ^{[ 46} ]${\displaystyle 5.}$${\displaystyle 5^{2}}$${\displaystyle 5}$

Die zentrale Bedeutung der Primzahlen für die Zahlentheorie und die Mathematik im Allgemeinen rührt vom Fundamentalsatz der Arithmetik her . ^{[ 47 ]} Dieser Satz besagt, dass jede ganze Zahl größer als 1 als Produkt einer oder mehrerer Primzahlen dargestellt werden kann. Genauer gesagt ist dieses Produkt eindeutig, da je zwei Primfaktorzerlegungen derselben Zahl die gleiche Anzahl an Primzahlen enthalten, auch wenn deren Reihenfolge unterschiedlich sein kann. ^{[ 48 ]} Obwohl es also viele verschiedene Wege gibt, eine Primfaktorzerlegung mithilfe eines Algorithmus zur Primfaktorzerlegung ganzer Zahlen zu finden , müssen sie alle zum gleichen Ergebnis führen. Primzahlen können daher als die „Grundbausteine“ der natürlichen Zahlen betrachtet werden. ^{[ 49 ]}

Einige Beweise für die Eindeutigkeit von Primfaktorzerlegungen basieren auf dem Lemma von Euklid : Wenn ⁠ ⁠${\displaystyle p}$ eine Primzahl ist und ⁠ ⁠${\displaystyle p}$ ein Produkt von ganzen Zahlen ⁠ ⁠ teilt , dann teilt ⁠ ⁠ ⁠ ⁠ ⁠ oder ⁠ ⁠ ⁠ ⁠ (oder beides). ^{[ 50 ]} Umgekehrt gilt: Wenn eine Zahl ⁠ ⁠ die Eigenschaft besitzt, dass sie bei der Teilung eines Produkts stets mindestens einen Teiler des Produkts teilt, dann muss ⁠ ⁠ eine Primzahl sein. ^{[ 51 ]}${\displaystyle ab}$${\displaystyle a}$${\displaystyle b,}$${\displaystyle p}$${\displaystyle a}$${\displaystyle p}$${\displaystyle b}$${\displaystyle p}$${\displaystyle p}$

Es gibt unendlich viele Primzahlen. Anders ausgedrückt: Die Folge

${\displaystyle 2,3,5,7,11,13,...}$

Die Anzahl der Primzahlen ist unendlich. Diese Aussage wird zu Ehren des antiken griechischen Mathematikers Euklid als Euklidischer Satz bezeichnet , da ihm der erste bekannte Beweis zugeschrieben wird. Es sind viele weitere Beweise für die Unendlichkeit der Primzahlen bekannt, darunter ein analytischer Beweis von Euler , Goldbachs Beweis basierend auf Fermat-Zahlen ^{[ 52 ]} , Furstenbergs Beweis mithilfe der allgemeinen Topologie ^[ 53 ^{] und} Kummers Beweis durch Widerspruch ^{[ 54 ] [ 55 ]} .

Euklids Beweis zeigt, dass jede endliche Liste von Primzahlen unvollständig ist. ^{[ 56 ]} Die Kernidee besteht darin, die Primzahlen einer gegebenen Liste miteinander zu multiplizieren und zu addieren. Besteht die Liste aus den Primzahlen, so ergibt dies die Anzahl ${\displaystyle 1.}$${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

Nach dem Fundamentalsatz der Arithmetik besitzt ⁠ ⁠${\displaystyle N}$ eine Primfaktorzerlegung

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

mit einem oder mehreren Primfaktoren. ⁠ ⁠${\displaystyle N}$ ist durch jeden dieser Faktoren teilbar, aber ⁠ ⁠${\displaystyle N}$ lässt bei Division durch eine der Primzahlen der gegebenen Liste den Rest 1, daher kann keiner der Primfaktoren von ⁠ ⁠${\displaystyle N}$ in der gegebenen Liste enthalten sein. Da es keine endliche Liste aller Primzahlen gibt, muss es unendlich viele Primzahlen geben.

Die Zahlen, die durch Addition von Eins zu den Produkten der kleinsten Primzahlen entstehen, werden euklidische Zahlen genannt . ^{[ 57 ]} Die ersten fünf von ihnen sind Primzahlen, aber die sechste,

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

ist eine zusammengesetzte Zahl.

Es gibt keine bekannte effiziente Formel für Primzahlen. Beispielsweise existiert kein nicht-konstantes Polynom , selbst nicht in mehreren Variablen, das ausschließlich Primzahlen annimmt. ^{[ 58 ]} Es existieren jedoch zahlreiche Ausdrücke, die entweder alle oder nur Primzahlen kodieren. Eine mögliche Formel basiert auf dem Satz von Wilson und erzeugt die Zahl 2 viele Male und alle anderen Primzahlen genau einmal. ^{[ 59 ]} Es gibt außerdem ein System diophantischer Gleichungen mit neun Variablen und einem Parameter, dessen Eigenschaft lautet: Der Parameter ist genau dann eine Primzahl, wenn das resultierende Gleichungssystem eine Lösung über den natürlichen Zahlen besitzt. Dies kann genutzt werden, um eine Formel zu erhalten, deren positive Werte ausschließlich Primzahlen sind. ^{[ 58 ]}

Weitere Beispiele für Primzahlerzeugungsformeln stammen aus dem Satz von Mills und einem Satz von Wright . Diese besagen, dass es reelle Konstanten gibt , sodass ${\displaystyle A>1}$${\displaystyle \mu }$

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }$

sind Primzahlen für jede natürliche Zahl in${\displaystyle n}$ der ersten Formel und für jede Anzahl von Exponenten in der zweiten Formel. ^{[ 60 ]} Hier bezeichnet die Abrundungsfunktion die größte ganze Zahl , die kleiner oder gleich der fraglichen Zahl ist. Diese Formeln sind jedoch nicht zur Erzeugung von Primzahlen geeignet, da die Primzahlen zuerst erzeugt werden müssen , um die Werte von oder zu berechnen . ^{[ 58 ]}${\displaystyle \lfloor {}\cdot {}\rfloor }$${\displaystyle A}$${\displaystyle \mu .}$

Es wurden zahlreiche Vermutungen über Primzahlen aufgestellt. Viele dieser Vermutungen, die oft elementar formuliert sind, haben jahrzehntelang unbewiesen geblieben: Alle vier Probleme von Landau aus dem Jahr 1912 sind noch immer ungelöst. ^{[ 61 ]} Eine davon ist die Goldbachsche Vermutung , die besagt, dass jede gerade Zahl größer${\displaystyle n}$ als n als Summe zweier Primzahlen geschrieben werden kann. ^{[ 62 ]} Stand 2014 wurde diese Vermutung für alle Zahlen bis n = 2 bestätigt. [ 63 ${\displaystyle 2}$^{] Schwächere Aussagen} wurden bewiesen; beispielsweise besagt der Satz von Vinogradov , dass jede hinreichend große ungerade Zahl als Summe dreier Primzahlen geschrieben werden kann. ^{[ 64 ]} Der Satz von Chen besagt, dass jede hinreichend große gerade Zahl als Summe einer Primzahl und einer Semiprimzahl (dem Produkt zweier Primzahlen) ausgedrückt werden kann. ^{[ 65 ]} Außerdem lässt sich jede gerade Zahl größer als 10 als Summe von sechs Primzahlen darstellen. ^{[ 66 ]} Der Teilbereich der Zahlentheorie, der sich mit solchen Fragen befasst, heißt additive Zahlentheorie . ^{[ 67 ]}${\displaystyle n=4\cdot 10^{18}.}$

Ein weiteres Problem betrifft Primzahllücken , also die Differenzen zwischen aufeinanderfolgenden Primzahlen. Die Existenz beliebig großer Primzahllücken lässt sich dadurch zeigen, dass die Folge aus zusammengesetzten Zahlen besteht , für jede natürliche Zahl ^{[ 68 ].} Große Primzahllücken treten jedoch viel früher auf, als dieses Argument zeigt ^{[ 69 ]} . Beispielsweise liegt die erste Primzahllücke der Länge 8 zwischen den Primzahlen 89 und 97 ^{[ 70 ]} , also deutlich kleiner als die Differenz zwischen zwei aufeinanderfolgenden Primzahlen. Es wird vermutet, dass es unendlich viele Zwillingsprimzahlen gibt , also Paare von Primzahlen mit der Differenz 2; dies ist die Zwillingsprimzahlenvermutung . Polignacs Vermutung besagt allgemeiner, dass es für jede positive ganze Zahl unendlich viele Paare aufeinanderfolgender Primzahlen gibt, die sich um 1/2 unterscheiden. ^{[ 71 ]} Andricas Vermutung ^{[ 71 ]} , Brocards Vermutung [ ^{72 ] ,} Legendres Vermutung ^{[ 73 ]} und Oppermanns Vermutung ^{[ 72 ]} legen nahe, dass die größten Abstände zwischen Primzahlen von 1 bis 1 höchstens ungefähr 1/2 betragen sollten – ein Ergebnis, das bekanntermaßen aus der Riemannschen Vermutung folgt. Die wesentlich stärkere Cramér-Vermutung setzt die größte Abstände auf 1/2 fest . [ 71 ] Primzahllücken lassen sich ^{auf Primzahl -} Tupel verallgemeinern , also auf Muster in den Unterschieden zwischen mehr als zwei Primzahlen. Ihre Unendlichkeit und Dichte sind Gegenstand der ersten Hardy-Littlewood-Vermutung , die sich durch die Heuristik motivieren lässt , dass sich die Primzahlen ähnlich wie eine Zufallsfolge von Zahlen mit einer durch den Primzahlsatz gegebenen Dichte verhalten. ^{[ 74 ]}${\displaystyle n!+2,n!+3,\dots ,n!+n}$${\displaystyle n-1}$${\displaystyle n.}$${\displaystyle 8!=40320.}$${\displaystyle k,}$${\displaystyle 2k.}$${\displaystyle n}$${\displaystyle {\sqrt {n}},}$${\displaystyle O((\log n)^{2})}$${\displaystyle k}$

Die analytische Zahlentheorie untersucht die Zahlentheorie durch die Linse stetiger Funktionen , Grenzwerte , unendlicher Reihen und der damit verbundenen Mathematik des Unendlichen und Infinitesimalen .

Dieses Forschungsgebiet begann mit Leonhard Euler und seinem ersten bedeutenden Ergebnis, der Lösung des Basler Problems . Gesucht war der Wert der unendlichen Summe , die heute als Riemannsche Zetafunktion bekannt ist . Diese Funktion steht in engem Zusammenhang mit den Primzahlen und einem der wichtigsten ungelösten Probleme der Mathematik, der Riemannschen Vermutung . Euler zeigte, dass ⁠ ⁠ . ^{[ 75 ]} Der Kehrwert dieser Zahl, ⁠ ⁠ , ist die Grenzwahrscheinlichkeit, dass zwei zufällig aus einem großen Bereich gleichverteilt ausgewählte Zahlen teilerfremd sind (keine gemeinsamen Teiler haben). ^{[ 76 ]}${\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,}$${\displaystyle \zeta (2)}$${\displaystyle \zeta (2)=\pi ^{2}/6}$${\displaystyle 6/\pi ^{2}}$

Die Verteilung der Primzahlen im Großen, etwa die Frage, wie viele Primzahlen kleiner als eine gegebene, große Schwelle sind, wird durch den Primzahlsatz beschrieben , aber es ist keine effiziente Formel für die n -${\displaystyle n}$ te Primzahl bekannt. Der Satz von Dirichlet über arithmetische Folgen besagt in seiner Grundform, dass lineare Polynome

${\displaystyle p(n)=a+bn}$

Bei teilerfremden ganzen Zahlen nehmen die Zahlen ⁠ ⁠${\displaystyle a}$ und ⁠ ⁠${\displaystyle b}$ unendlich viele Primzahlen an. Obwohl Vermutungen über die Häufigkeit von Primzahlen in Polynomen höheren Grades formuliert wurden, sind diese noch unbewiesen, und es ist unbekannt, ob es ein quadratisches Polynom gibt, das (bei ganzzahligen Argumenten) unendlich oft prim ist.

Eulers Beweis, dass es unendlich viele Primzahlen gibt, betrachtet die Summen der Kehrwerte von Primzahlen.

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}$

Euler zeigte, dass es für jede beliebige reelle Zahl ⁠ ⁠ eine Primzahl ${\displaystyle x}$⁠ ⁠${\displaystyle p}$ gibt, für die diese Summe größer als ⁠ ⁠${\displaystyle x}$ ist . ^{[ 77 ]} Dies beweist, dass es unendlich viele Primzahlen gibt, denn gäbe es nur endlich viele Primzahlen, würde die Summe ihren Maximalwert bei der größten Primzahl erreichen, anstatt über jedes  ⁠ ⁠${\displaystyle x}$ hinaus zu wachsen . Die Wachstumsrate dieser Summe wird genauer durch den zweiten Satz von Mertens beschrieben . ^{[ 78 ]} Zum Vergleich: die Summe

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

strebt nicht gegen unendlich, wenn ⁠ ⁠${\displaystyle n}$ gegen unendlich strebt (siehe das Basler Problem ). In diesem Sinne kommen Primzahlen häufiger vor als Quadrate natürlicher Zahlen, obwohl beide Mengen unendlich sind. ^{[ 79 ]} Der Satz von Brun besagt, dass die Summe der Kehrwerte von Zwillingsprimzahlen

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

ist endlich. Aufgrund des Satzes von Brun ist es nicht möglich, die Zwillingsprimzahlvermutung , dass es unendlich viele Zwillingsprimzahlen gibt, mit dem Euler-Verfahren zu lösen . ^{[ 79 ]}

Die Primzahlzählfunktion ist definiert als die Anzahl der Primzahlen, die nicht größer als ⁠ ⁠ sind . ^{[ 80 ]} Zum Beispiel ⁠ ⁠ , da es fünf Primzahlen kleiner oder gleich 11 gibt. Methoden wie der Meissel-Lehmer-Algorithmus können exakte Werte von schneller berechnen, als es möglich wäre, jede Primzahl bis ⁠ ⁠ aufzulisten . ^{[ 81 ]} Der Primzahlsatz besagt, dass ⁠ ⁠ asymptotisch gegen ⁠ ⁠ konvergiert, was mit ⁠ ... ${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (11)=5}$${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (n)}$${\displaystyle n/\log n}$

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

und bedeutet, dass das Verhältnis von zum rechten Bruch gegen 1 strebt , wenn ⁠ ⁠ gegen unendlich strebt. ^{[ 82 ]} Daraus folgt, dass die Wahrscheinlichkeit, dass eine zufällig gewählte Zahl kleiner als ⁠ ⁠ eine Primzahl ist, (annähernd) umgekehrt proportional zur Anzahl der Ziffern in  ⁠ ⁠ ist . ^{[ 83 ]} Es folgt außerdem, dass die ⁠ ⁠ -te Primzahl proportional zu ⁠ ⁠ ist ^{[ 84 ]} und daher die durchschnittliche Größe einer Primzahllücke proportional zu ⁠ ⁠ ist . ^{[ 69 ]} Eine genauere Schätzung für liefert das Offset-Logarithmusintegral ^{[ 82 ].}${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n\log n}$${\displaystyle \log n}$${\displaystyle \pi (n)}$

${\displaystyle \pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

Eine arithmetische Folge ist eine endliche oder unendliche Zahlenfolge, bei der alle aufeinanderfolgenden Zahlen die gleiche Differenz aufweisen. ^{[ 85 ]} Diese Differenz wird als Betrag der Folge bezeichnet. ^{[ 86 ]} Zum Beispiel:

${\displaystyle 3,12,21,30,39,...,}$

ist eine unendliche arithmetische Folge mit Modulo 9. In einer arithmetischen Folge haben alle Zahlen denselben Rest bei Division durch den Modulo; in diesem Beispiel ist der Rest 3. Da sowohl Modulo 9 als auch Rest 3 Vielfache von 3 sind, ist auch jedes Element der Folge ein Vielfaches von 3. Daher enthält diese Folge nur eine Primzahl, nämlich 3 selbst. Im Allgemeinen ist die unendliche Folge

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

Eine Folge kann nur dann mehr als eine Primzahl enthalten, wenn ihr Rest und ihr ${\displaystyle a}$Betrag teilerfremd sind${\displaystyle q}$ . Sind sie teilerfremd, so besagt der Satz von Dirichlet über arithmetische Folgen, dass die Folge unendlich viele Primzahlen enthält. ^{[ 87 ]}

Primzahlen in arithmetischen Folgen modulo 9. Jede Zeile des schmalen horizontalen Streifens zeigt eine der neun möglichen Folgen modulo 9, wobei die Primzahlen rot markiert sind. Die Folgen von Zahlen, die 0, 3 oder 6 modulo 9 sind, enthalten höchstens eine Primzahl (die Zahl 3); die übrigen Folgen von Zahlen, die 1, 2, 4, 5, 7 und 8 modulo 9 sind, enthalten unendlich viele Primzahlen, wobei jede Folge eine ähnliche Anzahl von Primzahlen aufweist.

Der Satz von Green-Tao zeigt, dass es beliebig lange endliche arithmetische Folgen gibt, die nur aus Primzahlen bestehen. ^{[ 34 ] [ 88 ]}

Euler bemerkte, dass die Funktion

${\displaystyle n^{2}-n+41}$

Die Funktion liefert Primzahlen für ⁠ ⁠${\displaystyle 1\leq n\leq 40}$ , obwohl unter ihren späteren Werten auch zusammengesetzte Zahlen auftreten. ^{[ 89 ] [ 90 ]} Die Suche nach einer Erklärung für dieses Phänomen führte zur tiefen algebraischen Zahlentheorie der Heegner-Zahlen und zum Klassenzahlenproblem . ^{[ 91 ]} Die Hardy-Littlewood-Vermutung F sagt die Dichte der Primzahlen unter den Werten quadratischer Polynome mit ganzzahligen Koeffizienten in Abhängigkeit vom logarithmischen Integral und den Polynomkoeffizienten voraus. Es wurde bisher kein quadratisches Polynom bewiesen, das unendlich viele Primzahlen annimmt. ^{[ 92 ]}

Die Ulam-Spirale ^{[ 93 ]} ordnet die natürlichen Zahlen in einem zweidimensionalen Gitter an, das sich in konzentrischen Quadraten um den Ursprung windet, wobei die Primzahlen hervorgehoben sind. Visuell scheinen sich die Primzahlen auf bestimmten Diagonalen zu konzentrieren, nicht aber auf anderen, was darauf hindeutet, dass manche quadratischen Polynome häufiger Primzahlen annehmen als andere. ^{[ 92 ]}

Der russische Mathematiker Viktor Bunyakovsky vermutete 1857 , dass jedes Polynom einer Variablen mit ganzzahligen Koeffizienten unendlich viele Primzahlen in der Folge erzeugen würde . Ein solches Polynom muss die Bedingungen erfüllen, dass sein Leitkoeffizient positiv ist, es über den rationalen Zahlen irreduzibel ist und der Wert einer solchen Folge keinen gemeinsamen Teiler größer als 1 besitzt. Diese Vermutung wurde von dem polnischen Mathematiker Andrzej Schinzel in seiner Hypothese H verallgemeinert und später in der Dickson-Vermutung und der Bateman-Horn-Vermutung auf Polynome mehrerer Variablen erweitert . ^{[ 94 ]}${\displaystyle f(x)}$${\displaystyle f(1),f(2),f(3),\dots }$

Eine der bekanntesten ungelösten Fragen der Mathematik, die aus dem Jahr 1859 stammt und zu den Millennium-Problemen gehörte , ist die Riemannsche Vermutung . Sie fragt nach den Nullstellen der Riemannschen Zetafunktion . Diese Funktion ist eine analytische Funktion der komplexen Zahlen . [ ^{95 ] Für} komplexe Zahlen mit Realteil größer als eins entspricht sie sowohl einer unendlichen Summe über alle ganzen Zahlen als auch einem unendlichen Produkt über die Primzahlen. Diese von Euler entdeckte Gleichheit zwischen einer Summe und einem Produkt wird Euler-Produkt genannt . ^{[ 96 ]} Das Euler-Produkt lässt sich aus dem Fundamentalsatz der Arithmetik ableiten und zeigt den engen Zusammenhang zwischen der Zetafunktion und den Primzahlen auf. ^{[ 97 ]} Dies führt zu einem weiteren Beweis für die Existenz unendlich vieler Primzahlen: Gäbe es nur endlich viele, so wäre die Summen-Produkt-Gleichung auch bei ⁠ ⁠ gültig , aber die Summe würde divergieren (es handelt sich um die harmonische Reihe ⁠ ⁠ ), während das Produkt endlich wäre – ein Widerspruch. ^{[ 98 ]}${\displaystyle \zeta (s)}$${\displaystyle s}$$${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}$$${\displaystyle s=1}$${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots }$

Die Riemannsche Vermutung besagt, dass die Nullstellen der Zetafunktion entweder negative gerade Zahlen oder komplexe Zahlen mit Realteil 1/2 sind. ^{[ 99 ]} Der ursprüngliche Beweis des Primzahlsatzes basierte auf einer abgeschwächten Form dieser Vermutung, nämlich dass es keine Nullstellen mit Realteil 1 gibt. ^{[ 100 ] [ 101 ]} Es wurden jedoch auch andere, elementarere Beweise gefunden. ^{[ 102 ]} Die Primzahlzählfunktion lässt sich durch Riemanns explizite Formel als Summe darstellen, deren Terme jeweils von einer der Nullstellen der Zetafunktion stammen. Der Hauptterm dieser Summe ist das logarithmische Integral, und die übrigen Terme bewirken, dass die Summe um den Hauptterm schwankt. ^{[ 103 ]} In diesem Sinne bestimmen die Nullstellen, wie regelmäßig die Primzahlen verteilt sind. Wenn die Riemannsche Vermutung zutrifft, sind diese Schwankungen gering, und die durch den Primzahlsatz gegebene asymptotische Verteilung der Primzahlen gilt auch für viel kürzere Intervalle (deren Länge etwa der Quadratwurzel von ⁠ ⁠${\displaystyle x}$ für Intervalle in der Nähe einer Zahl ⁠ ⁠${\displaystyle x}$ entspricht ). ^{[ 101 ]}

Die modulare Arithmetik modifiziert die übliche Arithmetik, indem sie ausschließlich die Zahlen ⁠ ⁠${\displaystyle \{0,1,2,\dots ,n-1\}}$ für eine natürliche Zahl ⁠ ⁠,${\displaystyle n}$ den sogenannten Modulus, verwendet. Jede andere natürliche Zahl lässt sich in dieses System abbilden, indem man sie durch ihren Rest bei der Division durch ⁠ ⁠${\displaystyle n}$ ersetzt . ^{[ 104 ]} Modulare Summen, Differenzen und Produkte werden berechnet, indem man die gleiche Ersetzung durch den Rest auf das Ergebnis der üblichen Summe, Differenz oder des Produkts von ganzen Zahlen anwendet. ^{[ 105 ]} Die Gleichheit ganzer Zahlen entspricht der Kongruenz in der modularen Arithmetik: ⁠ ⁠${\displaystyle x}$ und ⁠ ⁠${\displaystyle y}$ sind kongruent (geschrieben mod ⁠ ⁠ ), wenn sie bei der Division durch ⁠ ⁠ denselben Rest haben . ^{[ 106 ]} In diesem Zahlensystem ist die Division durch alle von Null verschiedenen Zahlen genau dann möglich, wenn der Modulus eine Primzahl ist. Beispielsweise ist mit der Primzahl 7 als Modulus die Division durch 3 möglich: ⁠ ⁠ , da das Wegnehmen der Nenner durch Multiplikation beider Seiten mit 3 die gültige Formel ergibt . Mit dem zusammengesetzten Modulus 6 ist die Division durch 3 jedoch unmöglich. Es gibt keine gültige Lösung für : Das Wegnehmen der Nenner durch Multiplikation mit 3 führt dazu, dass die linke Seite zu 2 wird, während die rechte Seite entweder 0 oder 3 wird. In der Terminologie der abstrakten Algebra bedeutet die Möglichkeit der Division, dass die modulare Arithmetik modulo einer Primzahl einen Körper oder genauer gesagt einen endlichen Körper bildet , während andere Moduli nur einen Ring , aber keinen Körper ergeben. ^{[ 107 ]}${\displaystyle x\equiv y}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2/3\equiv 3{\bmod {7}}}$${\displaystyle 2\equiv 9{\bmod {7}}}$${\displaystyle 2/3\equiv x{\bmod {6}}}$

Mehrere Sätze über Primzahlen lassen sich mithilfe der modularen Arithmetik formulieren. Beispielsweise besagt der kleine Fermatsche Satz, dass, wenn (mod ⁠ ⁠ ), dann (mod ⁠ ⁠ ). ^{[ 108 ]} Die Summation über alle Wahlen von ⁠ ⁠ ergibt die Gleichung ${\displaystyle a\not \equiv 0}$${\displaystyle p}$${\displaystyle a^{p-1}\equiv 1}$${\displaystyle p}$${\displaystyle a}$

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

Diese Gleichung ist gültig, wenn ⁠ ⁠${\displaystyle p}$ eine Primzahl ist. Giugas Vermutung besagt, dass diese Gleichung auch eine hinreichende Bedingung dafür ist, dass ⁠ ⁠${\displaystyle p}$ eine Primzahl ist. ^{[ 109 ]} Der Satz von Wilson besagt, dass eine ganze Zahl genau dann eine Primzahl ist, wenn ihre Fakultät kongruent zu mod ⁠ ⁠ ist . Für eine zusammengesetzte Zahl  ⁠ ⁠ kann dies nicht gelten, da einer ihrer Faktoren sowohl n als auch ⁠ ⁠ teilt und somit unmöglich ist. ^{[ 110 ]}${\displaystyle p>1}$${\displaystyle (p-1)!}$${\displaystyle -1}$${\displaystyle p}$${\displaystyle n=r\cdot s}$${\displaystyle (n-1)!}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$

Die -adische${\displaystyle p}$ Ordnung einer ganzen Zahl ist die Anzahl der Primfaktoren von 2 in der Primfaktorzerlegung von 2. Dasselbe Konzept lässt sich von ganzen Zahlen auf rationale Zahlen übertragen, indem man die -adische Ordnung eines Bruchs als 2 definiert . Der -adische Betrag einer beliebigen rationalen Zahl ist dann definiert als 2. Multipliziert man eine ganze Zahl mit ihrem -adischen Betrag , so heben sich die Faktoren von 2 in ihrer Primfaktorzerlegung auf , sodass nur die anderen Primzahlen übrig bleiben. So wie der Abstand zwischen zwei reellen Zahlen durch den Betrag ihrer Differenz gemessen werden kann , so kann der Abstand zwischen zwei rationalen Zahlen durch ihren -adischen Abstand, den -adischen Betrag ihrer Differenz , gemessen werden . Gemäß dieser Definition des Abstands liegen zwei Zahlen nahe beieinander (sie haben einen kleinen Abstand), wenn ihre Differenz durch eine hohe Potenz von teilbar ist . Analog dazu, wie die reellen Zahlen aus den rationalen Zahlen und ihren Abständen gebildet werden können, indem man weitere Grenzwerte hinzufügt, um einen vollständigen Körper zu erhalten , lassen sich die rationalen Zahlen mit dem -adischen Abstand zu einem anderen vollständigen Körper, den -adischen Zahlen , erweitern . ^{[ 111 ] [ 112 ]}${\displaystyle \nu _{p}(n)}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle m/n}$${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$${\displaystyle p}$${\displaystyle |q|_{p}}$${\displaystyle q}$${\displaystyle \vert q\vert _{p}=p^{-\nu _{p}(q)}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

Dieses Bild von Ordnung, Absolutbetrag und vollständigem Körper, das sich daraus ableiten lässt, kann auf algebraische Zahlkörper und ihre Bewertungen (bestimmte Abbildungen von der multiplikativen Gruppe des Körpers auf eine total geordnete additive Gruppe , auch Ordnungen genannt), Absolutbeträge (bestimmte multiplikative Abbildungen vom Körper auf die reellen Zahlen, auch Normen genannt ) ^{[ 111 ]} und Stellen (Erweiterungen auf vollständige Körper, in denen der gegebene Körper eine dichte Menge ist , auch Vervollständigungen genannt) ^{[ 113 ]} verallgemeinert werden. Die Erweiterung von den rationalen Zahlen auf die reellen Zahlen ist beispielsweise eine Stelle, in der der Abstand zwischen Zahlen dem üblichen Absolutbetrag ihrer Differenz entspricht. Die entsprechende Abbildung auf eine additive Gruppe wäre der Logarithmus des Absolutbetrags, obwohl dies nicht alle Anforderungen an eine Bewertung erfüllt. Nach dem Satz von Ostrowski sind , bis auf einen natürlichen Äquivalenzbegriff, die reellen Zahlen und die -adischen${\displaystyle p}$ Zahlen mit ihren Ordnungen und Absolutbeträgen die einzigen Werte, Absolutbeträge und Stellenwerte der rationalen Zahlen. ^{[ 111 ]} Das Lokal-Global-Prinzip ermöglicht es, bestimmte Probleme über den rationalen Zahlen zu lösen, indem man Lösungen aus ihren jeweiligen Stellenwerten zusammensetzt, was erneut die Bedeutung der Primzahlen für die Zahlentheorie unterstreicht. ^{[ 114 ]}

Ein kommutativer Ring ist eine algebraische Struktur, in der Addition, Subtraktion und Multiplikation definiert sind. Die ganzen Zahlen bilden einen Ring, und die Primzahlen der ganzen Zahlen wurden auf zwei verschiedene Arten zu Ringen verallgemeinert: als Primelemente und als irreduzible Elemente . Ein Element eines Rings${\displaystyle p}$ heißt prim, wenn es ungleich null ist, kein multiplikatives Inverses besitzt (d. h. keine Einheit ist ) und folgende Bedingung erfüllt: Wenn das Produkt zweier Elemente von teilt , teilt es auch mindestens eines der Elemente oder . Ein Element ist irreduzibel , wenn es weder eine Einheit noch das Produkt zweier anderer Elemente ist , die keine Einheit sind . Im Ring der ganzen Zahlen bilden die Primelemente und die irreduziblen Elemente dieselbe Menge. ${\displaystyle R}$${\displaystyle p}$${\displaystyle xy}$${\displaystyle R}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.}$

In einem beliebigen Ring sind alle Primelemente irreduzibel. Die Umkehrung gilt im Allgemeinen nicht, wohl aber für eindeutige Faktorisierungsringe . ^{[ 115 ]}

Der Fundamentalsatz der Arithmetik gilt (definitionsgemäß) auch in Ringen mit eindeutiger Faktorisierung. Ein Beispiel für einen solchen Ring sind die Gaußschen Zahlen , der${\displaystyle \mathbb {Z} [i]}$ Ring der komplexen Zahlen der Form , wobei die imaginäre Einheit bezeichnet und und beliebige ganze Zahlen sind . Seine Primelemente werden als Gaußsche Primzahlen bezeichnet . Nicht jede Zahl, die unter den ganzen Zahlen prim ist, bleibt auch unter den Gaußschen Zahlen prim; beispielsweise lässt sich die Zahl 2 als Produkt der beiden Gaußschen Primzahlen und darstellen . Rationale Primzahlen (die Primelemente unter den ganzen Zahlen), die kongruent zu 3 mod 4 sind, sind Gaußsche Primzahlen, rationale Primzahlen, die kongruent zu 1 mod 4 sind, jedoch nicht. ^{[ 116 ]} Dies ist eine Folge des Fermatschen Satzes über Summen zweier Quadrate , der besagt, dass eine ungerade Primzahl ⁠ ⁠ als Summe zweier Quadrate ⁠ ⁠ ausgedrückt werden kann und daher als ⁠ ⁠ faktorisierbar ist , genau dann, wenn ⁠ ⁠ gleich 1 mod 4 ist. ^{[ 117 ]}${\displaystyle a+bi}$${\displaystyle i}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 1+i}$${\displaystyle 1-i}$${\displaystyle p}$${\displaystyle p=x^{2}+y^{2}}$${\displaystyle p=(x+iy)(x-iy)}$${\displaystyle p}$

Nicht jeder Ring ist ein eindeutiger Faktorisierungsbereich. Beispielsweise besitzt die Zahl n im Zahlenring (für ganze Zahlen ⁠ ⁠ und ⁠ ⁠ ) zwei Faktorisierungen ⁠ ⁠ , wobei keiner der vier Faktoren weiter reduziert werden kann. Daher besitzt sie keine eindeutige Faktorisierung. Um die eindeutige Faktorisierung auf eine größere Klasse von Ringen auszudehnen, kann der Begriff der Zahl durch den eines Ideals ersetzt werden . Ein Ideal ist eine Teilmenge der Elemente eines Rings, die alle Summen von Paaren seiner Elemente sowie alle Produkte seiner Elemente mit Ringelementen enthält. Primideale , die Primelemente insofern verallgemeinern, als das von einem Primelement erzeugte Hauptideal selbst ein Primideal ist, sind ein wichtiges Werkzeug und Untersuchungsobjekt in der kommutativen Algebra , der algebraischen Zahlentheorie und der algebraischen Geometrie . Die Primideale des Rings der ganzen Zahlen sind die Ideale ⁠ ⁠ , ⁠ ⁠ , ⁠ ⁠ , ⁠ ⁠ , ⁠ ⁠ , ... Der Fundamentalsatz der Arithmetik lässt sich zum Satz von Lasker - Noether verallgemeinern , der jedes Ideal in einem noetherschen kommutativen Ring als Schnittmenge von Primäridealen ausdrückt , welche die entsprechenden Verallgemeinerungen von Primpotenzen sind . ^{[ 118 ]}${\displaystyle a+b{\sqrt {-5}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 21}$${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$${\displaystyle (0)}$${\displaystyle (2)}$${\displaystyle (3)}$${\displaystyle (5)}$${\displaystyle (7)}$${\displaystyle (11)}$

Das Spektrum eines Rings ist ein geometrischer Raum, dessen Punkte die Primideale des Rings sind. ^{[ 119 ]} Auch die arithmetische Geometrie profitiert von diesem Konzept, und viele Konzepte finden sich sowohl in der Geometrie als auch in der Zahlentheorie wieder. Beispielsweise weist die Faktorisierung oder Verzweigung von Primidealen, übertragen auf einen Erweiterungskörper – ein grundlegendes Problem der algebraischen Zahlentheorie –, Ähnlichkeiten mit der Verzweigung in der Geometrie auf . Diese Konzepte können sogar bei zahlentheoretischen Fragestellungen hilfreich sein, die sich ausschließlich mit ganzen Zahlen befassen. So lassen sich beispielsweise Primideale im Ring der ganzen Zahlen quadratischer Zahlkörper zum Beweis der quadratischen Reziprozität verwenden , einer Aussage, die die Existenz von Quadratwurzeln modulo ganzzahligen Primzahlen betrifft. ^{[ 120 ]} Frühe Versuche, den Fermatschen Satz zu beweisen, führten zu Kummers Einführung regulärer Primzahlen , ganzzahliger Primzahlen, die mit dem Fehlen der eindeutigen Faktorisierung in den Kreisteilungszahlen in Zusammenhang stehen . ^{[ 121 ]} Die Frage, wie viele ganzzahlige Primzahlen sich in einem algebraischen Zahlkörper in ein Produkt aus mehreren Primidealen faktorisieren lassen, wird durch den Dichtesatz von Tschebotarew beantwortet , der (angewendet auf die Kreisteilungszahlen) den Satz von Dirichlet über Primzahlen in arithmetischen Folgen als Spezialfall enthält. ^{[ 122 ]}

In der Theorie endlicher Gruppen implizieren die Sätze von Sylow , dass jede Gruppe, deren Ordnung durch eine Primzahlpotenz teilbar ist , eine Untergruppe der Ordnung ⁠ ⁠ besitzt . Nach dem Satz von Lagrange ist jede Gruppe von Primzahlordnung eine zyklische Gruppe , und nach dem Satz von Burnside ist jede Gruppe, deren Ordnung nur durch zwei Primzahlen teilbar ist, auflösbar . ^{[ 123 ]}${\displaystyle p^{n}}$${\displaystyle p^{n}}$

Lange Zeit galt die Zahlentheorie im Allgemeinen und die Primzahltheorie im Besonderen als Inbegriff der reinen Mathematik, ohne Anwendungen außerhalb der Mathematik ^{[ c ]} , abgesehen von der Verwendung von Zahnrädern mit Primzahlen zur gleichmäßigen Verschleißverteilung. ^{[ 124 ]} Insbesondere Zahlentheoretiker wie der britische Mathematiker G. H. Hardy waren stolz darauf, Arbeiten zu verrichten, die keinerlei militärische Bedeutung hatten. ^{[ 125 ]}

Diese Vorstellung von der Reinheit der Zahlentheorie wurde in den 1970er Jahren erschüttert, als öffentlich bekannt wurde, dass Primzahlen als Grundlage für die Entwicklung von Public-Key-Kryptographiealgorithmen dienen können . ^{[ 31 ]} Diese Anwendungen führten zu intensiver Forschung an Algorithmen für das Rechnen mit Primzahlen, insbesondere an Primzahltests – Methoden zur Bestimmung, ob eine gegebene Zahl eine Primzahl ist. Die einfachste Primzahltest-Methode, die Probedivision, ist für große Zahlen zu langsam. Eine Gruppe moderner Primzahltests ist auf beliebige Zahlen anwendbar, während für spezielle Zahlentypen effizientere Tests verfügbar sind. Die meisten Primzahltests geben lediglich an, ob ihr Argument eine Primzahl ist oder nicht. Algorithmen, die zusätzlich den Primfaktor zusammengesetzter Argumente (oder alle ihre Primfaktoren) liefern, werden Faktorisierungsalgorithmen genannt . Primzahlen werden auch in der Berechnung von Prüfsummen , Hashtabellen und Pseudozufallszahlengeneratoren verwendet .

Die einfachste Methode, um zu prüfen, ob eine gegebene ganze Zahl eine Primzahl ist , heißt Probedivision${\displaystyle n}$ . Dabei wird die Zahl${\displaystyle n}$ durch jede ganze Zahl von 2 bis zur Quadratwurzel von geteilt . Jede Zahl, die die Zahl ohne Rest teilt , beweist , dass die Zahl zusammengesetzt ist ; andernfalls ist sie eine Primzahl. Ganze Zahlen größer als die Quadratwurzel müssen nicht geprüft werden, da immer einer der beiden Teiler kleiner oder gleich der Quadratwurzel von ist . Eine weitere Optimierungsmöglichkeit besteht darin , nur Primzahlen als Teiler in diesem Bereich zu prüfen. ^{[ 126 ]} Um beispielsweise zu prüfen, ob 37 eine Primzahl ist, teilt man sie durch die Primzahlen im Bereich von 2 bis ⁠ ⁠ , also 2, 3 und 5. Jede Division ergibt einen Rest ungleich Null, also ist 37 tatsächlich eine Primzahl. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=a\cdot b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle n}$${\displaystyle {\sqrt {37}}}$

Obwohl diese Methode einfach zu beschreiben ist, ist sie für die Prüfung der Primzahleigenschaft großer ganzer Zahlen unpraktisch, da die Anzahl der durchzuführenden Tests exponentiell mit der Anzahl der Stellen dieser Zahlen wächst . ^{[ 127 ]} Dennoch wird die Probedivision weiterhin angewendet, wobei die Teilergröße kleiner als die Quadratwurzel ist, um schnell zusammengesetzte Zahlen mit kleinen Faktoren zu finden, bevor komplexere Methoden auf die Zahlen angewendet werden, die dieses Filter bestehen. ^{[ 128 ]}

Vor dem Computerzeitalter wurden mathematische Tabellen, die alle Primzahlen oder Primfaktorzerlegungen bis zu einer bestimmten Grenze auflisteten, häufig gedruckt. ^{[ 129 ]} Die älteste bekannte Methode zur Erzeugung einer Liste von Primzahlen ist das Sieb des Eratosthenes. ^{[ 130 ]} Die Animation zeigt eine optimierte Variante dieser Methode. ^{[ 131 ]} Eine weitere, asymptotisch effizientere Siebmethode für dasselbe Problem ist das Sieb von Atkin . ^{[ 132 ]} In der höheren Mathematik wendet die Siebtheorie ähnliche Methoden auf andere Probleme an. ^{[ 133 ]}

Einige der schnellsten modernen Tests, um festzustellen, ob eine beliebige Zahl ⁠ ⁠${\displaystyle n}$ eine Primzahl ist, basieren auf probabilistischen (oder Monte-Carlo- )Algorithmen. Das bedeutet, dass sie mit geringer Wahrscheinlichkeit ein falsches Ergebnis liefern. ^{[ 134 ]} Beispielsweise wählt der Solovay-Strassen-Primzahltest für eine gegebene Zahl ⁠ ⁠${\displaystyle p}$ zufällig eine Zahl ⁠ ⁠${\displaystyle a}$ zwischen 2 und n und prüft mithilfe der modularen Exponentiation , ob ⁠ ⁠ durch ⁠ ⁠ teilbar ist . ^{[ d ]} Wenn ja, lautet die Antwort „Ja“, andernfalls „Nein“. Ist ⁠ ⁠ tatsächlich eine Primzahl, lautet die Antwort immer „Ja“ . Ist ⁠ ⁠ hingegen eine zusammengesetzte Zahl, lautet die Antwort „Ja“ mit einer Wahrscheinlichkeit von höchstens 1/2 und „Nein“ mit einer Wahrscheinlichkeit von mindestens 1/2. ^{[ 135 ]} Wird dieser Test ⁠ ⁠ Mal mit derselben Zahl wiederholt, beträgt die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl den Test jedes Mal besteht, höchstens ⁠ ⁠ . Da diese Wahrscheinlichkeit mit der Anzahl der Tests exponentiell abnimmt, bietet sie eine hohe Wahrscheinlichkeit (wenn auch keine Gewissheit), dass eine Zahl, die den wiederholten Test besteht, eine Primzahl ist. Schlägt der Test hingegen einmal fehl, so ist die Zahl mit Sicherheit zusammengesetzt. ^{[ 136 ]} Eine zusammengesetzte Zahl, die einen solchen Test besteht, wird als Pseudoprimzahl bezeichnet . ^{[ 135 ]}${\displaystyle p-2}$${\displaystyle a^{(p-1)/2}\pm 1}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle n}$${\displaystyle 1/2^{n}}$

Im Gegensatz dazu garantieren einige andere Algorithmen, dass ihr Ergebnis stets korrekt ist: Primzahlen werden immer als Primzahlen und zusammengesetzte Zahlen immer als zusammengesetzte Zahlen erkannt. Dies trifft beispielsweise auf die Probedivision zu. Zu den Algorithmen mit garantiert korrekter Ausgabe gehören sowohl deterministische (nicht-zufällige) Algorithmen wie der AKS-Primzahltest [ ^{137 ]} als auch randomisierte Las-Vegas-Algorithmen, bei denen die zufälligen Entscheidungen des Algorithmus das Endergebnis nicht beeinflussen, wie etwa einige Varianten des Primzahlbeweises mittels elliptischer Kurven ^{[ 134 ] .} Wenn die Methode der elliptischen Kurven zu dem Schluss kommt, dass eine Zahl prim ist, liefert sie ein Primzahlzertifikat , das schnell überprüft werden kann ^{[ 138 ]} . Der Primzahltest mittels elliptischer Kurven ist in der Praxis der schnellste der Primzahltests mit garantiert korrekter Ausgabe, seine schnelle Leistung lässt sich jedoch nur durch Heuristiken und nicht durch strenge Beweise erklären. Der AKS-Primzahltest ist nachweislich in Polynomialzeit durchführbar , hat aber einen höheren Polynomexponenten und ist daher in der Praxis langsamer als der Test mit elliptischen Kurven. ^{[ 139 ]} Mit diesen Methoden lassen sich große zufällige Primzahlen erzeugen, indem man Zufallszahlen generiert und testet, bis man eine Primzahl findet. Dabei kann ein schnellerer probabilistischer Test die meisten zusammengesetzten Zahlen schnell ausschließen, bevor ein garantiert korrekter Algorithmus die Primzahleigenschaft der verbleibenden Zahlen überprüft. ^{[ e ]}

Die folgende Tabelle listet einige dieser Tests auf. Ihre Laufzeit wird in Abhängigkeit von der Anzahl der zu testenden Elemente und, bei probabilistischen Algorithmen, der Anzahl der durchgeführten Tests angegeben .${\displaystyle n}$ Dabei ist eine${\displaystyle k}$ beliebig kleine positive Zahl, und log ist der Logarithmus zu einer nicht näher spezifizierten Basis. Die O-Notation bedeutet , dass jede Zeitvorgabe mit einem konstanten Faktor multipliziert werden muss , um sie von dimensionslosen Einheiten in Zeiteinheiten umzurechnen. Dieser Faktor hängt von Implementierungsdetails wie dem verwendeten Computertyp ab, jedoch nicht von den Eingabeparametern und .${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle k}$

Prüfen	Entwickelt in	Typ	Laufzeit	Anmerkungen	Referenzen
AKS-Primzahltest	2002	deterministisch	${\displaystyle O((\log n)^{6+\varepsilon })}$		[ 137 ] [ 140 ]
Primzahlbeweis für elliptische Kurven	1986	Las Vegas	${\displaystyle O((\log n)^{4+\varepsilon })}$heuristisch		[ 139 ]
Baillie-PSW-Primzahltest	1980	Monte Carlo	${\displaystyle O((\log n)^{2+\varepsilon })}$		[ 141 ] [ 142 ]
Miller-Rabin-Primzahltest	1980	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	Fehlerwahrscheinlichkeit${\displaystyle 4^{-k}}$	[ 143 ]
Solovay-Strassen-Primzahltest	1977	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	Fehlerwahrscheinlichkeit${\displaystyle 2^{-k}}$	[ 143 ]

Zusätzlich zu den bereits erwähnten Tests, die für jede natürliche Zahl gelten, lassen sich einige Zahlen spezieller Form schneller auf Primzahleigenschaft prüfen. Beispielsweise kann der Lucas-Lehmer-Primzahltest deterministisch bestimmen, ob eine Mersenne-Zahl (eins kleiner als eine Zweierpotenz ) prim ist, und zwar in der gleichen Zeit, die ein einziger Durchlauf des Miller-Rabin-Tests benötigt. ^{[ 144 ]} Aus diesem Grund ist seit 1992 (Stand Oktober 2024) die größte bekannte Primzahl stets eine Mersenne-Primzahl. ^{[ 145 ]} Es wird vermutet, dass es unendlich viele Mersenne-Primzahlen gibt. ^{[ 146 ]}

Die folgende Tabelle listet die größten bekannten Primzahlen verschiedener Typen auf. Einige dieser Primzahlen wurden mithilfe von verteiltem Rechnen gefunden . Im Jahr 2009 wurde das Projekt „Great Internet Mersenne Prime Search“ mit einem Preisgeld von 100.000 US-Dollar für die erstmalige Entdeckung einer Primzahl mit mindestens 10 Millionen Stellen ausgezeichnet. ^{[ 147 ]} Die Electronic Frontier Foundation (EFF) lobt außerdem 150.000 US-Dollar bzw. 250.000 US-Dollar für Primzahlen mit mindestens 100 Millionen bzw. 1 Milliarde Stellen aus. ^{[ 148 ]}

Die Aufgabe, einen (oder alle) Primfaktoren einer zusammengesetzten Zahl ⁠ ⁠ zu finden, wird als ${\displaystyle n}$Faktorisierung von ⁠ ⁠${\displaystyle n}$ bezeichnet . Sie ist deutlich schwieriger als der Primzahltest ^{[ 156 ]} , und obwohl viele Faktorisierungsalgorithmen bekannt sind, sind diese langsamer als die schnellsten Primzahltestmethoden. Probedivision und Pollards Rho-Algorithmus können verwendet werden, um sehr kleine Faktoren von ⁠ ⁠ zu finden ${\displaystyle n}$^{[ 128 ]} , und die Faktorisierung mittels elliptischer Kurven kann effektiv sein, wenn ⁠ ⁠${\displaystyle n}$ Faktoren mittlerer Größe besitzt ^{[ 157 ]} . Methoden, die für beliebig große Zahlen geeignet sind und nicht von der Größe ihrer Faktoren abhängen, umfassen das quadratische Sieb und das allgemeine Zahlkörpersieb . Wie beim Primzahltest gibt es auch Faktorisierungsalgorithmen, die eine spezielle Form der Eingabe erfordern, darunter das spezielle Zahlkörpersieb . ^{[ 158 ]} Stand Dezember 2019 ist die größte Zahl, die bekanntermaßen mit einem universellen Algorithmus faktorisiert werden konnte, RSA-240 . Sie hat 240 Dezimalstellen (795 Bit) und ist das Produkt zweier großer Primzahlen. ^{[ 159 ]}

Shors Algorithmus kann jede ganze Zahl in polynomieller Anzahl von Schritten auf einem Quantencomputer faktorisieren . ^{[ 160 ]} Die aktuelle Technologie kann diesen Algorithmus jedoch nur für sehr kleine Zahlen ausführen. Stand Oktober 2012 war die größte Zahl, die von einem Quantencomputer mit Shors Algorithmus faktorisiert wurde, 21. ^{[ 161 ]}

Mehrere Public-Key-Kryptographiealgorithmen , wie RSA und der Diffie-Hellman-Schlüsselaustausch , basieren auf großen Primzahlen (2048- Bit -Primzahlen sind üblich). ^{[ 162 ]} RSA beruht auf der Annahme, dass die Multiplikation zweier (großer) Zahlen ⁠ ⁠${\displaystyle x}$ und ⁠ ⁠${\displaystyle y}$ wesentlich einfacher (d. h. effizienter) ist als die Berechnung von ⁠ ⁠${\displaystyle x}$ und ⁠ ⁠${\displaystyle y}$ (angenommen teilerfremd ), wenn nur das Produkt bekannt ist. ^{[ 31 ]} Der Diffie-Hellman-Schlüsselaustausch basiert auf der Tatsache, dass effiziente Algorithmen für die modulare Exponentiation (Berechnung von ⁠ ⁠ ) existieren , während die Umkehroperation (der diskrete Logarithmus ) als schwieriges Problem gilt. ^{[ 163 ]}${\displaystyle xy}$${\displaystyle a^{b}{\bmod {c}}}$

Primzahlen werden häufig für Hashtabellen verwendet . Beispielsweise basierte die ursprüngliche Methode von Carter und Wegman für universelles Hashing auf der Berechnung von Hashfunktionen durch die Wahl zufälliger linearer Funktionen modulo großer Primzahlen. Carter und Wegman verallgemeinerten diese Methode zu α -${\displaystyle k}$ unabhängigem Hashing durch die Verwendung von Polynomen höheren Grades, wiederum modulo großer Primzahlen. ^{[ 164 ]} Ebenso wie in der Hashfunktion werden Primzahlen auch für die Größe der Hashtabelle in auf quadratischem Sondieren basierenden Hashtabellen verwendet, um sicherzustellen, dass die Sondierungssequenz die gesamte Tabelle abdeckt. ^{[ 165 ]}

Einige Prüfsummenverfahren basieren auf der Mathematik der Primzahlen. Beispielsweise werden die in International Standard Book Numbers (ISBN) verwendeten Prüfsummen durch die Berechnung des Restes der Zahl modulo 11, einer Primzahl, definiert. Da 11 eine Primzahl ist, kann dieses Verfahren sowohl einstellige Fehler als auch Vertauschungen benachbarter Ziffern erkennen. ^{[ 166 ]} Ein anderes Prüfsummenverfahren, das Adler-32- Verfahren , verwendet Arithmetik modulo 65521, der größten Primzahl kleiner als 1. [ ${\displaystyle 2^{16}}$^{167 ] Primzahlen} werden auch in Pseudozufallszahlengeneratoren verwendet , darunter lineare Kongruenzgeneratoren ^{[ 168 ]} und der Mersenne-Twister . ^{[ 169 ]}

Primzahlen sind von zentraler Bedeutung für die Zahlentheorie, finden aber auch in vielen anderen Bereichen der Mathematik Anwendung, darunter in der abstrakten Algebra und der elementaren Geometrie. Beispielsweise lassen sich Primzahlen von Punkten in einem zweidimensionalen Gitter so anordnen, dass keine drei Punkte auf einer Geraden liegen oder dass jedes von drei dieser Punkte gebildete Dreieck eine große Fläche hat . ^{[ 170 ]} Ein weiteres Beispiel ist das Eisenstein-Kriterium , ein Test, der prüft, ob ein Polynom irreduzibel ist, basierend auf der Teilbarkeit seiner Koeffizienten durch eine Primzahl und deren Quadrat. ^{[ 171 ]}

Der Begriff der Primzahl ist so wichtig, dass er in verschiedenen Bereichen der Mathematik auf unterschiedliche Weise verallgemeinert wurde. Im Allgemeinen bezeichnet „prim“ Minimalität oder Unzerlegbarkeit im entsprechenden Sinne. Beispielsweise ist der Primkörper eines gegebenen Körpers dessen kleinster Teilkörper, der sowohl 0 als auch 1 enthält. Es handelt sich entweder um den Körper der rationalen Zahlen oder um einen endlichen Körper mit einer Primzahl an Elementen, daher der Name. ^{[ 172 ]} Oftmals wird mit dem Wort „prim“ eine zweite, zusätzliche Bedeutung gemeint, nämlich dass sich jedes Objekt im Wesentlichen eindeutig in seine Primkomponenten zerlegen lässt. In der Knotentheorie ist beispielsweise ein Primknoten ein Knoten , der in dem Sinne unzerlegbar ist, dass er nicht als zusammenhängende Summe zweier nichttrivialer Knoten dargestellt werden kann. Jeder Knoten lässt sich eindeutig als zusammenhängende Summe von Primknoten ausdrücken. ^{[ 173 ]} Die Primzerlegung von 3-Mannigfaltigkeiten ist ein weiteres Beispiel hierfür. ^{[ 174 ]}

Über Mathematik und Informatik hinaus bergen Primzahlen potenzielle Verbindungen zur Quantenmechanik und wurden in Kunst und Literatur metaphorisch verwendet. Auch in der Evolutionsbiologie finden sie Anwendung , beispielsweise zur Erklärung der Lebenszyklen von Zikaden .

Fermat-Primzahlen sind Primzahlen der Form

${\displaystyle F_{k}=2^{2^{k}}+1,}$

mit einer nichtnegativen ${\displaystyle k}$ganzen Zahl . ^{[ 175 ]} Sie sind nach Pierre de Fermat benannt , der vermutete , dass alle diese Zahlen Primzahlen sind. Die ersten fünf dieser Zahlen – 3, 5, 17, 257 und 65.537 – sind Primzahlen, ^{[ 176 ]} aber ist zusammengesetzt, ebenso wie alle anderen Fermat-Zahlen, die bis 2017 verifiziert wurden. ^{[ 177 ]} Ein regelmäßiges -Eck lässt sich mit Zirkel und Lineal genau dann konstruieren , wenn die ungeraden Primfaktoren von ( falls vorhanden) verschiedene Fermat-Primzahlen sind. ^{[ 176 ]} Ebenso kann ein regelmäßiges ⁠ ⁠ -Eck mit Lineal, Zirkel und Winkeldreiteiler genau dann konstruiert werden, wenn die Primfaktoren von ⁠ ⁠ eine beliebige Anzahl von Kopien von 2 oder 3 zusammen mit einer (möglicherweise leeren) Menge von verschiedenen Pierpont-Primzahlen , Primzahlen der Form ⁠ ⁠ , sind . ^{[ 178 ]}${\displaystyle F_{5}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2^{a}3^{b}+1}$

Es ist möglich , jedes konvexe Polygon in kleinere konvexe Polygone mit gleichem Flächeninhalt und gleichem Umfang zu zerlegen , wenn ${\displaystyle n}$^eine Potenz einer Primzahl ist ;${\displaystyle n}$ dies ist jedoch für andere Werte von nicht bekannt . ^[ 179 ^]${\displaystyle n}$

Ausgehend von den Arbeiten von Hugh Montgomery und Freeman Dyson in den 1970er Jahren spekulierten Mathematiker und Physiker, dass die Nullstellen der Riemannschen Zetafunktion mit den Energieniveaus von Quantensystemen zusammenhängen . ^{[ 180 ] [ 181 ]} Primzahlen sind auch in der Quanteninformationswissenschaft von Bedeutung , dank mathematischer Strukturen wie zueinander unvoreingenommenen Basen und symmetrischen informationsvollständigen Maßen mit positiven Operatorwerten . ^{[ 182 ] [ 183 ]}

Die evolutionäre Strategie der Zikaden der Gattung Magicicada nutzt Primzahlen. ^{[ 184 ]} Diese Insekten verbringen den Großteil ihres Lebens als Larven unter der Erde. Erst nach 7, 13 oder 17 Jahren verpuppen sie sich und verlassen ihre Höhlen. Dann fliegen sie umher, pflanzen sich fort und sterben nach höchstens wenigen Wochen. Biologen vermuten, dass sich diese auf Primzahlen basierenden Fortpflanzungszyklen entwickelt haben, um zu verhindern, dass Fressfeinde sich mit diesen Zyklen synchronisieren. ^{[ 185 ] [ 186 ]} Im Gegensatz dazu wird angenommen, dass die mehrjährigen Perioden zwischen den Blütezeiten von Bambuspflanzen glatte Zahlen darstellen , deren Faktorisierung nur kleine Primzahlen enthält. ^{[ 187 ]}

Primzahlen haben viele Künstler und Schriftsteller beeinflusst. Der französische Komponist Olivier Messiaen nutzte Primzahlen, um durch „Naturphänomene“ ametrische Musik zu schaffen. In Werken wie „La Nativité du Seigneur“ (1935) und „Quatre études de rythme“ (1949–1950) verwendet er gleichzeitig Motive unterschiedlicher Primzahllänge, um unvorhersehbare Rhythmen zu erzeugen: Die Primzahlen 41, 43, 47 und 53 erscheinen in der dritten Etüde „Neumes rythmiques“. Laut Messiaen war diese Kompositionsweise „von den Bewegungen der Natur inspiriert, von Bewegungen freier und ungleicher Dauer“. ^{[ 188 ]}

In seinem Science-Fiction-Roman „ Contact“ schlug der Wissenschaftler Carl Sagan vor, die Primfaktorzerlegung zur Etablierung zweidimensionaler Bildebenen in der Kommunikation mit Außerirdischen zu nutzen – eine Idee, die er 1975 informell mit dem amerikanischen Astronomen Frank Drake entwickelt hatte. ^{[ 189 ]} In Mark Haddons Roman „ Supergute Tage“ ordnet der Erzähler die Abschnitte der Geschichte nach aufeinanderfolgenden Primzahlen, um den mentalen Zustand der Hauptfigur, eines mathematisch begabten Teenagers mit Asperger-Syndrom, zu verdeutlichen . ^{[ 190 ]} In Paolo Giordanos Roman „Die Einsamkeit der Primzahlen“ dienen Primzahlen als Metapher für Einsamkeit und Isolation ; sie werden dort als „Außenseiter“ unter den ganzen Zahlen dargestellt. ^{[ 191 ]} Der Gaunerfilm „Sneakers“ aus dem Jahr 1992 zeigt eine fiktive Methode, große Zahlen schnell in Primzahlen zu zerlegen und so Computerverschlüsselungssysteme zu knacken. ^{[ 192 ] [ 193 ] [ 194 ]}