Mersenne-Zahl

Eine Mersenne-Zahl ist eine Zahl der Form ${\displaystyle 2^{n}-1}$. Im Speziellen bezeichnet man mit ${\displaystyle M_{n}=2^{n}-1}$ die ${\displaystyle n}$-te Mersenne-Zahl. Die ersten sieben Mersenne-Zahlen ${\displaystyle M_{n}}$ sind

${\displaystyle 1,3,7,15,31,63,127}$ (Folge A000225 in OEIS).

Die Primzahlen unter den Mersenne-Zahlen werden Mersenne-Primzahlen genannt. Die ersten acht Mersenne-Primzahlen ${\displaystyle M_{p}}$ sind

${\displaystyle 3,7,31,127,8191,131071,524287,2147483647}$ (Folge A000668 in OEIS)

für die Exponenten ${\displaystyle p=2,3,5,7,13,17,19,31}$ (Folge A000043 in OEIS).

Bei der Darstellung im Dualsystem zeigen sich Mersennezahlen als Einserkolonnen, d. h. Zahlen, die ausschließlich aus Einsen bestehen. Die ${\displaystyle n}$-te Mersennezahl ist im Dualsystem eine Zahl mit ${\displaystyle n}$ Einsen (Beispiel: ${\displaystyle M_{3}=7=111_{2}}$). Mersenne-Zahlen zählen im Binären zu den Zahlenpalindromen, Mersenne-Primzahlen dementsprechend zu den Primzahlpalindromen.

Ihren Namen haben diese Primzahlen von dem französischen Mönch und Priester Marin Mersenne (1588–1648), der im Vorwort seiner Cogitata Physico-Mathematica^[1] behauptete, dass für ${\displaystyle p=2,3,5,7,13,17,19,31,67,127}$ und ${\displaystyle 257}$ die Zahl ${\displaystyle M_{p}}$ eine Primzahl sei.

Er irrte sich jedoch bei den Zahlen ${\displaystyle M_{67}}$ und ${\displaystyle M_{257}}$ und übersah die Mersenne-Primzahlen ${\displaystyle M_{61}}$, ${\displaystyle M_{89}}$ und ${\displaystyle M_{107}}$. Dass ${\displaystyle M_{67}}$ keine Primzahl ist, hat Édouard Lucas 1876 gezeigt, aber erst im Jahre 1903 konnte der Mathematiker Frank Nelson Cole die Primfaktoren dieser Zahl benennen. Um den Nachweis zu führen, dass ${\displaystyle M_{257}}$ keine Primzahl ist, wurde 1932 eine frühe Rechenmaschine verwendet. Bei der Zahl ${\displaystyle M_{67}}$ handelt es sich möglicherweise um einen Lesefehler seitens Mersenne aus seiner Korrespondenz mit Bernard Frénicle de Bessy und Pierre de Fermat, wobei er ${\displaystyle p=61}$ mit ${\displaystyle p=67}$ verwechselte.

Mersenne-Zahlen kommen auch beim Mersenne-Twister vor, einem Pseudozufallszahlengenerator.

Mersenne-Zahlen wurden zuerst in der Antike im Zusammenhang mit vollkommenen Zahlen untersucht. Eine natürliche Zahl wird vollkommen genannt, wenn sie gleich der Summe ihrer echten Teiler ist (Beispiel: ${\displaystyle 6=1+2+3}$). Schon Euklid hatte gezeigt, dass die Zahl ${\displaystyle 2^{n-1}(2^{n}-1)}$ vollkommen ist, wenn ${\displaystyle 2^{n}-1}$ eine Primzahl ist (${\displaystyle n=2}$ liefert die Zahl ${\displaystyle 6}$). 2000 Jahre später wurde von Euler die Umkehrung für gerade vollkommene Zahlen gezeigt: Jede gerade vollkommene Zahl ist von der Form ${\displaystyle 2^{n-1}(2^{n}-1)}$, wobei ${\displaystyle 2^{n}-1}$ eine Primzahl ist.^[2]

Ungerade vollkommene Zahlen sind bisher nicht gefunden worden, allerdings konnte ihre Existenz bis heute weder bewiesen noch widerlegt werden.

Die ersten vier vollkommenen Zahlen ${\displaystyle 6,28,496}$ und ${\displaystyle 8128}$ waren schon in der Antike bekannt. Die Suche nach weiteren vollkommenen Zahlen motivierte die Suche nach weiteren Mersenne-Primzahlen. Denn die vollkommenen Zahlen sind exakt die Dreieckszahlen aus den Mersenne-Primzahlen. Die wichtigste dabei zu beachtende Eigenschaft ist die folgende:

