Primzahl

Eine Primzahl (von lateinisch numerus primus ‚erste Zahl‘) ist eine natürliche Zahl, die genau zwei Teiler hat (und somit größer als 1 ist). Diese zwei Teiler sind 1 und die Zahl selber. Dabei bedeutet primus speziell „Anfang, das Erste (der Dinge)“,^[1] sodass eine „Anfangszahl“ gemeint ist, die aus keiner anderen natürlichen Zahl multiplikativ konstruiert werden kann.^[2]

Die Menge der Primzahlen wird in der Regel mit dem Symbol ${\displaystyle \mathbb {P} }$ bezeichnet. Man weiß durch den Satz des Euklid seit der Antike, dass es unendlich viele Primzahlen gibt. Mit ${\displaystyle \mathbb {P} }$ verknüpft ist die Folge ${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }}$ der nach ihrer Größe geordneten Primzahlen, die man auch Primzahlfolge nennt.

Die Primzahlen lassen sich unter anderem mit Hilfe der Teileranzahlfunktion ${\displaystyle d(n)}$ definieren:

${\displaystyle \mathbb {P} =\{n\in \mathbb {N} \mid d(n)=2\}.}$

Es ist demnach

${\displaystyle \mathbb {P} =\{p_{n}\mid n\in \mathbb {N} \}\subset \mathbb {N} }$

mit

${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }=\left(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,\dotsc \right)}$ (Folge A000040 in OEIS).

Die Bedeutung der Primzahlen für viele Bereiche der Mathematik beruht auf drei Folgerungen aus ihrer Definition:

• Existenz und Eindeutigkeit der Primfaktorzerlegung: Jede natürliche Zahl, die größer als 1 und selbst keine Primzahl ist, lässt sich als Produkt von mindestens zwei Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Zum Beweis dient das
• Lemma von Euklid: Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist mindestens einer der Faktoren durch sie teilbar.
• Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen.

Diese Eigenschaften werden in der Algebra für Verallgemeinerungen des Primzahlbegriffs genutzt.

Eine Zahl, die das Produkt von zwei oder mehr Primfaktoren ist, nennt man zusammengesetzt. Die Zahl 1 ist weder prim noch zusammengesetzt. Alle anderen natürlichen Zahlen sind eines von beiden, entweder prim (also Primzahl) oder zusammengesetzt.

Schon im antiken Griechenland interessierte man sich für die Primzahlen und entdeckte einige ihrer Eigenschaften. Obwohl Primzahlen seit damals stets einen großen Reiz auf die Menschen ausübten, sind viele die Primzahlen betreffenden Fragen bis heute ungeklärt, darunter solche, die mehr als hundert Jahre alt und leicht verständlich formulierbar sind. Dazu gehören die Goldbachsche Vermutung, wonach außer 2 jede gerade Zahl als Summe zweier Primzahlen darstellbar ist, und die Vermutung, dass es unendlich viele Primzahlzwillinge gibt (das sind Paare von Primzahlen, deren Differenz gleich 2 ist).

Primzahlen und ihre Eigenschaften spielen in der Kryptographie eine große Rolle, weil Primfaktoren auch mit dem Aufkommen elektronischer Rechenmaschinen nicht effizient gefunden werden können. Andererseits ermöglichen diese Maschinen eine effiziente Verschlüsselung sowie, wenn man den Schlüssel kennt, Entschlüsselung auch langer Texte.

Die Primzahlen sind innerhalb der Menge ${\displaystyle \mathbb {N} }$ der natürlichen Zahlen dadurch charakterisiert, dass jede von ihnen genau zwei natürliche Zahlen als Teiler hat.^[3]

Mit Ausnahme der Zahl 2 sind alle Primzahlen ${\displaystyle p}$ ungerade, denn alle größeren geraden Zahlen lassen sich außer durch sich selbst und 1 auch noch (mindestens) durch 2 teilen. Damit hat jede Primzahl außer 2 die Form ${\displaystyle 2k+1}$ mit einer natürlichen Zahl ${\displaystyle k}$.

Jede Primzahl ${\displaystyle p\neq 2}$ lässt sich einer der beiden Klassen „Primzahl der Form ${\displaystyle 4k+1}$“ oder „Primzahl der Form ${\displaystyle 4k+3}$“ zuordnen, wobei ${\displaystyle k}$ eine natürliche Zahl ist. Von den ersten ${\displaystyle 1000}$ Primzahlen ${\displaystyle p\neq 2}$ haben ${\displaystyle 495}$ die Form ${\displaystyle 4n+1}$ und ${\displaystyle 505}$ die Form ${\displaystyle 4n+3}$. Setzt man die Primzahlfolge fort, so nähern sich die Anteile beider Formen dem Wert ${\displaystyle 0{,}5}$.^[4]

Jede Primzahl ${\displaystyle p\neq 3}$ lässt sich zudem einer der beiden Klassen „Primzahl der Form ${\displaystyle 3k+1}$“ oder „Primzahl der Form ${\displaystyle 3k+2}$“ zuordnen, wobei ${\displaystyle k}$ eine natürliche Zahl ist.

Darüber hinaus hat jede Primzahl ${\displaystyle p>3}$ die Form ${\displaystyle p=6k+1}$ oder ${\displaystyle p=6k-1}$, wobei ${\displaystyle k}$ eine natürliche Zahl ist. Ferner endet jede Primzahl ${\displaystyle p>5}$ auf eine der vier Dezimalziffern ${\displaystyle 1,3,7}$ oder ${\displaystyle 9}$. Nach dem Dirichletschen Primzahlsatz gibt es in jeder dieser Klassen unendlich viele Primzahlen.

Jede natürliche Zahl der Form ${\displaystyle 4m+3}$ mit einer nichtnegativen ganzen Zahl ${\displaystyle m}$ enthält mindestens einen Primfaktor der Form ${\displaystyle 4k+3}$. Eine entsprechende Aussage über Zahlen der Form ${\displaystyle 4m+1}$ oder Primfaktoren der Form ${\displaystyle 4k+1}$ ist nicht möglich.

