Primzahl

Definition und grundlegende Bedeutung

Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei verschiedene natürliche Teiler besitzt: 1 und sich selbst. Die Menge der Primzahlen wird meist mit ℙ bezeichnet; die geordnete Primzahlfolge (pₙ) beginnt mit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … Mit der Teileranzahlfunktion d(n) lautet die Definition ℙ = {n ∈ ℕ | d(n) = 2}. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt. Jede weitere natürliche Zahl ist entweder eine Primzahl oder eine zusammengesetzte Zahl, also ein Produkt von mindestens zwei Primfaktoren.

Nach dem Satz des Euklid gibt es unendlich viele Primzahlen. Der Fundamentalsatz der Arithmetik erklärt ihre zentrale Bedeutung: Jede ganze Zahl größer als 1 lässt sich als Produkt von Primzahlen darstellen, und diese Primfaktorzerlegung ist bis auf die Reihenfolge der Faktoren eindeutig. Grundlage dafür ist das Lemma von Euklid: Teilt eine Primzahl ein Produkt zweier natürlicher Zahlen, so teilt sie mindestens einen der beiden Faktoren.

Beispielsweise ist 11 prim, während 12 zusammengesetzt ist. Für 12 gilt etwa 12 = 2² · 3. Primzahlen wirken damit wie multiplikative Grundbausteine der natürlichen Zahlen.

Mehrere leicht verständliche Fragen sind weiterhin ungelöst. Nach der Goldbachschen Vermutung lässt sich jede gerade Zahl außer 2 als Summe zweier Primzahlen schreiben. Ebenfalls unbewiesen ist, dass es unendlich viele Primzahlzwillinge gibt, also Primzahlpaare mit der Differenz 2.

Eigenschaften und wichtige Sätze

2 ist die einzige gerade Primzahl. Jede Primzahl p > 2 ist ungerade und hat die Form 2k + 1. Für p > 3 gilt sogar p = 6k + 1 oder p = 6k − 1. Jede Primzahl p > 5 endet im Dezimalsystem auf 1, 3, 7 oder 9. Diese Formen sind notwendige, aber keine hinreichenden Bedingungen: Nicht jede Zahl dieser Formen ist prim.

Primzahlen außer 2 gehören entweder zur Form 4k + 1 oder 4k + 3; langfristig nähern sich die Anteile beider Klassen 0,5. Der Dirichletsche Primzahlsatz besagt allgemeiner, dass jede arithmetische Folge a, a + m, a + 2m, … unendlich viele Primzahlen enthält, wenn a und m teilerfremd sind. Daher gibt es unendlich viele Primzahlen sowohl der Form 4k + 1 als auch der Form 4k + 3.

Der Zwei-Quadrate-Satz lautet: Eine Primzahl p > 2 kann genau dann als a² + b² mit ganzen Zahlen a und b geschrieben werden, wenn p = 4k + 1 ist. Die Darstellung ist bis auf Reihenfolge und Vorzeichen im Wesentlichen eindeutig. Entsprechend lässt sich eine Primzahl p > 3 genau dann als a² + 3b² darstellen, wenn p = 3k + 1 ist.

Ein elementares Prüfmerkmal lautet: Ist n > 1 durch keine Primzahl p mit 1 < p ≤ √n teilbar, dann ist n prim. Bei einer zusammengesetzten Zahl müsste nämlich mindestens ein Primfaktor höchstens √n sein.

Der kleine Satz von Fermat besagt für eine Primzahl p und eine nicht durch p teilbare ganze Zahl a: a^(p−1) ≡ 1 mod p. Äquivalent gilt a^p ≡ a mod p. Zusammengesetzte Zahlen, die diese Bedingung für eine bestimmte Basis erfüllen, heißen Fermatsche Pseudoprimzahlen; erfüllen sie sie für alle teilerfremden Basen, heißen sie Carmichael-Zahlen. Deshalb beweist ein bestandener Fermat-Test allein die Primalität nicht.

Für eine ungerade Primzahl p gilt a^((p−1)/2) ≡ +1 oder −1 mod p. Der Wert +1 tritt genau dann auf, wenn a modulo p ein quadratischer Rest ist. Außerdem teilt p jeden Binomialkoeffizienten (p über k) für 1 ≤ k ≤ p−1; daraus folgt (a+b)^p ≡ a^p+b^p mod p. Der Satz von Wilson charakterisiert Primzahlen durch (p−1)! ≡ −1 mod p.