Ist ${\displaystyle n}$ eine zusammengesetzte Zahl, so ist auch ${\displaystyle M_{n}}$ eine zusammengesetzte Zahl. Dass ${\displaystyle 2^{a\cdot b}-1}$ von ${\displaystyle 2^{a}-1}$ und von ${\displaystyle 2^{b}-1}$ ohne Rest geteilt wird, kann mit Hilfe einer Polynomdivision gezeigt werden, falls ${\displaystyle a}$ und ${\displaystyle b}$ natürliche Zahlen ohne die Null sind.

Daraus folgt unmittelbar, dass der Exponent ${\displaystyle p}$ einer Mersenne-Primzahl ${\displaystyle M_{p}=2^{p}-1}$ selbst eine Primzahl ist. Durch diese Eigenschaft wird die Suche nach Mersenne-Primzahlen erleichtert, da nur noch Mersenne-Zahlen mit Primzahlexponent betrachtet werden müssen.

Der Umkehrschluss, dass ${\displaystyle M_{p}}$ prim ist, wenn ${\displaystyle {p}}$ prim ist, ist jedoch falsch, da beispielsweise ${\displaystyle M_{11}=2047=23\cdot 89}$ keine Primzahl ist.

Mersenne-Primzahlen sind selten: Bislang (Stand Oktober 2024) sind erst 52 davon gefunden worden. Da es einen besonders effizienten Primzahltest für sie gibt, sind die größten bekannten Primzahlen Mersenne-Primzahlen.

Im Lauf ihrer langen Geschichte sind viele Ergebnisse über Mersenne-Zahlen gefunden worden. Außer der schon erwähnten grundlegenden Teilbarkeitseigenschaft (teilt ${\displaystyle r}$ die Zahl ${\displaystyle n}$, so ist ${\displaystyle M_{r}}$ Teiler von ${\displaystyle M_{n}}$) gibt es z. B. folgende Ergebnisse:

• Ist ${\displaystyle n}$ eine gerade Zahl und ${\displaystyle n+1}$ prim, so ist ${\displaystyle n+1}$ ein Teiler von ${\displaystyle M_{n}}$, z. B. ${\displaystyle M_{10}=1023=3\cdot 11\cdot 31,M_{12}=4095=3^{2}\cdot 5\cdot 7\cdot 13}$.

• Ist ${\displaystyle n}$ eine ungerade Primzahl und ${\displaystyle q}$ ein Primfaktor von M_n, so gilt ${\displaystyle q\equiv 1{\bmod {\ }}2n}$ und ${\displaystyle q\equiv \pm 1\ {\bmod {\ }}8}$. Beispiel: ${\displaystyle M_{11}=2047=23\cdot 89}$ und ${\displaystyle 23=2\cdot 11+1}$, ${\displaystyle 89=4\cdot 2\cdot 11+1}$.

• Wenn ${\displaystyle p}$ eine Primzahl mit ${\displaystyle p\equiv 3\ mod\ 4}$ ist, dann gilt die folgende Äquivalenz: ${\displaystyle 2p+1}$ teilt die Mersenne-Zahl ${\displaystyle M_{p}}$ genau dann, wenn ${\displaystyle 2p+1}$ prim ist. Beispiel: ${\displaystyle 11}$ ist prim und lässt einen Rest von ${\displaystyle 3}$ bei Division durch ${\displaystyle 4}$. Da ${\displaystyle 23}$ (als Ergebnis von ${\displaystyle 2\cdot 11+1}$) prim ist, folgt: ${\displaystyle 23}$ teilt die Mersenne-Zahl ${\displaystyle M_{11}=2047}$. Diese Aussage wurde von Leonhard Euler formuliert, aber erst später von Joseph-Louis Lagrange bewiesen (siehe auch Sophie-Germain-Primzahl).

• Ist ${\displaystyle M_{p}>3}$ eine Primzahl, dann ist ${\displaystyle M_{p}+2}$ keine Primzahl (nämlich durch ${\displaystyle 3}$ teilbar). Mersenne-Primzahlen eignen sich also nicht als die kleinere Primzahl eines Primzahlzwillings.

• Ist ${\displaystyle n=2^{m}}$ mit ${\displaystyle m>0}$, so ist ${\displaystyle M_{n}}$ das Produkt der Fermat-Zahlen ${\displaystyle F_{0}}$ bis ${\displaystyle F_{m-1}}$. Beispiel: ${\displaystyle M_{16}=F_{0}\cdot F_{1}\cdot F_{2}\cdot F_{3}=3\cdot 5\cdot 17\cdot 257}$.

