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 , dann ist die Zahl 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 sie und alle ihre Vielfachen aus der Liste. Die kleinste Zahl der Restliste, die 3, ist die nächste Primzahl. Man entfernt sie und alle ihre Vielfachen aus der Liste usw.
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. Wie kommt man also ausgerechnet auf diese Zahl?
In der Antike und bis ins Mittelalter glaubte man, daß für jede Primzahl p die Zahl wieder eine Primzahl ist. Dabei ist klar, daß für eine zusammengesetzte Zahl k=mn wegen
keine Primzahl sein kann. So wurde etwa 1456 von einem unbekannten Mathematiker die Primzahleigenschaft von
Im Jahre 1644 behauptete nun der französische Mönch Marin Mersenne im Vorwort seiner Cogitata Physica-Mathematica, daß für alle Primzahlen bis 257 nur die Fälle
eine Primzahl
Wenn man etwa die Größe der Primzahl (1876 von Lucas bewiesen)
bedenkt, so dürfte klar sein, daß
Mersenne zu seiner Zeit
unmöglich für alle Primzahlen p bis 257 die Primzahleigenschaft von
Satz: Für eine ungerade Primzahl p ist
Dabei sind die Lucas-Zahlen rekursiv durch
In der folgenden Tabelle sind in fortlaufender Numerierung die Mersenneschen
Primzahlen
Für die letzten vier Einträge ist zur Zeit noch unbekannt, ob zwischen ihnen nicht noch weitere Mersenneschen Primzahlen liegen. Es läuft ein über das Internet verbreiteter Test der Primzahlen p in den verbleibenden Lücken, an dem sich jeder Interessierte mit entsprechender Computerkapazität beteiligen kann. Eine Anlaufadresse ist
http://www.utm.edu/research/primes/mersenne.shtml
Nr. | p | Dezimalstellen von | Entdeckungsjahr | Entdecker |
1 | 2 | 1 | - | - |
2 | 3 | 1 | - | - |
3 | 5 | 2 | - | - |
4 | 7 | 3 | - | - |
5 | 13 | 4 | 1456 | unbekannt |
6 | 17 | 6 | 1588 | Cataldi |
7 | 19 | 6 | 1588 | Cataldi |
8 | 31 | 10 | 1772 | Euler |
9 | 61 | 19 | 1883 | Pervushin |
10 | 89 | 27 | 1911 | Powers |
11 | 107 | 33 | 1914 | Powers |
12 | 127 | 39 | 1876 | Lucas |
13 | 521 | 157 | 1952 | Lehmer & Robinson |
14 | 607 | 183 | 1952 | Lehmer & Robinson |
15 | 1279 | 386 | 1952 | Lehmer & Robinson |
16 | 2203 | 664 | 1952 | Lehmer & Robinson |
17 | 2281 | 687 | 1952 | Lehmer & Robinson |
18 | 3217 | 969 | 1957 | Riesel |
19 | 4253 | 1281 | 1961 | Hurwitz & Selfridge |
20 | 4423 | 1332 | 1961 | Hurwitz & Selfridge |
21 | 9689 | 2917 | 1963 | Gillies |
22 | 9941 | 2993 | 1963 | Gillies |
23 | 11213 | 3376 | 1963 | Gillies |
24 | 19937 | 6002 | 1971 | Tuckerman |
25 | 21701 | 6533 | 1978 | Noll & Nickel |
26 | 23209 | 6987 | 1979 | Noll |
27 | 44497 | 13395 | 1979 | Nelson & Slowinski |
28 | 86243 | 25962 | 1982 | Slowinski |
29 | 110503 | 33265 | 1988 | Colquitt & Welsh |
30 | 132049 | 39751 | 1983 | Slowinski |
31 | 216091 | 65050 | 1985 | Slowinski |
32 | 756839 | 227832 | 1992 | Slowinski & Gage |
? | 859433 | 258716 | 1994 | Slowinski & Gage |
? | 1257787 | 378632 | 1996 | Slowinski & Gage |
? | 1398269 | 420921 | 1996 | Armengaud et al. |