Eine Primzahl ${\displaystyle p>2}$ lässt sich genau dann in der Form ${\displaystyle a^{2}+b^{2}}$ mit ganzen Zahlen ${\displaystyle a,b}$ schreiben, wenn ${\displaystyle p}$ die Form ${\displaystyle 4k+1}$ hat (Zwei-Quadrate-Satz). In diesem Fall ist die Darstellung im Wesentlichen eindeutig, d. h. bis auf Reihenfolge und Vorzeichen von ${\displaystyle a,b}$. Diese Darstellung entspricht der Primfaktorzerlegung

${\displaystyle p=(a+b\mathrm {i} )(a-b\mathrm {i} )}$

im Ring der ganzen Gaußschen Zahlen.

Die Zahl −1 ist quadratischer Rest modulo jeder Primzahl der Form ${\displaystyle 4k+1}$ und quadratischer Nichtrest modulo jeder Primzahl der Form ${\displaystyle 4k+3}$.

Eine Primzahl ${\displaystyle p>3}$ lässt sich zudem genau dann eindeutig in der Form ${\displaystyle a^{2}+3b^{2}}$ mit ganzen Zahlen ${\displaystyle a,b}$ schreiben, wenn ${\displaystyle p}$ die Form ${\displaystyle 3k+1}$ hat.^[5]

Ist eine Zahl ${\displaystyle n>1}$ durch keine Primzahl ${\displaystyle 2\leq p\leq {\sqrt {n}}}$ teilbar, so ist ${\displaystyle n}$ eine Primzahl (siehe Abschnitt Primzahltests und Artikel Probedivision).

Es sei ${\displaystyle p}$ eine Primzahl. Für jede ganze Zahl ${\displaystyle a}$, die nicht durch ${\displaystyle p}$ teilbar ist, gilt (für die Notation siehe Kongruenz):

${\displaystyle a^{p-1}\equiv 1\mod p}$

Für nicht durch ${\displaystyle p}$ teilbare Zahlen ${\displaystyle a}$ ist die folgende Formulierung äquivalent:

${\displaystyle a^{p}\equiv a\mod p}$

Es gibt Zahlen ${\displaystyle n}$, die keine Primzahlen sind, sich aber dennoch zu einer Basis ${\displaystyle a}$ wie Primzahlen verhalten, d. h., es ist ${\displaystyle a^{n-1}\equiv 1{\bmod {n}}}$. Solche ${\displaystyle n}$ nennt man Fermatsche Pseudoprimzahlen zur Basis ${\displaystyle a}$. Ein ${\displaystyle n}$, das Fermatsche Pseudoprimzahl bezüglich aller zu ihm teilerfremden Basen ${\displaystyle a}$ ist, nennt man Carmichael-Zahl.

In diesem Zusammenhang zeigt sich die Problematik Fermatscher Pseudoprimzahlen: Sie werden von einem Primzahltest, der den kleinen Satz von Fermat nutzt (Fermatscher Primzahltest), fälschlicherweise für Primzahlen gehalten. Wenn allerdings ein Verschlüsselungsverfahren wie RSA eine zusammengesetzte Zahl statt einer Primzahl verwendet, ist die Verschlüsselung nicht mehr sicher. Deshalb müssen bei solchen Verfahren bessere Primzahltests verwendet werden.

Eine einfache Folge aus dem kleinen Satz von Fermat ist: Für jede ungerade Primzahl ${\displaystyle p}$ und jede ganze Zahl ${\displaystyle a}$, die nicht durch ${\displaystyle p}$ teilbar ist, gilt entweder

${\displaystyle a^{\frac {p-1}{2}}\equiv 1\mod p}$

oder

${\displaystyle a^{\frac {p-1}{2}}\equiv -1\mod p.}$

Der erste Fall tritt genau dann ein, wenn es eine Quadratzahl gibt, die kongruent zu ${\displaystyle a}$ modulo ${\displaystyle p}$ ist, siehe Legendre-Symbol.

Für Primzahlen ${\displaystyle p}$ und ${\displaystyle 1\leq k<p}$ gilt

${\displaystyle p\,{\Big |}{p \choose k}.}$

Zusammen mit dem binomischen Satz folgt daraus

${\displaystyle (a+b)^{p}\equiv a^{p}+b^{p}\mod p.}$

Für ganze Zahlen ${\displaystyle a,b}$ folgt diese Aussage auch direkt aus dem kleinen Fermatschen Satz, aber sie ist beispielsweise auch für Polynome mit ganzzahligen Koeffizienten anwendbar; im allgemeinen Kontext entspricht sie der Tatsache, dass die Abbildung ${\displaystyle x\mapsto x^{p}}$ in Ringen der Charakteristik ${\displaystyle p}$ ein Homomorphismus ist, der sogenannte Frobenius-Homomorphismus.

Aus dem Satz von Wilson (${\displaystyle p}$ ist genau dann eine Primzahl, wenn ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ ist) folgt, dass für jede Primzahl ${\displaystyle p}$ und jede natürliche Zahl ${\displaystyle n}$ die Kongruenz

${\displaystyle {{np-1} \choose {p-1}}\equiv 1{\pmod {p}}}$

erfüllt ist.

Charles Babbage bewies 1819, dass für jede Primzahl ${\displaystyle p>2}$ diese Kongruenz gilt:

${\displaystyle {{2p-1} \choose {p-1}}\equiv 1{\pmod {p^{2}}}}$

Der Mathematiker Joseph Wolstenholme (1829–1891) bewies dann 1862, dass für jede Primzahl ${\displaystyle p>3}$ die folgende Kongruenz gilt:

${\displaystyle {{2p-1} \choose {p-1}}\equiv 1{\pmod {p^{3}}}}$

Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl ${\displaystyle p}$ gilt:

${\displaystyle 1^{p-1}+2^{p-1}+\dotsb +(p-1)^{p-1}\equiv -1{\pmod {p}}}$

Beispiel ${\displaystyle p=5}$:

${\displaystyle 1^{4}+2^{4}+3^{4}+4^{4}=1+16+81+256=354=71\cdot 5-1\equiv -1{\pmod {5}}}$