Für die Erzielung von Primzahl-Rekorden eignen sich Mersenne-Primzahlen in mehrfacher Hinsicht besonders gut, weil (a) zusammengesetzte Exponenten unberücksichtigt bleiben können, weil diese keine Primzahlen generieren, und deshalb eine Liste der Kandidaten für den Exponent ${\displaystyle p}$ leicht mit Primzahlgeneratoren erstellt werden kann^[19] (b) durch den funktionalen Zusammenhang die Größenordnung der Primzahl exponentiell – nämlich zur Basis zwei – mit dem Argument ${\displaystyle p}$ anwächst, man also schnell sehr große Zahlen erhält, (c) mit dem nachfolgend beschriebenen Lucas-Lehmer-Test ein einfacher und effektiver Primzahltest zur Verfügung steht.

Seit 1992 ist die größte bekannte Primzahl daher immer eine Mersenne-Primzahl gewesen.

Dieser Test ist ein speziell auf Mersenne-Zahlen zugeschnittener Primzahltest, der auf Arbeiten von Édouard Lucas aus der Zeit 1870–1876 beruht und im Jahr 1930 von Derrick Henry Lehmer ergänzt wurde.

Er funktioniert wie folgt:

Sei ${\displaystyle p}$ ungerade und prim. Die Folge ${\displaystyle (S_{k})_{k\in \mathbb {N} }}$ sei rekursiv definiert durch ${\displaystyle S_{1}=4}$ und ${\displaystyle S_{k+1}=S_{k}^{2}-2}$.

Dann gilt: ${\displaystyle M_{p}=2^{p}-1}$ ist genau dann eine Primzahl, wenn ${\displaystyle S_{p-1}}$ durch ${\displaystyle M_{p}}$ teilbar ist.

Im Oktober 2024 waren 52 Mersenne-Primzahlen bekannt. Mit massivem Computereinsatz wird nach weiteren Mersenne-Primzahlen gesucht. Da es sich um sehr große Zahlen handelt, sind die Berechnungen aufwendig: Die 51. Mersenne-Primzahl hat mehr als 24 Millionen Ziffern^[20] im Dezimalsystem. Die Berechnung erfolgt durch Langzahlarithmetik.

GIMPS (engl.: Great Internet Mersenne Prime Search) versucht, weltweit möglichst viele Computer an den Berechnungen zu beteiligen. Die dafür nötige Software (Prime95) wurde von George Woltman und Scott Kurowski erstellt und ist für mehrere Computer-Plattformen (Windows, Linux …) verfügbar.

Mit Stand 21. Oktober 2024 ist nicht ausgeschlossen, dass es zwischen p = 57.885.161 und p = 136.279.841 noch weitere, bisher unentdeckte Mersenne-Primzahlen gibt; deshalb ist die Nummerierung ab Nr. 49 noch ungewiss (und mit einem „?“ versehen).

Wie so oft in der Zahlentheorie gibt es auch zu Mersenne-Zahlen ungelöste Probleme, die sehr einfach zu formulieren sind:

• Gibt es unendlich viele Mersenne-Primzahlen? Man vermutet aufgrund plausibler Heuristiken, dass es etwa ${\displaystyle c\cdot \ln(x)}$ viele Mersenne-Primzahlen ${\displaystyle M_{p}}$ gibt mit ${\displaystyle p<x}$ (für eine positive Konstante ${\displaystyle c}$). Sollte das zutreffen, so gäbe es tatsächlich unendlich viele Mersenne-Primzahlen.

• Genauer: Ist die Vermutung, die H. W. Lenstra und C. Pomerance unabhängig voneinander aufstellten, richtig, dass es asymptotisch ${\displaystyle e^{\gamma }\log _{2}(\log _{2}(x))+O(1)}$ viele Mersenne-Primzahlen gibt, die kleiner oder gleich ${\displaystyle x}$ sind?^[22]
• Umgekehrt: Gibt es unendlich viele Mersenne-Zahlen ${\displaystyle M_{p}}$ mit ${\displaystyle p}$ prim, die keine Primzahlen sind? Auch hier vermutet man als Antwort ja. Dies würde zum Beispiel aus der Vermutung folgen, dass es unendlich viele Sophie-Germain-Primzahlen gibt, die kongruent 3 modulo 4 sind.
• Sind alle Mersenne-Zahlen ${\displaystyle M_{p}}$ mit ${\displaystyle p}$ prim quadratfrei, d. h., kommt in der Primfaktorzerlegung der Zahl jeder Primfaktor genau einmal vor? Man konnte bisher noch nicht einmal beweisen, dass dies für unendlich viele Mersenne-Zahlen gilt.
• Gilt die „neue Mersenne-Vermutung“? Die Folge von Mersenne-Primzahlen, die Mersenne angab, lässt vermuten, dass er meinte, dass eine Mersenne-Zahl ${\displaystyle M_{p}}$ mit ${\displaystyle p}$ prim genau dann prim ist, wenn ${\displaystyle p=2^{k}\pm 1}$ oder ${\displaystyle p=4^{k}\pm 3}$. Da diese Aussage nicht gilt, stellten P. Bateman, J. Selfridge und S. Wagstaff die neue Mersenne-Vermutung auf.

  Diese besagt, dass aus zwei der folgenden drei Aussagen bereits die dritte folgt:

  1. ${\displaystyle n=2^{k}\pm 1}$ oder ${\displaystyle n=4^{k}\pm 3}$,
  2. ${\displaystyle 2^{n}-1}$ ist eine (Mersenne-)Primzahl,
  3. ${\displaystyle (2^{n}+1)/3}$ ist eine Primzahl (man nennt sie Wagstaff-Primzahl).

