mini|Natürliche Zahlen von 0 bis 100, die Primzahlen sind rot markiert, die zusammengesetzten Zahlen grün
Eine Primzahl (von ) 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 selbst. Dabei bedeutet speziell „Anfang, das Erste (der Dinge)“, sodass eine „Anfangszahl“ gemeint ist, die aus keiner anderen natürlichen Zahl multiplikativ konstruiert werden kann.
Grundlagen Die Menge der Primzahlen wird in der Regel mit dem Symbol bezeichnet. Man weiß durch den Satz des Euklid seit der Antike, dass es unendlich viele Primzahlen gibt. Mit verknüpft ist die Folge der nach ihrer Größe geordneten Primzahlen, die man auch Primzahlfolge nennt.
Die Primzahlen lassen sich unter anderem mit Hilfe der Teileranzahlfunktion definieren:
Es ist demnach
mit
mini|Die Zahl 12 ist keine Primzahl, da sich 12 Objekte in Form eines Rechtecks anordnen lassen. Die Zahl 11 hingegen ist Primzahl, da dies nicht möglich ist. Dargestellt sind fehlgeschlagene Versuche, bei denen jeweils etwas übrig bleibt.
Die Bedeutung der Primzahlen für viele Bereiche der Mathematik beruht auf direkten Folgerungen aus ihrer Definition. Vor allem ist hier der Fundamentalsatz der Arithmetik zu nennen, der die Existenz und Eindeutigkeit der Primfaktorzerlegung einer natürlichen Zahl sichert. Denn danach lässt sich jede natürliche Zahl, die größer als 1 und selbst keine Primzahl ist, auf genau eine Art und Weise – von der Reihenfolge der Faktoren abgesehen – als Produkt von mindestens zwei Primzahlen schreiben.
Der Beweis des Fundamentalsatzes beruht auf dem Lemma von Euklid: Eine Primzahl, die ein Produkt zweier natürlicher Zahlen teilt, ist schon Teiler von mindestens einer dieser beiden Zahlen. Dies bedeutet insbesondere, dass Primzahlen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen lassen.
Die genannten Eigenschaften werden in der Algebra für Verallgemeinerungen des Primzahlbegriffs genutzt.
Eine Zahl, die das Produkt von zwei oder mehr Primfaktoren ist, nennt man zusammengesetzte Zahl. Die Zahlen 0 und 1 sind 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 spielen wegen ihrer Eigenschaften in der modernen Kryptographie eine bedeutende Rolle. Denn trotz der Verfügbarkeit leistungsstarker elektronischer Rechenanlagen können große natürliche Zahlen auch weiterhin nicht effizient in Primfaktoren zerlegt werden. Dies wird für sichere Verschlüsselungsverfahren genutzt.
Eigenschaften von Primzahlen Die Primzahlen sind innerhalb der Menge der natürlichen Zahlen dadurch charakterisiert, dass jede von ihnen genau zwei natürliche Zahlen als Teiler hat, nämlich 1 und die Zahl selbst.Armin Leutbecher: Zahlentheorie: Eine Einführung in die Algebra. Springer, 1996, ISBN 3-540-58791-8, S. 18, .
Mit Ausnahme der Zahl 2 sind alle Primzahlen ungerade, denn alle größeren geraden Zahlen lassen sich auch noch (mindestens) durch 2 teilen. Damit hat jede Primzahl außer 2 die Form mit einer natürlichen Zahl .
Jede Primzahl lässt sich einer der beiden Klassen „Primzahl der Form “ oder „Primzahl der Form “ zuordnen, wobei eine natürliche Zahl ist. Von den ersten Primzahlen haben die Form und die Form . Setzt man die Primzahlfolge fort, so nähern sich die Anteile beider Formen dem Wert .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.
Jede Primzahl lässt sich zudem einer der beiden Klassen „Primzahl der Form “ oder „Primzahl der Form “ zuordnen, wobei eine natürliche Zahl ist.
Darüber hinaus hat jede Primzahl die Form oder , wobei eine natürliche Zahl ist. Ferner endet jede Primzahl auf eine der vier Dezimalziffern oder . Nach dem Dirichletschen Primzahlsatz gibt es in jeder dieser Klassen unendlich viele Primzahlen.
Jede natürliche Zahl der Form mit einer nichtnegativen ganzen Zahl enthält mindestens einen Primfaktor der Form . Eine entsprechende Aussage über Zahlen der Form oder Primfaktoren der Form ist nicht möglich.
Eine Primzahl lässt sich genau dann in der Form mit ganzen Zahlen schreiben, wenn die Form hat (Zwei-Quadrate-Satz). In diesem Fall ist die Darstellung im Wesentlichen eindeutig, d. h. bis auf Reihenfolge und Vorzeichen von . Diese Darstellung entspricht der Primfaktorzerlegung
im Ring der ganzen Gaußschen Zahlen.
Die Zahl ist quadratischer Rest modulo jeder Primzahl der Form und quadratischer Nichtrest modulo jeder Primzahl der Form .
Eine Primzahl lässt sich genau dann in der Form mit ganzen Zahlen schreiben, wenn die Form hat.Don Zagier: Lösungen von Gleichungen in ganzen Zahlen. (PDF; 600 kB) mpim-bonn.mpg.de, 1984, S. 311–326. In diesem Fall ist die Darstellung im Wesentlichen eindeutig.
Ist eine Zahl durch keine Primzahl teilbar, so ist eine Primzahl. Gäbe es nämlich einen Primteiler von mit , so wäre eine natürliche Zahl mit und hätte als solche auch (mindestens) einen Primteiler mit , den man bis dahin gefunden haben müsste (siehe Abschnitt Primzahltests und Artikel Probedivision).
Der kleine Satz von Fermat
Es sei eine Primzahl. Für jede ganze Zahl , die nicht durch teilbar ist, gilt (für die Notation siehe Kongruenz):
Für nicht durch teilbare Zahlen ist die folgende Formulierung äquivalent:
Es gibt Zahlen , die keine Primzahlen sind, sich aber dennoch zu einer Basis wie Primzahlen verhalten, d. h., es ist . Solche nennt man Fermatsche Pseudoprimzahlen zur Basis . Ein , das Fermatsche Pseudoprimzahl bezüglich aller zu ihm teilerfremden Basen 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.
Euler und das Legendre-Symbol Eine einfache Folge aus dem kleinen Satz von Fermat ist: Für jede ungerade Primzahl und jede ganze Zahl , die nicht durch teilbar ist, gilt entweder oder
Der erste Fall tritt genau dann ein, wenn es eine Quadratzahl gibt, die kongruent zu modulo ist, siehe Legendre-Symbol.
Binomialkoeffizient Eine Primzahl ist für jede ganze Zahl mit stets ein Teiler des Binomialkoeffizienten . Zusammen mit dem binomischen Satz folgt daraus
Für ganze Zahlen 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 in Ringen der Charakteristik ein Homomorphismus ist, der sogenannte Frobenius-Homomorphismus.
Aus dem Satz von Wilson ( ist genau dann eine Primzahl, wenn ist) folgt, dass für jede Primzahl und jede natürliche Zahl die Kongruenz
erfüllt ist.
Charles Babbage (1791–1871) bewies 1819, dass für jede Primzahl diese Kongruenz gilt:
Der Mathematiker Joseph Wolstenholme (1829–1891) bewies dann 1862, dass für jede Primzahl die folgende Kongruenz gilt:
Giuga Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl gilt:
Beispiel :
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 Dezimalziffern haben müsste. Im Zusammenhang mit Giugas Vermutung werden die Giuga-Zahlen untersucht.
Lineare Rekursionen Den kleinen Fermatschen Satz kann man auch in der Form lesen: In der Folge ist für eine Primzahl das -te Folgenglied stets durch teilbar. Ähnliche Eigenschaften besitzen auch andere Folgen von exponentiellem Charakter, wie die Lucas-Folge () und die Perrin-Folge (). Für andere lineare Rekursionen gelten analoge, aber kompliziertere Aussagen, beispielsweise für die Fibonacci-Folge : Ist eine Primzahl, so ist durch teilbar. Dabei ist
das Legendre-Symbol.
Divergenz der Summe der Kehrwerte
Die Reihe der Kehrwerte der Primzahlen ist bestimmt divergent. Somit gilt:
Das ist gleichbedeutend mit der Aussage, dass die durch definierte Folge keinen endlichen Grenzwert besitzt, was wiederum bedeutet, dass jede reelle Zahl übertreffen kann, indem man 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.
Primzahlformeln 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.Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, New York 1996, S. 182 ff. Dazu zählen nicht zuletzt eine Formel von Wacław Sierpiński aus dem Jahre 1952,Wacław Sierpiński: Sur une formule donnant tous les nombres premiers. Band 235. Comptes rendus de l’Académie des sciences, Paris 1952, S. 1078–1079. eine Formel von C. P. Willans aus dem Jahre 1964C. P. Willans: On formulae for the nth prime number. Math. Gaz., Band 48, 1964, S. 413–415. und eine Formel von J. M. Gandhi aus dem Jahre 1971.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.
Formel von Sierpiński Die für jede natürliche Zahl gültige Sierpiński’sche Formel geht von der konvergenten Reihe
aus. Damit erhält man: ist die Gaußklammer.
Formel von Willans Die für natürlichzahliges gültige Formel von Willans zeigt, wie man die Primzahlen aus der Primzahlfunktion zurückgewinnen kann. Es gilt nämlich:
Formel von Gandhi Die für alle natürlichen Zahlen gültige Gandhi’sche Formel zeigt, wie man die Primzahlen mit Hilfe der Möbiusfunktion und dem natürlichen Logarithmus darstellen kann. Hier gilt nämlich, wenn bedeutet:
Primzahltests
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.
Primzahlzertifikat