Die Summe der Kehrwerte aller Primzahlen divergiert: 1/2 + 1/3 + 1/5 + 1/7 + … = ∞. Obwohl die durchschnittlichen Abstände zwischen Primzahlen wachsen, kann diese Summe also jede vorgegebene reelle Zahl überschreiten.

Verteilung, Wachstum und offene Vermutungen

Die Primzahlzählfunktion π(n) gibt die Anzahl der Primzahlen ≤ n an. Beispiele sind π(1)=0, π(10)=4, π(100)=25, π(1000)=168 und π(10⁶)=78.498. Der Primzahlsatz beschreibt ihr langfristiges Wachstum:

π(x) ∼ x/ln x,

also lim(x→∞) π(x)/(x/ln x) = 1. Primzahlen werden somit mit zunehmender Größe seltener, verschwinden aber nie. Für die n-te Primzahl gilt insbesondere lim(n→∞) pₙ₊₁/pₙ = 1. Für n ≥ 67 gilt außerdem n/(ln n−1/2) < π(n) < n/(ln n−3/2).

In den zu einem festen m teilerfremden Restklassen sind die Primzahlen asymptotisch gleichmäßig verteilt: Der jeweilige Anteil nähert sich 1/φ(m), wobei φ die Eulersche Phi-Funktion ist. Die Quotienten p/q aus Primzahlen liegen dicht in den positiven reellen Zahlen; zwischen beliebigen 0 < a < b existieren also Primzahlen p und q mit a < p/q < b.

Die Differenz benachbarter Primzahlen heißt Primzahllücke. Ihre Größe schwankt, und es gibt beliebig große Primzahllücken. Der Satz von Bertrand garantiert zugleich, dass zwischen jeder natürlichen Zahl n und 2n eine Primzahl liegt.

Mehrere stärkere Aussagen sind unbewiesen. Nach der Andricaschen Vermutung ist die Differenz der Quadratwurzeln zweier aufeinanderfolgender Primzahlen kleiner als 1. Die Legendresche Vermutung behauptet, dass zwischen n² und (n+1)² stets mindestens eine Primzahl liegt. Eine weitere im Artikel beschriebene Vermutung über p × p-Zahlenquadrate würde die Legendresche Vermutung nach sich ziehen.

Bestimmung, Erzeugung und Rekorde

Das Sieb des Eratosthenes ist einer der ältesten Algorithmen zur Bestimmung aller Primzahlen bis zu einer Grenze. Für eine einzelne Zahl verwendet man Primzahltests. In der Praxis kommt häufig der sehr schnelle Miller-Rabin-Test zum Einsatz; er kann allerdings mit kleiner Wahrscheinlichkeit ein falsch-positives Ergebnis liefern. Der AKS-Primzahltest entscheidet die Primalität ohne Irrtumsgefahr in polynomieller Laufzeit, ist praktisch aber deutlich langsamer.

Ein Primzahlzertifikat ist eine Kette leicht überprüfbarer Aussagen, die gemeinsam beweist, dass eine Zahl prim ist. Seine Gesamtlänge ist höchstens proportional zum Quadrat der Stellenlänge der Primzahl. Bei einer zusammengesetzten Zahl reichen zwei Faktoren als Beleg; diese Faktoren zu finden kann jedoch sehr schwierig sein. Für beliebige Zahlen ist kein effizientes Faktorisierungsverfahren bekannt.

Ein effizienter Generator für beliebig große Primzahlen ist ebenfalls nicht bekannt. Manche Formeln erzeugen Zahlen, die mit einer gewissen Wahrscheinlichkeit prim sind; anschließend ist ein Primzahltest nötig. Daneben existieren exakte, aber nicht unbedingt praktisch effiziente Primzahlformeln: die Formel von Sierpiński von 1952, die Formel von C. P. Willans von 1964 und die Formel von J. M. Gandhi von 1971. Sie stellen pₙ unter anderem mithilfe einer speziell konstruierten Konstanten, der Primzahlzählfunktion π beziehungsweise der Möbiusfunktion μ dar.