• Sind alle Glieder der Folge ${\displaystyle C(0)=2}$, ${\displaystyle C(k+1)=2^{C(k)}-1}$ Primzahlen? Die stärkere Vermutung, dass alle Zahlen ${\displaystyle M_{M_{p}}}$ Primzahlen sind, für die ${\displaystyle M_{p}}$ eine Primzahl ist, konnte 1957 durch Raphael Robinson widerlegt werden. (Z. B. ist ${\displaystyle M_{M_{13}}=M_{8191}}$ nicht prim.) Diese letzteren Zahlen nennt man doppelte Mersenne-Zahlen (OEIS, A077585). Bisher sind doppelte Mersenne-Primzahlen nur für ${\displaystyle p=2,3,5,7}$ bekannt (OEIS, A077586); für ${\displaystyle p=13,17,19}$ und ${\displaystyle 31}$ wurden kleine Faktoren gefunden.^[23] Ob es weitere oder sogar unendlich viele doppelte Mersenne-Primzahlen gibt, bleibt unbekannt.

Eine Mersenne–Fermat-Zahl hat die Form ${\displaystyle MF(p,r)={\tfrac {2^{p^{r}}-1}{2^{p^{r-1}}-1}}}$, wobei ${\displaystyle p\in \mathbb {P} }$ eine Primzahl und ${\displaystyle r\in \mathbb {N} }$ eine natürliche Zahl ist. Ist die Mersenne–Fermat-Zahl eine Primzahl, so nennt man sie Mersenne–Fermat-Primzahl.

• Sei ${\displaystyle r=1}$.

  Dann erhält man Mersenne–Fermat-Zahlen der Form ${\displaystyle MF(p,1)={\frac {2^{p^{1}}-1}{2^{p^{1-1}}-1}}={\frac {2^{p}-1}{2^{p^{0}}-1}}={\frac {2^{p}-1}{2^{1}-1}}={\frac {2^{p}-1}{1}}=2^{p}-1}$. Diese Zahlen sind die Mersenne-Zahlen ${\displaystyle M_{p}}$.

• Sei ${\displaystyle p=2}$.

  Dann erhält man Mersenne–Fermat-Zahlen der Form ${\displaystyle MF(2,r)={\frac {2^{2^{r}}-1}{2^{2^{r-1}}-1}}={\frac {(2^{2^{r-1}}-1)\cdot (2^{2^{r-1}}+1)}{2^{2^{r-1}}-1}}=2^{2^{r-1}}+1}$. Diese Zahlen sind die Fermat-Zahlen ${\displaystyle F_{r-1}}$.