Giuseppe Giuga vermutete, dass auch die umgekehrte Schlussrichtung gilt, dass also eine Zahl mit dieser Eigenschaft stets prim ist. Es ist nicht geklärt, ob diese Vermutung richtig ist. Bekannt ist aber, dass ein Gegenbeispiel mehr als 10.000 Dezimalstellen haben müsste. Im Zusammenhang mit Giugas Vermutung werden die Giuga-Zahlen untersucht.

Den kleinen Fermatschen Satz kann man auch in der Form lesen: In der Folge ${\displaystyle a^{n}-a}$ ist für eine Primzahl ${\displaystyle p}$ das ${\displaystyle p}$-te Folgenglied stets durch ${\displaystyle p}$ teilbar. Ähnliche Eigenschaften besitzen auch andere Folgen von exponentiellem Charakter, wie die Lucas-Folge (${\displaystyle p\mid L_{p}-1}$) und die Perrin-Folge (${\displaystyle p\mid P_{p}}$). Für andere lineare Rekursionen gelten analoge, aber kompliziertere Aussagen, beispielsweise für die Fibonacci-Folge ${\displaystyle (f_{n})_{n=0,1,2,\dotsc }=0,1,1,2,3,5,\dotsc }$: Ist ${\displaystyle p}$ eine Primzahl, so ist ${\displaystyle f_{p}-\left({\frac {p}{5}}\right)}$ durch ${\displaystyle p}$ teilbar. Dabei ist

${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}1&p\equiv 1,4\mod 5\\-1&p\equiv 2,3\mod 5\\0&p=5\end{cases}}}$

das Legendre-Symbol.

Die Reihe der Kehrwerte der Primzahlen ist bestimmt divergent. Somit gilt:

${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{p_{k}}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\dotsb =\infty }$

Das ist gleichbedeutend mit der Aussage, dass die durch ${\displaystyle \textstyle a_{n}=\sum _{k=1}^{n}{\frac {1}{p_{k}}}}$ definierte Folge keinen endlichen Grenzwert besitzt, was wiederum bedeutet, dass ${\displaystyle a_{n}}$ jede reelle Zahl übertreffen kann, indem man ${\displaystyle n}$ groß genug wählt. Dies ist zunächst einmal verblüffend, da die Primzahllücken im Schnitt immer weiter zunehmen. Der Satz von Mertens trifft eine Aussage über das genaue Wachstumsverhalten dieser divergenten Reihe.

Es sind verschiedene Primzahlformeln bekannt, von denen einige in der bekannten Monographie The New Book of Prime Number Records von Paulo Ribenboim aus dem Jahre 1996 dargestellt werden.^[6] Dazu zählen nicht zuletzt eine Formel von Wacław Sierpiński aus dem Jahre 1952,^[7] eine Formel von C. P. Willans aus dem Jahre 1964^[8] und eine Formel von J. M. Gandhi aus dem Jahre 1971^[9].

Die für jede natürliche Zahl ${\displaystyle n\geq 1}$ gültige Sierpiński’sche Formel geht von der konvergenten Reihe

${\displaystyle \alpha =\sum _{k=1}^{\infty }\left({\frac {p_{k}}{10^{2^{k}}}}\right)}$

aus. Damit erhält man:

${\displaystyle p_{n}=\lfloor 10^{2^{n}}\cdot \alpha \rfloor -10^{2^{n-1}}\cdot \lfloor 10^{2^{n-1}}\cdot \alpha \rfloor }$^{[A 1]}

Die für natürlichzahliges ${\displaystyle n\geq 1}$ gültige Formel von Willans zeigt, wie man die Primzahlen aus der Primzahlfunktion zurückgewinnen kann. Es gilt nämlich:

${\displaystyle p_{n}=1+\sum _{k=1}^{2^{n}}{\lfloor {\lfloor {\frac {n}{1+\pi (k)}}\rfloor }^{\frac {1}{n}}\rfloor }}$

Die für alle natürlichen Zahlen ${\displaystyle n\geq 1}$ gültige Gandhi’sche Formel zeigt, wie man die Primzahlen mit Hilfe der Möbiusfunktion ${\displaystyle \mu }$ und dem natürlichen Logarithmus ${\displaystyle \ln }$ darstellen kann. Hier gilt nämlich, wenn ${\displaystyle P_{n-1}=p_{1}\cdot p_{2}\cdot \cdot \cdot p_{n-1}}$ bedeutet:

${\displaystyle p_{n}=\lfloor {1-{\frac {1}{\ln 2}}\cdot \ln \left(-{\frac {1}{2}}+\sum _{d\mid P_{n-1}}{\frac {\mu (d)}{2^{d}-1}}\right)\rfloor }}$

Ob eine beliebige natürliche Zahl prim ist, kann mit einem Primzahltest herausgefunden werden. Es gibt mehrere solcher Verfahren, die sich auf besondere Eigenschaften von Primzahlen stützen. In der Praxis wird der Miller-Rabin-Test am häufigsten verwendet, der eine extrem kurze Laufzeit hat, allerdings mit kleiner Wahrscheinlichkeit falsch-positive Ergebnisse liefert. Mit dem AKS-Primzahltest ist es möglich, über die Primalität ohne Gefahr eines Irrtums in polynomieller Laufzeit zu entscheiden. Allerdings ist er in der Praxis deutlich langsamer als der Miller-Rabin-Test.

Herauszufinden, ob eine natürliche Zahl prim ist oder nicht, kann sehr aufwändig sein. Zu jeder Primzahl lässt sich aber eine Kette von Behauptungen angeben, die alle unmittelbar nachvollziehbar sind, zusammen die Primalität belegen und deren Gesamtlänge höchstens proportional ist zum Quadrat der Länge der Primzahl.^[10][11] Ein solcher Beleg wird Zertifikat (englisch primality certificate) genannt.^[12]

Bei der Zusammengesetztheit (Nichtprimalität) einer Zahl ist der Unterschied zwischen Beleg und Finden eines Belegs noch augenfälliger: Als Beleg genügen zwei Faktoren, deren Produkt die zusammengesetzte Zahl ergibt; das Finden eines echten Teilers kann aber sehr viel Aufwand bedeuten.

