Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei positive Teiler hat: 1 und sich selbst. Formal ist eine Zahl p > 1 genau dann prim, wenn es keine Zahlen m und n mit 1 < i> < m < i> < p bzw. 1 < i> < n < i> < p gibt, so dass p = m × n. Anders ausgedrückt: eine Primzahl lässt sich nicht als Produkt zweier kleinerer natürlicher Zahlen darstellen. Die kleinste Primzahl ist 2 (die einzige gerade Primzahl). Die nächsten Primzahlen sind 3, 5, 7, 11 und 13. Die Zahl 1 ist per Konvention weder prim noch zusammengesetzt; die kleinste zusammengesetzte Zahl ist 4 = 2 × 2. Es gibt unendlich viele Primzahlen.

Wesentliche Eigenschaften

  • Primfaktorzerlegung / Fundamentalsatz der Arithmetik: Jede natürliche Zahl größer als 1 lässt sich eindeutig (bis auf die Reihenfolge) als Produkt von Primzahlen schreiben. Diese Zerlegung nennt man Primfaktorzerlegung.
  • Einzigartigkeit und Konstruktion: Primzahlen sind die „Bausteine“ der ganzen Zahlen; zusammengesetzte Zahlen entstehen durch Multiplikation von Primfaktoren.
  • Gerade und ungerade Primzahlen: 2 ist die einzige gerade Primzahl; alle anderen Primzahlen sind ungerade und enden in 1, 3, 7 oder 9 (in Basis 10), aber das ist keine hinreichende Bedingung für Primalität.
  • Unendlichkeit der Primzahlen: Es gibt keine größte Primzahl. Ein klassischer Beweis (Euklid) geht so: nehme endlich viele Primzahlen p1,...,pn und betrachte N = p1·p2·...·pn + 1. N ist durch keine der pi teilbar, also muss N entweder prim sein oder weitere Primteiler besitzen, also können die Primzahlen nicht endlich sein.
  • Spezielle Klassen: Dazu gehören Mersenne-Primzahlen (Form 2^p − 1), Fermat-Zahlen, Sophie-Germain-Primzahlen, sichere Primzahlen u. a.

Verteilung der Primzahlen

Die Frage, wie Primzahlen unter den natürlichen Zahlen verteilt sind, ist zentral in der Zahlentheorie. Das Primzahlentheorem gibt eine asymptotische Beschreibung: die Zahl der Primzahlen ≤ x, genannt π(x), verhält sich für große x wie x / log(x). Genauer gilt π(x) ~ x / ln(x). Trotzdem bleiben viele feine Fragen offen: etwa wie regelmäßig Lücken zwischen aufeinanderfolgenden Primzahlen auftreten, wie oft Primzahlschwestern (twin primes) vorkommen, oder wie Primzahlen in arithmetischen Progressionen verteilt sind. Die Riemannsche Vermutung verbindet die Verteilung der Nullstellen der Riemannschen Zetafunktion mit sehr genauen Aussagen über Abweichungen von x / ln(x).

Prüfverfahren und Suche nach Primzahlen

  • Einfaches Verfahren: Trialdivision (Probieren durch alle möglichen Teiler bis √n) ist für kleine Zahlen praktikabel.
  • Siebverfahren: Das Sieb des Eratosthenes und seine Verbesserungen erzeugen effizient alle Primzahlen bis zu einer oberen Schranke.
  • Probabilistische Tests: Miller–Rabin und ähnliche Tests liefern sehr schnell mit hoher Wahrscheinlichkeit die Primalität (oder Kompositheit) für große Zahlen; sie sind in der Praxis weit verbreitet.
  • Deterministische Tests: Der AKS-Algorithmus ist ein deterministischer Polynomzeit-Test für Primalität. Für spezielle Formen (z. B. Mersenne-Zahlen) gibt es sehr effiziente deterministische Tests wie den Lucas–Lehmer-Test.
  • Suche nach großen Primzahlen: Die größten bekannten Primzahlen sind oft Mersenne-Primzahlen und werden mit verteilten Rechnersystemen (z. B. GIMPS) gefunden. Solche Entdeckungen benötigen spezialisierte Tests und viel Rechenzeit.

Offene Probleme und klassische Vermutungen

Die Zahlentheorie enthält viele ungelöste Fragen über Primzahlen. Zu den bekanntesten zählen die Goldbachsche Vermutung (jede gerade Zahl > 2 ist Summe zweier Primzahlen) und die Zwillingsprimvermutung (es gibt unendlich viele Primzahlpaare p, p+2). Auch die Feinstruktur der Primverteilung, etwa genaue Abschätzungen für Lücken zwischen Primzahlen, ist Gegenstand intensiver Forschung.

Anwendungen

Primzahlen sind nicht nur theoretisch wichtig, sie haben auch praktische Anwendungen, besonders in der Kryptographie. Public-Key-Verfahren wie RSA beruhen auf der Schwierigkeit, große Zahlen in ihre Primfaktoren zu zerlegen, während das Erkennen von Primalität vergleichsweise einfacher ist. Weiterhin werden Primzahlen in Hashverfahren, Zufallszahlengeneratoren und in Algorithmen zur Kodierung und Fehlerkorrektur verwendet.

Zusammenfassung

Primzahlen sind fundamentale Bausteine der ganzen Zahlen mit einfacher Definition, aber überraschend komplexen Eigenschaften. Sie treten unregelmäßig auf, ihre Verteilung ist nur asymptotisch gut beschrieben, und viele tiefe Fragen (etwa Goldbach, Zwillingsprimzahlen, Verbindungen zur Riemannschen Vermutung) sind nach wie vor offen. Gleichzeitig sind Primzahlen praktisch relevant, vor allem in der modernen Kryptographie.