• Die einzigen momentan bekannten Mersenne–Fermat-Primzahlen mit ${\displaystyle r>1}$ sind die folgenden acht:^[24]

  ${\displaystyle {\begin{array}{lclclclcl}MF(2,2)&=&\displaystyle {\frac {2^{2^{2}}-1}{2^{2^{1}}-1}}&=&\displaystyle {\frac {2^{4}-1}{2^{2}-1}}&=&\displaystyle {\frac {15}{3}}&=&5\\MF(2,3)&=&\displaystyle {\frac {2^{2^{3}}-1}{2^{2^{2}}-1}}&=&\displaystyle {\frac {2^{8}-1}{2^{4}-1}}&=&\displaystyle {\frac {255}{15}}&=&17\\MF(2,4)&=&\displaystyle {\frac {2^{2^{4}}-1}{2^{2^{3}}-1}}&=&\displaystyle {\frac {2^{16}-1}{2^{8}-1}}&=&\displaystyle {\frac {65535}{255}}&=&257\\MF(2,5)&=&\displaystyle {\frac {2^{2^{5}}-1}{2^{2^{4}}-1}}&=&\displaystyle {\frac {2^{32}-1}{2^{16}-1}}&=&\displaystyle {\frac {4294967295}{65535}}&=&65537\\MF(3,2)&=&\displaystyle {\frac {2^{3^{2}}-1}{2^{3^{1}}-1}}&=&\displaystyle {\frac {2^{9}-1}{2^{3}-1}}&=&\displaystyle {\frac {511}{7}}&=&73\\MF(3,3)&=&\displaystyle {\frac {2^{3^{3}}-1}{2^{3^{2}}-1}}&=&\displaystyle {\frac {2^{27}-1}{2^{9}-1}}&=&\displaystyle {\frac {134217727}{511}}&=&262657\\MF(7,2)&=&\displaystyle {\frac {2^{7^{2}}-1}{2^{7^{1}}-1}}&=&\displaystyle {\frac {2^{49}-1}{2^{7}-1}}&=&\displaystyle {\frac {562949953421311}{127}}&=&4432676798593\\MF(59,2)&=&\displaystyle {\frac {2^{59^{2}}-1}{2^{59^{1}}-1}}&=&\displaystyle {\frac {2^{3481}-1}{2^{59}-1}}\end{array}}}$

  Die momentan größte bekannte Mersenne–Fermat-Primzahl ${\displaystyle MF(59,2)={\frac {2^{3481}-1}{2^{59}-1}}}$ hat 1031 Stellen.

• Es gelten folgende Eigenschaften:^[24]
  • ${\displaystyle MF(p,r)=\Phi _{p^{r}}(2)}$, wobei ${\displaystyle \Phi _{p^{r}}}$ das ${\displaystyle p^{r}}$-te Kreisteilungspolynom ist.
  • Je zwei verschiedene Mersenne–Fermat-Primzahlen sind paarweise zueinander prim. Das heißt

    ${\displaystyle ggT(MF(p,r),MF(p,s))=1}$ für ${\displaystyle r\not =s}$

    ${\displaystyle ggT(MF(p,r),MF(q,s))=1}$ für ${\displaystyle p\not =q}$

Sei ${\displaystyle f(x):=x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{1}x+a_{0}}$ ein Polynom, bei dem der höchste Exponent ${\displaystyle n}$ niedrig sein soll (der sogenannte Grad des Polynoms). Auch die ganzzahligen Koeffizienten ${\displaystyle a_{0},a_{1},a_{2},\ldots ,a_{n-1}}$ sollen nicht allzu hoch sein. Dann ist ${\displaystyle f(2^{m})}$ eine verallgemeinerte Mersenne-Zahl. Ist sie prim, so heißt sie verallgemeinerte Mersenne-Primzahl.^[25]

Mit anderen Worten: Eine verallgemeinerte Mersenne-Zahl hat die Form^[26]

${\displaystyle 2^{k}+a_{n-1}2^{k-1}+\dotsb +a_{1}2^{1}+a_{0}}$.

• Seien ${\displaystyle f(x)=x-1}$ ein Polynom 1. Grades und ${\displaystyle m=5}$.

  Dann ist ${\displaystyle f(2^{m})=2^{m}-1}$ und somit gilt:

  ${\displaystyle f(2^{5})=2^{5}-1=32-1=31}$

  Diese Zahl ${\displaystyle f(2^{5})=2^{5}-1=31}$ ist eine Primzahl und somit eine verallgemeinerte Mersenne-Primzahl. Mit diesem Polynom ${\displaystyle f(x)=x-1}$ erhält man alle Mersenne-Primzahlen.

• Seien ${\displaystyle f(x)=x+1}$ ein Polynom 1. Grades und ${\displaystyle m=3}$.

  Dann ist ${\displaystyle f(2^{m})=2^{m}+1}$ und somit gilt:

  ${\displaystyle f(2^{3})=2^{3}+1=8+1=9}$

  Diese Zahl ${\displaystyle f(2^{3})=9=3\cdot 3}$ ist keine Primzahl und somit zwar eine verallgemeinerte Mersenne-Zahl, aber keine verallgemeinerte Mersenne-Primzahl. Mit diesem Polynom ${\displaystyle f(x)=x+1}$ erhält man unter anderem alle Fermat-Zahlen.

• Seien ${\displaystyle f(x)=x^{2}+5x+1}$ ein Polynom 2. Grades und ${\displaystyle m=3}$.

  Dann ist ${\displaystyle f(2^{m})=(2^{m})^{2}+5\cdot 2^{m}+1}$ und somit gilt:

  ${\displaystyle f(2^{3})=(2^{3})^{2}+5\cdot 2^{3}+1=2^{6}+5\cdot 2^{3}+1=64+40+1=105}$

  Diese Zahl ${\displaystyle f(2^{3})=105}$ ist keine Primzahl und somit keine verallgemeinerte Mersenne-Primzahl, sondern nur eine verallgemeinerte Mersenne-Zahl.