Der Grieche Euklid hat im vierten Jahrhundert vor Christus logisch gefolgert, dass es unendlich viele Primzahlen gibt; diese Aussage wird als Satz von Euklid bezeichnet. Euklid führte einen Widerspruchsbeweis für die Richtigkeit dieses Satzes (Elemente, Buch IX, § 20): Ausgehend von der Annahme, dass es nur endlich viele Primzahlen gibt, lässt sich eine weitere Zahl konstruieren, die eine bisher nicht bekannte Primzahl als Teiler hat oder selbst eine Primzahl ist, was einen Widerspruch zur Annahme darstellt. Somit kann eine endliche Menge niemals alle Primzahlen enthalten, also gibt es unendlich viele. Heute kennt man eine ganze Reihe von Beweisen für den Satz von Euklid.^[13]

Der Satz von Euklid besagt, dass es keine größte Primzahl gibt. Es ist jedoch kein Verfahren bekannt, das effizient beliebig große Primzahlen generiert – deshalb gab es stets eine jeweils größte bekannte Primzahl, seitdem sich die Menschen mit Primzahlen befassen. Derzeit (Stand: Dezember 2018) ist es ${\displaystyle 2^{82.589.933}-1,}$ eine Zahl mit 24.862.048 (dezimalen) Stellen, die am 7. Dezember 2018 berechnet wurde. Für den Entdecker Patrick Laroche gab es für den Fund 3.000 US-Dollar vom Projekt Great Internet Mersenne Prime Search, das Mersenne-Primzahlen mittels verteiltem Rechnen sucht.^[14]

Die größte bekannte Primzahl war fast immer eine Mersenne-Primzahl, also von der Form ${\displaystyle 2^{n}-1,}$ da in diesem Spezialfall der Lucas-Lehmer-Test angewendet werden kann, ein im Vergleich zur allgemeinen Situation sehr schneller Primzahltest. Bei der Suche nach großen Primzahlen werden deshalb nur Zahlen dieses oder eines ähnlich geeigneten Typs auf Primalität untersucht.

Zur Untersuchung der Verteilung der Primzahlen betrachtet man unter anderem die Funktion

${\displaystyle \pi \colon \mathbb {N} \to \mathbb {N} ,\;n\mapsto \pi (n)}$,

die die Anzahl der Primzahlen ${\displaystyle \leq n}$ angibt und auch Primzahlzählfunktion genannt wird. Zum Beispiel ist

${\displaystyle \pi (1)=0\ ;\ \pi (10)=4\ ;\ \pi (100)=25\ ;\ \pi (1000)=168;\ \pi (1000000)=78498}$.

Diese Funktion und ihr Wachstumsverhalten ist ein beliebter Forschungsgegenstand in der Zahlentheorie. Mit der Zeit wurden einige Näherungsformeln entwickelt und verbessert.

Der Primzahlsatz besagt, dass

${\displaystyle \pi (x)\sim {\frac {x}{\ln x}}}$

gilt, das heißt, dass der Quotient von linker und rechter Seite für ${\displaystyle x\to \infty }$ gegen 1 strebt:

${\displaystyle \lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\ln x}}}=1}$ (siehe Asymptotische Analyse)

Der Dirichletsche Primzahlsatz dagegen schränkt die Betrachtung auf Restklassen ein: Es sei ${\displaystyle m}$ eine natürliche Zahl. Ist ${\displaystyle a}$ eine ganze Zahl, die zu ${\displaystyle m}$ nicht teilerfremd ist, so kann die arithmetische Folge

${\displaystyle a,a+m,a+2m,a+3m,\dotsc }$

höchstens eine Primzahl enthalten, weil alle Folgenglieder durch den größten gemeinsamen Teiler von ${\displaystyle a}$ und ${\displaystyle m}$ teilbar sind. Ist ${\displaystyle a}$ aber teilerfremd zu ${\displaystyle m}$, so besagt der Dirichletsche Primzahlsatz, dass die Folge unendlich viele Primzahlen enthält. Beispielsweise gibt es unendlich viele Primzahlen der Form ${\displaystyle 4k+1}$ und unendlich viele der Form ${\displaystyle 4k+3}$ (${\displaystyle k}$ durchläuft jeweils die nichtnegativen natürlichen Zahlen).

Diese Aussage kann noch in der folgenden Form präzisiert werden. Es gilt:

${\displaystyle \lim _{x\to \infty }{\frac {\#\{p\ \mid \ \mathrm {prim} ,\ p\leq x\ \mathrm {und} \ p\equiv a{\pmod {m}}\}}{\#\{p\ \mid \ \mathrm {prim} ,\ p\leq x\}}}={\frac {1}{\varphi (m)}}}$

Dabei ist ${\displaystyle \varphi (m)}$ die Eulersche Phi-Funktion. In diesem Sinne liegen also für ein festes ${\displaystyle m}$ in den Restklassen ${\displaystyle a+m\mathbb {Z} }$ mit ${\displaystyle \mathrm {ggT} (a,m)=1}$ jeweils „gleich viele“ Primzahlen.

Die (bewiesene) Bonsesche Ungleichung garantiert, dass das Quadrat einer Primzahl kleiner ist als das Produkt aller kleineren Primzahlen (ab der fünften Primzahl).

Nach der (unbewiesenen) Andricaschen Vermutung ist die Differenz der Wurzeln der ${\displaystyle n}$-ten und der ${\displaystyle (n+1)}$-ten Primzahl kleiner als 1.

Im Folgenden sei die Folge der Primzahlen mit ${\displaystyle (p_{n})_{n\in \mathbb {N} }}$ bezeichnet.

Für Indizes ${\displaystyle n\in \mathbb {N} }$ gelten folgende Abschätzungen:

(1a)

${\displaystyle p_{n}<p_{n+1}<2\cdot p_{n}}$^[18][19]

(1b)

${\displaystyle {p_{n+1}}^{2}\leq 2\cdot {p_{n}}^{2}}$ für ${\displaystyle n\geq 5}$^{[20][21][A 2]}

(1c)

${\displaystyle p_{n}<2^{n}}$ für ${\displaystyle n\geq 2}$^[22]

(1d)

${\displaystyle p_{n}>n\cdot \ln(n)}$^[23]

(1e)

${\displaystyle \sum _{k=2}^{n}{\frac {1}{p_{k}}}>{\frac {1}{36}}\cdot {\ln {\ln(n+1)}}}$ für ${\displaystyle n\geq 2}$^[24][25]

Mit dem Primzahlsatz ergeben sich folgende Resultate:

(2a)

${\displaystyle \lim _{n\rightarrow \infty }{\frac {p_{n+1}}{p_{n}}}=1}$^[26]

(2b)

${\displaystyle {\frac {n}{\ln(n)-{\frac {1}{2}}}}<\pi (n)<{\frac {n}{\ln(n)-{\frac {3}{2}}}}}$ für ${\displaystyle n\geq 67}$^[27][28][29]

(2c)

Für jede positive reelle Zahl ${\displaystyle x}$ existiert eine Folge ${\displaystyle (q_{n})_{n\in \mathbb {N} }}$ von Primzahlen mit

${\displaystyle \lim _{n\rightarrow \infty }{\frac {q_{n}}{n}}=x}$.^[30][31]

(2d)

Die Menge der aus allen Primzahlen gebildeten Quotienten ist eine dichte Teilmenge der Menge aller positiven reellen Zahlen. D. h.: Für beliebige positive reelle Zahlen ${\displaystyle a,b}$ mit ${\displaystyle 0<a<b}$ existieren stets Primzahlen ${\displaystyle p,q}$, sodass

${\displaystyle a<{\frac {p}{q}}<b}$

erfüllt ist.^[32]

Die Differenz zwischen zwei benachbarten Primzahlen heißt Primzahllücke. Diese Differenz schwankt, und es gibt Primzahllücken beliebiger Größe. Es gibt aber auch Beschränkungen für die Lückengröße in Abhängigkeit von ihrer Lage.

• Der Satz von Bertrand sichert die Existenz einer Primzahl zwischen jeder natürlichen Zahl ${\displaystyle n}$ und ihrem Doppelten ${\displaystyle 2n}$.

• Nach der (unbewiesenen) Legendreschen Vermutung gibt es stets mindestens eine Primzahl zwischen ${\displaystyle n^{2}}$ und ${\displaystyle (n+1)^{2}}$.

Die Legendresche Vermutung stellt eine notwendige Bedingung für die nachfolgende (ebenfalls unbewiesene) Vermutung dar:

• Gegeben sei eine Primzahl ${\displaystyle p}$. Die natürlichen Zahlen ${\displaystyle 1}$ bis ${\displaystyle p^{2}}$ seien zeilenweise aufsteigend quadratisch angeordnet wie in der Abbildung für die ersten fünf Primzahlen ${\displaystyle p=2;3;5;7}$ und ${\displaystyle 11}$ dargestellt.

Dann gibt es zu jeder solchen quadratischen Anordnung eine Auswahl von ${\displaystyle p}$ Primzahlen, so dass sich in jeder Zeile und jeder Spalte genau eine Primzahl befindet.

Daraus, dass sich in der letzten Zeile einer jeden quadratischen Anordnung mindestens eine Primzahl befinden muss, lässt sich die Legendresche Vermutung folgern.^[33]

Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes. Bis heute ist kein effizienter Primzahlgenerator bekannt. Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen prim sind. Solche Zahlen müssen nachträglich noch auf ihre Primalität getestet werden.

Seit Beginn des 20. Jahrhunderts beschäftigten sich Experten mit der Frage, unter welchen Bedingungen Zahlen, deren Ziffern ausschließlich Einsen sind (sog. Repunit-Zahlen), Primzahlen sind.

1907 verfasste Henry Ernest Dudeney sein erstes Rätselbuch mit dem Titel The Canterbury Puzzles, in dem er behauptete, dass 11 die einzige Repunit-Primzahl sei. Er konnte zwar nachweisen, dass alle aus 3 bis 18 Ziffern bestehende Repunit-Zahlen keine Primzahlen sind, jedoch gelang ihm dies nicht für Repunit-Zahlen mit mehr als 18 Ziffern.

Nach der Lektüre von Dudeneys Buch bewies 1918 der New Yorker Oscar Hope, dass die 19-stellige Zahl 1.111.111.111.111.111.111 eine Primzahl ist. Später wurde auch die 23-stellige Repunit-Zahl als Primzahl nachgewiesen. Bis 1970 wurden bis zu 373-stellige Repunit-Zahlen untersucht, ohne jedoch eine vierte solche Primzahl zu finden.

Das Problem, ob es mehr als drei oder sogar unendlich viele Repunit-Primzahlen gibt, ist bis heute nicht gelöst.^[34][35]

Weitere spezielle Arten von Primzahlen finden sich in der Kategorie:Primzahl.

In der Ringtheorie wird das Konzept der Primzahl auf gewisse Elemente eines beliebigen kommutativen unitären Rings verallgemeinert. Die entsprechenden Begriffe sind Primelement und irreduzibles Element.

Die Primzahlen und deren Negative sind dann genau die Primelemente und auch genau die irreduziblen Elemente des Rings der ganzen Zahlen. In faktoriellen Ringen, das sind Ringe mit eindeutiger Primfaktorisierung, fallen die Begriffe Primelement und irreduzibles Element zusammen; im Allgemeinen ist die Menge der Primelemente jedoch nur eine Teilmenge der Menge der irreduziblen Elemente.

Insbesondere im zahlentheoretisch bedeutsamen Fall der Dedekindringe übernehmen Primideale die Rolle der Primzahlen.

Es gilt der Fundamentalsatz der Arithmetik: Jede ganze Zahl größer als 1 lässt sich als Produkt von Primzahlen darstellen, und diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Man nennt sie die Primfaktoren der Zahl.

Weil sich jede natürliche Zahl größer als 0 durch Multiplikation von Primzahlen darstellen lässt, nehmen die Primzahlen eine besondere atomare Stellung in der Mathematik ein, sie „erzeugen“ gewissermaßen alle anderen natürlichen Zahlen – die Eins als leeres Produkt. Alexander K. Dewdney bezeichnete sie als den Elementen der Chemie weitgehend ähnlich.

Daraus wird auch klar, warum es unzweckmäßig ist, die Eins als Primzahl zu definieren: Sie ist das neutrale Element der Multiplikation und kann somit multiplikativ keine weiteren Zahlen erzeugen. Sie wird für die Darstellung der Zahlen als Produkt von Primfaktoren nicht benötigt. Würde man die 1 zu den Primzahlen zählen, verlöre sich darüber hinaus die Eindeutigkeit der Primfaktorzerlegung, weil man an jede Zerlegung beliebig viele Einsen anhängen kann, ohne den Wert der Zahl zu ändern.

Man hat eine Reihe von Faktorisierungsverfahren entwickelt, um die Primfaktoren von allgemeinen Zahlen oder auch solchen von spezieller Form möglichst schnell zu bestimmen. Man kennt aber bisher keine Methode, um beliebige Zahlen effizient zu faktorisieren, d. h. in einer Zeit, die höchstens polynomiell mit der Länge der gegebenen Zahl wächst. Die Faktorisierungsannahme besagt, dass es eine solche Methode auch nicht gibt.

Manche Tier- und Pflanzenarten (z. B. bestimmte Zikaden oder Fichten) vermehren sich in Zyklen von Primzahlen (etwa alle 11, 13 oder 17 Jahre) besonders stark, um es Fressfeinden zu erschweren, sich auf das massenhafte Auftreten einzustellen.^[36][37]

Bei der Informationssicherheit und insbesondere bei der Verschlüsselung von Nachrichten (siehe Kryptographie) spielen Primzahlen eine wichtige Rolle. Sie werden oft in asymmetrischen Kryptosystemen wie etwa Public-Key-Verschlüsselungsverfahren eingesetzt. Wichtige Beispiele sind der Diffie-Hellman-Schlüsselaustausch, das RSA-Kryptosystem, das unter anderem bei OpenPGP zum Einsatz kommt, das Elgamal-Kryptosystem und das Rabin-Kryptosystem. Dabei werden die Schlüssel aus großen, zufällig erzeugten Primzahlen berechnet, die geheim bleiben müssen.

Solche Algorithmen basieren auf Einwegfunktionen, die schnell ausführbar sind, deren Umkehrung aber mit der aktuell bekannten Technologie praktisch unmöglich zu berechnen ist. Neue Informationstechnologien, zum Beispiel Quantencomputer, könnten das aber ändern. Das ungelöste P-NP-Problem steht damit in Zusammenhang.

Seit hunderten von Jahren diskutieren Mathematiker, ob die Zahl 1 als Primzahl anzusehen ist. Bei dieser Frage handelt es sich nicht um eine mathematische Aussage oder Feststellung, sondern um eine Definition. Definitionen werden intuitiv und/oder pragmatisch begründet; sie sind subjektiv, können aber hinsichtlich ihrer Nützlichkeit durchaus objektiv bewertet werden. Eine gute Definition ist an sich leicht und intuitiv verständlich (d. h. naheliegend) und macht auch die Formulierung von Theoremen leicht und intuitiv verständlich (d. h., sie ist nützlich).

Die Frage, ob 1 eine Primzahl ist, hängt also davon ab, was wir unter dem Begriff Primzahl intuitiv verstehen wollen und wie nützlich die Definition des Begriffs dann für die Formulierung von Theoremen ist.

Der bedeutende Mathematiker Godfrey Harold Hardy bezeichnete zum Beispiel noch im Jahr 1908 die Zahl 1 als Primzahl, aber spätestens im Jahr 1929 nicht mehr.^[38] Generell gilt seit dem 20. Jahrhundert unter den meisten Mathematikern die Übereinkunft, die Zahl 1 nicht zu den Primzahlen zu zählen.

Das Argument dafür, dass 1 in der Tat eine Primzahl sein sollte, ist:

• Gegeben, die Definition „Primzahlen sind nur durch sich selbst und 1 teilbar“ hat jede Primzahl hat höchstens zwei Teiler. Konkret einen einzigen Teiler für den Fall, dass die Zahl 1 ist, und zwei verschiedene Teiler für den Fall, dass es sich um eine andere Primzahl handelt.

Argumente dafür, dass 1 keine Primzahl sein sollte, sind:

• Jede Primzahl hat genau zwei Teiler (die Zahl 1 und sich selbst), wobei genau zwei konkret bedeutet, dass die Teiler unterschiedlich sind. Hieran erkennt man, dass das obige Dafür-Argument vielmehr eine unsaubere Wiedergabe dieser Idee entspricht.
• Ein Satz in der Mathematik ist die Eindeutigkeit der Primfaktorzerlegung. Wäre ${\displaystyle n=1}$ eine Primzahl, so hätte zum Beispiel die zusammengesetzte Zahl ${\displaystyle x=6}$ viele verschiedene Primfaktorzerlegungen, zum Beispiel ${\displaystyle x=6=2\cdot 3=1\cdot 2\cdot 3=1^{2}\cdot 2\cdot 3=\ldots =1^{657}\cdot 2\cdot 3=\ldots }$.

Damit hätte jede Zahl unendlich viele verschiedene Primfaktorzerlegungen und man müsste die Voraussetzungen für diesen Satz anders formulieren, damit die Eindeutigkeit wieder gegeben ist. Die Vieldeutigkeit ergibt sich speziell in diesem Zusammenhang daraus, dass die Zahl 1 das neutrale Element der Multiplikation ist, wodurch ihre Nutzung deswegen hierbei unsinnig wird.

• Das Produkt von zwei Primzahlen ist stets eine zusammengesetzte Zahl, also eine Zahl, die aus mindestens zwei Primfaktoren besteht. Wäre 1 eine Primzahl, könnte man sie zum Beispiel mit einer Primzahl multiplizieren und würde als Produkt wieder eine Primzahl und keine zusammengesetzte Zahl erhalten. Man müsste also die Definition der zusammengesetzten Zahl wesentlich umständlicher fassen.
• Das Sieb des Eratosthenes braucht eine Sonderbehandlung für 1, da man andernfalls als ersten Schritt alle Vielfachen von 1 streichen würde, womit keine einzige andere Zahl mehr übrig bleiben würde außer der 1.
• Für alle Primzahlen ${\displaystyle p}$ ist die Eulersche Phi-Funktion ${\displaystyle \varphi (p)=p-1}$. Für ${\displaystyle n=1}$ gilt aber ${\displaystyle \varphi (1)=1\neq 1-1=0}$. Der Satz müsste also umformuliert werden und 1 zur Ausnahme machen.
• Für alle Primzahlen ${\displaystyle p}$ gilt für die Teilerfunktion ${\displaystyle \sigma _{0}(p)=2}$. Für ${\displaystyle n=1}$ ist aber ${\displaystyle \sigma _{0}(1)=1\neq 2}$. Es gilt auch ${\displaystyle \sigma _{1}(p)=p+1}$. Für ${\displaystyle n=1}$ ist aber ${\displaystyle \sigma _{1}(1)=1\neq 1+1=2}$. Es wäre also die Zahl 1 auch für diese Funktion(en) eine große Ausnahme.
• Die Definition von Primelementen müsste man umformulieren, wenn 1 eine Primzahl wäre. Die neue Definition wäre komplizierter.
• Es gibt zu jeder Primpotenz einen endlichen Körper, der genau so viele Elemente hat. Wäre 1 eine Primzahl, dann müsste gemäß dieser Aussage der Nullring als Körper aufgefasst werden.
• Die vielfältigen Besonderheiten, die dem Nullring zu eigen sind (z. B. dass er keine echte algebraische Erweiterung zulässt), sind leichter zu würdigen, indem man ihm die Sonderrolle unter den Ringen, die er wirklich einnimmt, auch zuspricht, den Begriff des „Nullkörpers“ nicht bildet und von einem Körper fordert, dass er mindestens zwei Elemente hat, m. a. W., dass sich die neutralen Elemente der beiden Ringoperationen Addition und Multiplikation unterscheiden.

Die Beispiele zeigen, dass man auf jeden Fall für die (so definierten) Primzahlen und die 1 verschiedene Begriffe braucht, und nun – warum soll man nicht diese Primzahlen unter dem Begriff „Primzahl“ verstehen und für die 1 einen anderen Begriff, nämlich den der „Einheit“ einführen, um nachher die Zahlenmenge auch besser erweitern zu können, bspw. auf die der ganzen Zahlen, wo sich eine weitere Zahl als Einheit herausstellt, nämlich die −1?

• Fastprimzahlen
• Frobeniushomomorphismus
• Gilbreaths Vermutung
• Illegale Primzahl
• Permutierbare Primzahl
• Primzahltupel
• Primzahlzwillinge
• Relativ prim
• Ulam-Spirale

1. ↑ ${\displaystyle \lfloor \cdot \rfloor }$ ist die Gaußklammer.
2. ↑ Diese Beziehung wird mit ${\displaystyle \leq }$ statt ${\displaystyle <}$ angegeben, obwohl die Gleichung ${\displaystyle \,{p_{n+1}}^{2}=2\cdot {p_{n}}^{2}\,}$ wegen ${\displaystyle 2\nmid p_{n+1}}$ nie erfüllbar ist.

• Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
• Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. Beck, München 2004, ISBN 3-406-52320-X.
• Władysław Narkiewicz: The Development of Prime Number Theory. From Euclid to Hardy and Littlewood. Springer, Berlin 2000, ISBN 3-540-66289-8.
• Paulo Ribenboim: The New Book of Prime Number Records. Springer, New York 1996, ISBN 0-387-94457-5.
• Robert E. Dressler, Louis Pigno, Robert Young: Sums of squares of primes. In: Nordisk Mat. Tidskr. Band 24, 1976, S. 39–40 (MR0419352). 
• Hans Rademacher, Otto Toeplitz: Von Zahlen und Figuren. Proben mathematischen Denkens für Liebhaber der Mathematik (= Heidelberger Taschenbücher. Band 50). Springer Verlag, Berlin (u. a.) 1968 (MR0252141). 
• J. B. Rosser: The n-th prime is greater than n log n. In: Proc. London Math. Soc. Band 45, 1939, S. 21–44. 
• J. Barkley Rosser, L. Schoenfeld: Approximate formulas for some functions of prime numbers. In: Illinois J. Math. Band 6, 1962, S. 64–94 (projecteuclid.org [PDF]).  MR0137689
• József Sándor, Dragoslav S. Mitrinović, Borislav Crstici: Handbook of Number Theory. 2. Auflage. Band I. Springer-Verlag, Dordrecht (NL) 2006, ISBN 1-4020-4215-9 (MR2186914). 
• Wacław Sierpiński: Elementary Theory of Numbers. Edited and with a preface by Andrzej Schinzel (= North-Holland Mathematical Library. Band 31). 2. überarbeitete und erweiterte Auflage. North-Holland (u. a.), Amsterdam (u. a.) 1988, ISBN 0-444-86662-0 (MR0930670). 
• Rebecca Waldecker, Lasse Rempe-Gillen: Primzahltests für Einsteiger: Zahlentheorie–Algorithmik–Kryptographie. 2. Auflage. Springer Spektrum, Wiesbaden 2016, ISBN 978-3-658-11216-5, doi:10.1007/978-3-658-11217-2. 

Commons: Primzahlen – Sammlung von Bildern, Videos und Audiodateien

Wiktionary: Primzahl – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Wikibooks: Fundamentalsatz der Arithmetik – Lern- und Lehrmaterialien

Wikibooks: Primzahlen von 2 bis 100.000 – Lern- und Lehrmaterialien

• The Prime Pages (englisch)
• Die Primzahlenseite
• Eric W. Weisstein: Rosser’s Theorem. In: MathWorld (englisch).
• Gesammelte Sätze und interessante Eigenschaften über Primzahlen. (PDF; 162 Seiten) Mathematik alpha (deutsch).

1. ↑ Karl Ernst Georges: prior. In: Ausführliches lateinisch-deutsches Handwörterbuch. 8., verbesserte und vermehrte Auflage. Band 2. Hahnsche Buchhandlung, Hannover 1918, Sp. 1925–1927 (Digitalisat. zeno.org). 
2. ↑ Christlieb von Clausberg: Demonstrative Rechenkunst, oder Wissenschaft gründlich und kurz zu rechnen. Worinnen sowol gemeine als andere Kaufmännische Rechnungsarten, Proben und Wechsel-Arbitragen auf besondere kurze Manier gründlich gelehret werden, und eine Beschreibung Europäischer Münzen, Wechselarten und Usanzen, eine Vergleichung der Gewichte und Ellenmaße, die wahre Berechnung des Interusurii, eine neue Logarithmische Tabelle, auch mehr andere Mathematische und curiose Rechnungen beygefüget sind. Bernhard Christoph Breitkopf und Sohn, Leipzig 1762, S. 86 (eingeschränkte Vorschau in der Google-Buchsuche). 
3. ↑ Armin Leutbecher: Zahlentheorie: Eine Einführung in die Algebra. Springer, 1996, ISBN 3-540-58791-8, S. 18, eingeschränkte Vorschau in der Google-Buchsuche.
4. ↑ Martin Erickson: Mathematische Appetithäppchen – Faszinierende Bilder. Packende Formeln. Reizvolle Sätze. Aus dem Englischen übersetzt von Roland Girgensohn. Springer Spektrum, Springer-Verlag, Berlin / Heidelberg 2015, ISBN 978-3-662-45458-9, S. 8. Übersetzung der amerikanischen Ausgabe: Martin Erickson: Beautiful Mathematics. Mathematical Association of America, 2011.
5. ↑ Don Zagier: Lösungen von Gleichungen in ganzen Zahlen. (PDF; 0,6 MB) S. 311–326, 1984.
6. ↑ Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, New York 1996, S. 182 ff.
7. ↑ Wacław Sierpiński: Sur une formule donnant tous les nombres premiers. C. R. Acad. Sci. Paris, Band 235, 1952, S. 1078–1079.
8. ↑ C. P. Willans: On formulae for the nth prime number. Math. Gaz., Band 48, 1964, S. 413–415.
9. ↑ J. M. Gandhi: Formulae for the nth prime. In: Proceedings of the Washington State University Conference on Number Theory. Washington State University, Department of Mathematics, Pi Mu Epsilon, Pullman, WA, 1971, S. 96–106.
10. ↑ Vaughan R. Pratt: Every Prime has a Succinct Certificate. (PDF; 0,6 MB).
11. ↑ Vašek Chvátal: Lecture notes on Pratt’s Primality Proofs. (PDF; 0,1 MB).
12. ↑ Der Satz von Vaughan Pratt als Theorem des Tages. (PDF; 0,3 MB).
13. ↑ Für Beweise des Satzes von Euklid siehe Beweisarchiv.
14. ↑ Mersenne Prime Number discovery – 2^82589933−1 is Prime! Abgerufen am 21. Dezember 2018 (englisch). 
15. ↑ List of known Mersenne prime numbers – PrimeNet. Abgerufen am 1. November 2019. 
16. ↑ primes.utm.edu
17. ↑ Daniel AJ Sokolov: Computer in Florida findet neue größte Primzahl. In: Heise.de. 22. Dezember 2018, abgerufen am 22. Dezember 2018. 
18. ↑ Rademacher-Toeplitz: S. 164.
19. ↑ Sierpiński: S. 146.
20. ↑ Dressler-Pigno-Young: Nordisk Mat. Tidskr. Band 24, S. 39. 
21. ↑ Sándor-Mitrinović-Crstici: S. 247.
22. ↑ Sierpiński: S. 145.
23. ↑ Die Abschätzung (1d) wurde zuerst von John Barkley Rosser gefunden (s. Rosser in: Proc. London Math. Soc., Band 45, S. 21 ff. / Sierpiński, S. 163 / Sándor-Mitrinović-Crstici, S. 247).
24. ↑ Sierpiński: S. 162.
25. ↑ Aus (1e) ergibt sich, wie Sierpiński anmerkt, unmittelbar die Divergenz der Reihe ${\displaystyle \textstyle \sum _{k=1}^{\infty }{\frac {1}{p_{k}}}}$.
26. ↑ Sierpiński: S. 163.
27. ↑ Rosser-Schoenfeld: Illinois J. Math. Band 6, S. 64 ff. 
28. ↑ Sierpiński: S. 163.
29. ↑ Wie Sierpiński anmerkt, gelangt man mit (2b) unmittelbar zum Primzahlsatz.
30. ↑ Sierpiński: S. 165.
31. ↑ Dieses Ergebnis wurde gemäß Sierpiński zuerst von dem polnischen Mathematiker Hugo Steinhaus gewonnen.
32. ↑ Sierpiński: S. 165.
33. ↑ Martin Erickson: Mathematische Appetithäppchen – Faszinierende Bilder. Packende Formeln. Reizvolle Sätze. Aus dem Englischen übersetzt von Roland Girgensohn. Springer Spektrum, Springer-Verlag, Berlin / Heidelberg 2015, ISBN 978-3-662-45458-9, S. 7. Übersetzung der amerikanischen Ausgabe: Martin Erickson: Beautiful Mathematics. Mathematical Association of America, 2011.
34. ↑ Martin Gardner: Mathematisches Labyrinth Friedrich Vieweg & Sohn, Braunschweig/Wiesbaden 1979, ISBN 978-3-528-08402-8, Seiten 86/87.
35. ↑ Henry Ernest Dudeney: The Canterbury Puzzles and other curious problems. New York: E. P. Dutton 1908 (Nachdruck bei Dover).
36. ↑ Klaus Schmeh: Was Zikaden mit Primzahlen zu tun haben. In: heise online. Abgerufen am 9. März 2020. 
37. ↑ Im Zikadenleben zählen Zahlen. (PDF) Max-Planck-Gesellschaft, 29. April 2002, archiviert vom Original (nicht mehr online verfügbar) am 1. Oktober 2007; abgerufen am 9. März 2020. 
38. ↑ Chris K. Caldwell, Angela Reddick, Yeng Xiong: The History of the Primality of One: A Selection of Sources. In: Journal of Integer Sequences. 2012, S. 1–40 (uwaterloo.ca [PDF; abgerufen am 10. Februar 2020] Article 12.9.8).