Primzahlen

Bekanntlich ist eine Primzahl eine von 1 verschiedene natürliche Zahl, die keine Teiler außer 1 und sich selbst hat. Schon in der Antike wußten griechische Mathematiker, daß sich jede natürliche Zahl eindeutig (bis auf die Reihenfolge der Faktoren) in ein Produkt von Primzahlen zerlegen läßt und daß es unendlich viele verschiedene Primzahlen gibt. Im Buch IX der Elemente des Euklid (um 300 v. Chr.) findet sich nämlich der folgende Widerspruchsbeweis: Nimmt man an, daß es nur endlich viele Primzahlen gibt, also etwa $p$₁, p₂, ... p_n, dann ist die Zahl $m=p$₁*p₂* ... *p_n+1 größer als alle diese Primzahlen und wird von keiner Primzahl geteilt. Also ist m selbst eine Primzahl, ein Widerspruch zur Annahme.

Mit Hilfe des Siebverfahrens des Eratosthenes (um 200 v. Chr.) kann man im Prinzip folgendermaßen nach und nach jede Primzahl finden. Man beginnt mit der unendlich langen Liste aller natürlichen Zahlen größer als 1. In ihr ist die kleinste Zahl, die 2, eine Primzahl. Man entfernt alle ihre Vielfachen aus der Liste. Die kleinste Zahl der Restliste, die größer ist als die soeben gefundene Primzahl, also in diesem Fall die 3, ist die nächste Primzahl. Man entfernt nun alle ihre Vielfachen aus der Liste usw.

Die Jagd nach großen Primzahlen

Natürlich ist dieses theoretische Verfahren nicht praktikabel, um schnell eine beliebig lange Liste von Primzahlen zu erzeugen. Es ist bis heute auch keine Formel bekannt, die es gestattet, schnell beliebig große Primzahlen zu berechnen, oder aus einer gegebenen Primzahl eine noch größere Primzahl herzustellen.

Daher gibt es beim aktuellen Stand der Forschung immer eine zur Zeit größte bekannte Primzahl und der augenblickliche Rekord steht bei

Es ist nun keineswegs so, daß man alle Primzahl unterhalb dieser sehr großen Zahl kennt, wie das beim Siebverfahren des Eratosthenes der Fall wäre. Mit Hilfe der Mersenne-Zahlen läßt sich eine solche Zahl bestimmen. So ist diese Zahl selbst auch eine Mersenne- Zahl.

• Primzahlzwillinge, bei denen es sich um zwei Primzahlen handelt, welche die Differenz zwei haben.
  Konkrete Beispiele sind 5 und 7, 11 und 13, 17 und 19, 29 und 31, 41 und 43,..., wobei das größte bekannte Primzahlzwillingspaar 33218925*2^169690+/-1 ist.
  Bis heute ist jedoch unbekannt, ob es unendlich viele Primzahlzwillinge gibt.

• Primzahldrillinge, die immer drei Primzahlen enthalten, bei denen es jeweils eine Differenz von zwei gibt. Da jede dritte ungerade Zahl durch drei teilbar ist, gibt es nur einen einzigen Drilling (3, 5 und 7).

• Primzahlvierlinge, die durch jeweils zwei Primzahlzwillinge, die nur vier Zahlen auseinanderliegen, charakterisiert sind. Beispiele wären: 11;13;17;19 oder 101;103;107;109

Bei der Primfaktorzerlegung gilt der Fundamentalsatz der Arithmetik. Dieser besagt, daß sich jede positive ganze Zahl bis auf die Reihenfolge eindeutig als Produkt von Primzahlen darstellen läßt. Die in dieser Darstellung auftretenden Primzahlen nennt man die Primfaktoren der Zahl. Die Schwierigkeiten bei der Primfaktorzerlegung bezeichnet man als Faktorisierungsprobleme. Doch man versucht sie mit geeigneten Faktorisierungsverfahren zu minimieren. Da sich jede natürliche Zahl als Produkt von Primzahlen schreiben läßt, nehmen die Primzahlen eine besondere Stellung in der Zahlentheorie ein. Sie nehmen daher eine ähnliche Stellung wie die Atome in der Chemie ein.

Die Sophie-Germain-Primzahlen sind eine ganze Klasse von Primzahlen, die für bestimmte zahlentheoretische Untersuchungen eine große Rolle gespielt haben. Eine weitere interessante Klasse von Primzahlen, die eng mit der Konstruierbarkeit regelmäßiger $n$-Ecke allein mittels Zirkel und Lineal verbunden sind, stellen die Fermatschen Primzahlen dar.