• Seien ${\displaystyle f(x)=x^{2}-x+1}$ ein Polynom 2. Grades und ${\displaystyle m=32}$.

  Dann ist ${\displaystyle f(2^{m})=(2^{m})^{2}-2^{m}+1}$ und somit gilt:

  ${\displaystyle f(2^{32})=(2^{32})^{2}-2^{32}+1=2^{64}-2^{32}+1=18446744069414584321}$

  Diese Zahl ${\displaystyle f(2^{32})}$ ist eine Primzahl und somit eine verallgemeinerte Mersenne-Primzahl.

• Seien ${\displaystyle f(x)=x^{3}-x-1}$ ein Polynom 3. Grades und ${\displaystyle m=64}$.

  Dann ist ${\displaystyle f(2^{m})=(2^{m})^{3}-2^{m}-1}$ und somit gilt:^[26]

  ${\displaystyle f(2^{64})=(2^{64})^{3}-2^{64}-1=2^{192}-2^{64}-1=6277101735386680763835789423207666416083908700390324961279}$

  Diese Zahl ${\displaystyle f(2^{64})}$ ist ebenfalls eine Primzahl und somit eine verallgemeinerte Mersenne-Primzahl.

Mersenne-Zahlen haben die Form ${\displaystyle M_{n}=2^{n}-1}$. Man kann sie verallgemeinern, indem man Zahlen der Form ${\displaystyle b^{n}-1}$ mit ganzzahligen ${\displaystyle b\in \mathbb {Z} }$ betrachtet. Allerdings sind Zahlen der Form ${\displaystyle b^{n}-1}$ immer durch ${\displaystyle b-1}$ teilbar (siehe Faktorisierungen von Potenzsummen) und somit erhält man nie Primzahlen der Form ${\displaystyle b^{n}-1}$ mit ${\displaystyle b\not =2}$ und ${\displaystyle n>1}$.

Wenn man aber die Zahl ${\displaystyle b^{n}-1}$ durch ${\displaystyle b-1}$ dividiert, so erhält man die Zahl ${\displaystyle {\frac {b^{n}-1}{b-1}}}$. Diese Zahl kann sowohl prim als auch nicht prim sein. Interessant ist der Fall, wann ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ prim ist.

• Sei ${\displaystyle b=10}$. Dann ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {10^{n}-1}{10-1}}={\frac {10^{n}-1}{9}}}$ prim für folgende ${\displaystyle n}$:

  2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, … (Folge A004023 in OEIS)

Damit erhält man die folgenden Primzahlen:

11, 1111111111111111111, 11111111111111111111111, … (Folge A004022 in OEIS)

Diese Zahlen nennt man Repunits.

• Sei ${\displaystyle b=-12}$. Dann ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-12)^{n}-1}{-12-1}}={\frac {(-12)^{n}-1}{-13}}}$ prim für folgende ${\displaystyle n}$:

  (2), 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, … (Folge A057178 in OEIS)

Damit erhält man die folgenden Primzahlen, wobei man den ersten Wert dazuzählen kann oder auch nicht:

(-11), 19141, 57154490053, …

Die drei Zahlen, die man aus ${\displaystyle n\in \{106859,139739,495953\}}$ erhält, sind momentan noch nicht eindeutig als Primzahlen interpretiert worden. Sie sind sogenannte PRP-Zahlen (probable prime).^[27]

• Die kleinsten ${\displaystyle n}$, sodass ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ eine Primzahl ist, sind die folgenden (mit aufsteigendem ${\displaystyle b=2,3,4,\ldots }$; es wird ${\displaystyle 0}$ angegeben, falls es kein ${\displaystyle n}$ gibt):

  2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 3, 3, 2, 3, 2, 19, 3, 3, 2, 5, 3, 0, 7, 3, 2, 5, 2, 7, 0, 3, 13, 313, 2, 13, 3, 349, 2, 3, 2, 5, 5, 19, 2, 127, 19, 0, 3, 4229, 2, 11, 3, 17, 7, 3, 2, 3, 2, 7, 3, 5, 0, 19, 2, 19, 5, 3, 2, 3, 2, … (Folge A084740 in OEIS)

Beispiel:

In der obigen Liste steht an der 12. Stelle der Wert 5. Weil man mit 2 zu zählen beginnen muss, ist es der zu ${\displaystyle b=13}$ gehörende Wert. Somit ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {13^{5}-1}{13-1}}={\frac {371293-1}{12}}=30941}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {13^{n}-1}{12}}}$ erhalten kann.