Es gibt keine größte Primzahl, wohl aber jeweils eine größte bekannte. Am 12. Oktober 2024 fand Luke Durant die Primzahl 2^136.279.841 − 1 mit 41.024.320 Dezimalstellen. Sie übertraf 2^82.589.933 − 1 mit 24.862.048 Stellen, die Patrick Laroche am 7. Dezember 2018 berechnet hatte. Rekordzahlen sind meist Mersenne-Primzahlen der Form 2^p − 1, weil sich für sie der besonders schnelle Lucas-Lehmer-Test verwenden lässt. Das Projekt Great Internet Mersenne Prime Search nutzt dafür verteiltes Rechnen.

Besondere Rekorde betreffen unter anderem Primzahlpalindrome und Primzahlen mit eingeschränkten Ziffern. Repunit-Zahlen bestehen ausschließlich aus Einsen. Nachgewiesene Repunit-Primzahlen sind unter anderem die Zahlen mit 2, 19 und 23 Einsen; bis 1970 fand man unter den untersuchten Repunit-Zahlen mit bis zu 373 Stellen keine vierte. Ob es mehr als drei oder sogar unendlich viele Repunit-Primzahlen gibt, ist ungeklärt.

Anwendungen und Verallgemeinerungen

In der Kryptographie werden große Primzahlen besonders in asymmetrischen Verfahren eingesetzt. Beispiele sind der Diffie-Hellman-Schlüsselaustausch, RSA, Elgamal und Rabin; RSA kommt unter anderem bei OpenPGP zum Einsatz. Die Schlüssel werden aus großen, zufällig erzeugten Primzahlen berechnet, die geheim bleiben müssen.

Die Sicherheit beruht auf Einwegfunktionen: Die Vorwärtsrechnung ist schnell, die bekannte Umkehrung praktisch sehr aufwändig. Insbesondere können große Zahlen derzeit nicht effizient in ihre Primfaktoren zerlegt werden. Würde versehentlich eine zusammengesetzte Zahl statt einer benötigten Primzahl verwendet, könnte die Sicherheit verloren gehen. Neue Technologien wie Quantencomputer könnten die Lage verändern; auch das ungelöste P-NP-Problem steht damit in Zusammenhang.

In der Natur treten bei manchen Zikaden und Fichten starke Vermehrungszyklen von 11, 13 oder 17 Jahren auf. Solche Primzahlzyklen erschweren es Fressfeinden, ihr eigenes Auftreten mit diesen Zyklen abzustimmen.

Die Algebra verallgemeinert den Primzahlbegriff auf kommutative Ringe mit Einselement. Dort unterscheidet man Primelemente und irreduzible Elemente. In den ganzen Zahlen sind genau die positiven und negativen Primzahlen sowohl prim als auch irreduzibel. In faktoriellen Ringen fallen beide Begriffe zusammen; allgemein bilden die Primelemente nur eine Teilmenge der irreduziblen Elemente. In Dedekindringen übernehmen Primideale die Rolle der Primzahlen.

Warum 1 keine Primzahl ist

Seit dem 20. Jahrhundert gilt allgemein die Definition, dass eine Primzahl genau zwei verschiedene Teiler haben muss. Daher ist 1 keine Primzahl: Sie hat nur einen Teiler, nämlich sich selbst. Diese Festlegung ist besonders nützlich, weil sie zahlreiche mathematische Sätze ohne Sonderfälle formulieren lässt.

Das wichtigste Argument ist die Eindeutigkeit der Primfaktorzerlegung. Würde 1 als Primzahl gelten, hätte etwa 6 unendlich viele Darstellungen: 6 = 2·3 = 1·2·3 = 1²·2·3 = …, weil beliebig viele Faktoren 1 eingefügt werden könnten. Die Zahl 1 ist das neutrale Element der Multiplikation und wird deshalb als Einheit, nicht als Primzahl behandelt.

Weitere Regeln würden andernfalls Ausnahmen benötigen: Das Produkt zweier Primzahlen soll zusammengesetzt sein; beim Sieb des Eratosthenes würden sonst zunächst alle Vielfachen von 1 gestrichen. Für Primzahlen gilt φ(p)=p−1, aber φ(1)=1 und nicht 0. Ebenso gilt für die Teilerfunktionen σ₀(p)=2 und σ₁(p)=p+1, während σ₀(1)=σ₁(1)=1. Auch Definitionen von Primelementen und Aussagen über endliche Körper wären komplizierter. Die heutige Abgrenzung behandelt daher Primzahlen und multiplikative Einheiten als verschiedene Begriffe.