• Die kleinsten ${\displaystyle n}$, sodass ${\displaystyle {\frac {b^{n}-1}{b-1}}}$ eine Primzahl ist, sind die folgenden (mit absteigendem ${\displaystyle b=-2,-3,-4,\ldots }$; es wird ${\displaystyle 0}$ angegeben, falls es kein ${\displaystyle n}$ gibt):

  3, 2, 2, 5, 2, 3, 2, 3, 5, 5, 2, 3, 2, 3, 3, 7, 2, 17, 2, 3, 3, 11, 2, 3, 11, 0, 3, 7, 2, 109, 2, 5, 3, 11, 31, 5, 2, 3, 53, 17, 2, 5, 2, 103, 7, 5, 2, 7, 1153, 3, 7, 21943, 2, 3, 37, 53, 3, 17, 2, 7, 2, 3, 0, 19, 7, 3, 2, 11, 3, 5, 2, …

In der OEIS-Liste ist der Wert ${\displaystyle n=2}$ nicht erlaubt, weil man damit nur negative Primzahlen erhält. Deswegen unterscheidet sich diese obige Liste von der OEIS-Liste. Die exakte OEIS-Liste lautet wie folgt:

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, … (Folge A084742 in OEIS)

Beispiele:

• In der obigen ersten Liste steht an der 12. Stelle der Wert 3. Weil man mit −2 zu zählen beginnen muss, ist es der zu ${\displaystyle b=-13}$ gehörende Wert. Somit ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-13)^{3}-1}{-13-1}}={\frac {-2197-1}{-14}}=157}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {(-13)^{n}-1}{-14}}}$ erhalten kann.
• In der obigen ersten Liste steht an der 5. Stelle der Wert 2. Weil man mit −2 zu zählen beginnen muss, ist es der zu ${\displaystyle b=-6}$ gehörende Wert. Somit ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-6)^{2}-1}{-6-1}}={\frac {36-1}{-7}}=-5}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {(-6)^{n}-1}{-7}}}$ erhalten kann. Da dieser Wert negativ ist, steht bei der OEIS-Liste an der 5. Stelle (der zu ${\displaystyle b=-6}$ gehörende Wert) der Wert 3. Dann erhält man ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-6)^{3}-1}{-6-1}}={\frac {-216-1}{-7}}=31}$ die kleinste positive Primzahl, die man mit ${\displaystyle {\frac {(-6)^{n}-1}{-7}}}$ erhalten kann.
• In der obigen ersten Liste steht an der 31. Stelle der Wert 2. Weil man mit −2 zu zählen beginnen muss, ist es der zu ${\displaystyle b=-32}$ gehörende Wert. Somit ist ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-32)^{2}-1}{-32-1}}={\frac {1024-1}{-33}}=-31}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {(-32)^{n}-1}{-33}}}$ erhalten kann. Da dieser Wert negativ ist, steht bei der OEIS-Liste an der 31. Stelle (der zu ${\displaystyle b=-32}$ gehörende Wert) der Wert 0. Dies bedeutet, dass man mit ${\displaystyle {\frac {b^{n}-1}{b-1}}={\frac {(-32)^{n}-1}{-33}}}$ keine positive Primzahl erhalten kann.

• Sei ${\displaystyle \operatorname {Prim} (n)}$ die ${\displaystyle n}$-te Primzahl. Die kleinsten ${\displaystyle b}$, sodass ${\displaystyle {\frac {b^{\operatorname {Prim} (n)}-1}{b-1}}}$ eine Primzahl ist, sind die folgenden (mit aufsteigendem ${\displaystyle n=1,2,3,\ldots }$):

  2, 2, 2, 2, 5, 2, 2, 2, 10, 6, 2, 61, 14, 15, 5, 24, 19, 2, 46, 3, 11, 22, 41, 2, 12, 22, 3, 2, 12, 86, 2, 7, 13, 11, 5, 29, 56, 30, 44, 60, 304, 5, 74, 118, 33, 156, 46, 183, 72, 606, 602, 223, 115, 37, 52, 104, 41, 6, 338, 217, … (Folge A066180 in OEIS)

Beispiel:

In der obigen Liste steht an der 5. Stelle der Wert ${\displaystyle b=5}$. Die 5. Primzahl ist ${\displaystyle p=11}$. Somit ist ${\displaystyle {\frac {b^{\operatorname {Prim} (n)}-1}{b-1}}={\frac {5^{11}-1}{5-1}}={\frac {48828125-1}{4}}=12207031}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {b^{11}-1}{b-1}}}$ erhalten kann.

• Sei ${\displaystyle \operatorname {Prim} (n)}$ die n-te Primzahl. Die betragsmäßig kleinsten negativen ${\displaystyle b}$, sodass ${\displaystyle {\frac {b^{\operatorname {Prim} (n)}-1}{b-1}}}$ eine Primzahl ist, sind die folgenden (mit aufsteigendem ${\displaystyle n=1,2,3,\ldots }$):

  3, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, … (Folge A103795 in OEIS)

Beispiel:

In der obigen Liste steht an der 5. Stelle der Wert ${\displaystyle b=2}$. Die 5. Primzahl ist ${\displaystyle p=11}$. Somit ist ${\displaystyle {\frac {b^{\operatorname {Prim} (n)}-1}{b-1}}={\frac {(-2)^{11}-1}{-2-1}}={\frac {-2048-1}{-3}}=683}$ die kleinste Primzahl, die man mit ${\displaystyle {\frac {b^{11}-1}{b-1}}}$, ${\displaystyle b\in \mathbb {Z} ^{-}}$ erhalten kann.

Es wird vermutet, dass für jedes ${\displaystyle b}$, welches keine Potenz einer natürlichen Zahl ist, unendlich viele ${\displaystyle n}$ existieren, sodass ${\displaystyle {\tfrac {b^{n}-1}{b-1}}}$ eine Primzahl ist.

(Ist ${\displaystyle b}$ eine Potenz einer natürlichen Zahl, so kann gezeigt werden, dass es höchstens ein ${\displaystyle n}$ gibt, sodass ${\displaystyle {\tfrac {b^{n}-1}{b-1}}}$ eine Primzahl ist.)

Man kann Mersenne-Zahlen auch insofern verallgemeinern, als dass man Zahlen der Form ${\displaystyle {\tfrac {a^{n}-b^{n}}{a-b}}}$ betrachtet, wobei ${\displaystyle a,b}$ teilerfremd, ${\displaystyle a>1}$ und ${\displaystyle -a<b<a}$ sein muss. Die Division durch die Zahl ${\displaystyle a-b}$ ist notwendig, weil diese Zahl immer Teiler von ${\displaystyle a^{n}-b^{n}}$ ist und man nur nach dieser Division Primzahlen erhalten kann.

Verallgemeinerte Mersenne-Zahlen der Form ${\displaystyle {\tfrac {a^{n}-b^{n}}{a-b}}}$ sind gleichzeitig die Zahlen der allgemeinen Lucas-Folge ${\displaystyle U_{n}(a+b,ab)}$, wobei ${\displaystyle a}$ und ${\displaystyle b}$ die Nullstellen der quadratischen Gleichung ${\displaystyle x^{2}-(a-b)x+ab=0}$ sind (siehe explizite Formeln).

• Sei ${\displaystyle {\frac {a^{n}-b^{n}}{a-b}}}$ eine Primzahl. Dann gilt:

  • ${\displaystyle n}$ ist eine Primzahl oder ${\displaystyle n=4}$
  • ${\displaystyle n=4}$ genau dann, wenn ${\displaystyle a+b=1}$ und ${\displaystyle a^{2}+b^{2}}$ ist eine Primzahl

Beweis der zweiten Behauptung:

Sei ${\displaystyle {\frac {a^{4}-b^{4}}{a-b}}}$ eine Primzahl (sei also ${\displaystyle n=4}$). Weil ${\displaystyle {\frac {a^{4}-b^{4}}{a-b}}=a^{3}+a^{2}b+ab^{2}+b^{3}=(a+b)\cdot (a^{2}+b^{2})}$ eine Primzahl ist, muss einer der beiden Faktoren ${\displaystyle 1}$ sein, somit ist ${\displaystyle (a,b)=(k+1,-k)}$ und ${\displaystyle a^{2}+b^{2}=(k+1)^{2}+k^{2}}$ muss eine Primzahl sein. Die kleinsten ${\displaystyle k}$ dieser Form lauten:

1, 2, 4, 5, 7, 9, 12, 14, 17, 19, 22, 24, 25, 29, 30, 32, 34, 35, 39, 42, 47, 50, 60, 65, 69, 70, 72, 79, 82, 84, 85, 87, 90, 97, 99, 100, … (Folge A027861 in OEIS)

${\displaystyle \Box }$

Die folgende Tabelle gibt die kleinsten ${\displaystyle n}$ an, für welche ${\displaystyle {\tfrac {a^{n}-b^{n}}{a-b}}}$ bei gegebenem ${\displaystyle a}$ und ${\displaystyle b}$ prim ist.^{[28][29][30][31][32][33][34]}

Bei besonders großen Zahlen ist es noch nicht gesichert, ob es sich um wirkliche Primzahlen handelt oder ob es nur sehr wahrscheinliche Primzahlen, so genannte PRP-Zahlen (probably primes) sind. Diese Zahlen werden in Klammern gesetzt.^[35][36]