Doppelte Mersenne-Zahl

In der Zahlentheorie ist eine doppelte Mersenne-Zahl eine Zahl der Form M M n = 2 2 n − 1 − 1 {\displaystyle M_{M_{n}}=2^{2^{n}-1}-1} , wobei n ∈ N {\displaystyle n\in \mathbb {N} } eine natürliche Zahl und M n {\displaystyle M_{n}} die n {\displaystyle n} -te Mersenne-Zahl ist.

Beispiele

Die ersten fünf doppelten Mersenne-Zahlen sind die folgenden (Folge A077585 in OEIS):

M M 1 = 2 2 1 − 1 − 1 = 2 1 − 1 = M 1 = 1 M M 2 = 2 2 2 − 1 − 1 = 2 3 − 1 = M 3 = 7 M M 3 = 2 2 3 − 1 − 1 = 2 7 − 1 = M 7 = 127 M M 4 = 2 2 4 − 1 − 1 = 2 15 − 1 = M 15 = 32767 M M 5 = 2 2 5 − 1 − 1 = 2 31 − 1 = M 31 = 2147483647 {\displaystyle {\begin{aligned}M_{M_{1}}&=&2^{2^{1}-1}-1&=&2^{1}-1&=&M_{1}&=&1\\M_{M_{2}}&=&2^{2^{2}-1}-1&=&2^{3}-1&=&M_{3}&=&7\\M_{M_{3}}&=&2^{2^{3}-1}-1&=&2^{7}-1&=&M_{7}&=&127\\M_{M_{4}}&=&2^{2^{4}-1}-1&=&2^{15}-1&=&M_{15}&=&32767\\M_{M_{5}}&=&2^{2^{5}-1}-1&=&2^{31}-1&=&M_{31}&=&2147483647\\\end{aligned}}}

Eigenschaften

Jede doppelte Mersenne-Zahl ist M M n {\displaystyle M_{M_{n}}} ist definitionsgemäß selbst Mersenne-Zahl, nämlich die M n {\displaystyle M_{n}} -te.

Doppelte Mersenne-Primzahlen

Ist eine doppelte Mersenne-Zahl M M p {\displaystyle M_{M_{p}}} eine Primzahl, nennt man sie doppelte Mersenne-Primzahl.

Beispiele

Die ersten vier doppelten Mersenne-Primzahlen sind die folgenden (Folge A077586 in OEIS):

M M 2 = 2 2 2 − 1 − 1 = 2 3 − 1 = M 3 = 7 M M 3 = 2 2 3 − 1 − 1 = 2 7 − 1 = M 7 = 127 M M 5 = 2 2 5 − 1 − 1 = 2 31 − 1 = M 31 = 2147483647 M M 7 = 2 2 7 − 1 − 1 = 2 127 − 1 = M 127 = 170141183460469231731687303715884105727 {\displaystyle {\begin{aligned}M_{M_{2}}&=&2^{2^{2}-1}-1&=&2^{3}-1&=&M_{3}&=&7\\M_{M_{3}}&=&2^{2^{3}-1}-1&=&2^{7}-1&=&M_{7}&=&127\\M_{M_{5}}&=&2^{2^{5}-1}-1&=&2^{31}-1&=&M_{31}&=&2147483647\\M_{M_{7}}&=&2^{2^{7}-1}-1&=&2^{127}-1&=&M_{127}&=&170141183460469231731687303715884105727\end{aligned}}}

Mehr als diese vier sind momentan nicht bekannt.

Eigenschaften

Sei M M n = 2 2 n − 1 − 1 {\displaystyle M_{M_{n}}=2^{2^{n}-1}-1} mit natürlichem n ∈ N {\displaystyle n\in \mathbb {N} } . Dann gilt:

M M n = 2 2 n − 1 − 1 {\displaystyle M_{M_{n}}=2^{2^{n}-1}-1} ist nur dann eine Primzahl, wenn auch die Mersenne-Zahl M n {\displaystyle M_{n}} eine Primzahl ist.

Die Umkehrung gilt nicht: Wenn M n {\displaystyle M_{n}} eine Primzahl ist, kann M M n = 2 2 n − 1 − 1 {\displaystyle M_{M_{n}}=2^{2^{n}-1}-1} eine Primzahl sein, muss es aber nicht.

Beweis der Behauptung:
Beweis:
Zuerst wird folgender Hilfssatz bewiesen:
  • Sei die Mersenne-Zahl M n := 2 n − 1 {\displaystyle M_{n}:=2^{n}-1} eine Primzahl. Dann muss auch n {\displaystyle n} eine Primzahl sein.
Beweis dieses Hilfssatzes:
Dieser Beweis funktioniert indirekt, er ist ein Beweis durch Widerspruch:
Angenommen, dass n {\displaystyle n} keine Primzahl, sondern eine zusammengesetzte Zahl ist. Dann kann man n {\displaystyle n} darstellen als Produkt zweier Zahlen, nämlich n = a ⋅ b {\displaystyle n=a\cdot b} mit a > 1 {\displaystyle a>1} und b > 1 {\displaystyle b>1} . Dann gilt wegen gewissen Formeln für höhere Potenzen:
M n = 2 n − 1 = 2 a b − 1 = ( 2 a ) b − 1 = ( 2 a − 1 ) ⋅ ( ( 2 a ) b − 1 + ( 2 a ) b − 2 + … + 2 a + 1 ) {\displaystyle M_{n}=2^{n}-1=2^{ab}-1=(2^{a})^{b}-1=(2^{a}-1)\cdot ((2^{a})^{b-1}+(2^{a})^{b-2}+\ldots +2^{a}+1)}
Somit hat M n = 2 n − 1 {\displaystyle M_{n}=2^{n}-1} den nichttrivialen Teiler 2 a − 1 > 1 {\displaystyle 2^{a}-1>1} und ist keine Primzahl.
Es wurde also gezeigt, dass wenn n {\displaystyle n} keine Primzahl ist, dass auch M n = 2 n − 1 {\displaystyle M_{n}=2^{n}-1} keine Primzahl ist.
Somit muss die Annahme fallengelassen werden, dass n {\displaystyle n} keine Primzahl ist. Nur wenn n {\displaystyle n} eine Primzahl ist, kann auch M n = 2 n − 1 {\displaystyle M_{n}=2^{n}-1} eine Primzahl sein. ◻ {\displaystyle \Box }
Nun wird bewiesen, dass die doppelte Mersenne-Zahl M M n = 2 2 n − 1 − 1 {\displaystyle M_{M_{n}}=2^{2^{n}-1}-1} nur dann eine Primzahl ist, wenn auch die Mersenne-Zahl M n {\displaystyle M_{n}} eine Primzahl ist:
Die doppelte Mersenne-Zahl M M n {\displaystyle M_{M_{n}}} ist auch eine Mersenne-Zahl. Somit kann man obigen Hilfssatz direkt anwenden. Es muss also M n {\displaystyle {M_{n}}} eine Primzahl sein. ◻ {\displaystyle \Box }
Bleibt noch zu zeigen, dass die Umkehrung nicht gilt:
Zu zeigen: wenn M p {\displaystyle M_{p}} eine Primzahl ist, kann M M p = 2 2 p − 1 − 1 {\displaystyle M_{M_{p}}=2^{2^{p}-1}-1} eine Primzahl sein, muss es aber nicht.
Es reicht ein einziges Gegenbeispiel:
Sei p = 13 {\displaystyle p=13} . Dann ist M M 13 = 2 2 13 − 1 − 1 = 2 8191 − 1 = M 8191 {\displaystyle M_{M_{13}}=2^{2^{13}-1}-1=2^{8191}-1=M_{8191}} . Diese Zahl hat aber den Primteiler p 1 = 338193759479 {\displaystyle p_{1}=338193759479} . Somit ist also M M 13 {\displaystyle M_{M_{13}}} keine Primzahl, ein Gegenbeispiel wurde gefunden. ◻ {\displaystyle \Box }

Tabelle

Die folgende Tabelle zeigt an, welche doppelten Mersenne-Zahlen M M p {\displaystyle M_{M_{p}}} mit p ∈ P {\displaystyle p\in \mathbb {P} } prim sind, welche nicht und von welchen noch nicht einmal bekannt ist, ob es sich um Primzahlen handelt oder nicht. Dabei ist Z k {\displaystyle Z_{k}} eine k {\displaystyle k} -stellige zusammengesetzte Zahl und R k {\displaystyle R_{k}} ein k {\displaystyle k} -stelliger Restfaktor:

p {\displaystyle p} M p = 2 p − 1 {\displaystyle M_{p}=2^{p}-1} M M p = 2 2 p − 1 − 1 {\displaystyle M_{M_{p}}=2^{2^{p}-1}-1} Anzahl der Stellen von M M p {\displaystyle M_{M_{p}}} M M p {\displaystyle M_{M_{p}}} Primzahl? Faktorisierung von M M p {\displaystyle M_{M_{p}}}
2 M 2 = 2 2 − 1 = 3 ∈ P {\displaystyle M_{2}=2^{2}-1=3\in \mathbb {P} } M M 2 = 2 3 − 1 = 7 {\displaystyle M_{M_{2}}=2^{3}-1=7} 1 prim 7 {\displaystyle 7}
3 M 3 = 2 3 − 1 = 7 ∈ P {\displaystyle M_{3}=2^{3}-1=7\in \mathbb {P} } M M 3 = 2 7 − 1 = 127 {\displaystyle M_{M_{3}}=2^{7}-1=127} 3 prim 127 {\displaystyle 127}
5 M 5 = 2 5 − 1 = 31 ∈ P {\displaystyle M_{5}=2^{5}-1=31\in \mathbb {P} } M M 5 = 2 31 − 1 = 2147483647 {\displaystyle M_{M_{5}}=2^{31}-1=2147483647} 10 prim 2147483647 {\displaystyle 2147483647}
7 M 7 = 2 7 − 1 = 127 ∈ P {\displaystyle M_{7}=2^{7}-1=127\in \mathbb {P} } M M 7 = 2 127 − 1 {\displaystyle M_{M_{7}}=2^{127}-1} 39 prim 170141183460469231731687303715884105727 {\displaystyle 170141183460469231731687303715884105727}
11 M 11 = 2 11 − 1 = 2047 ∉ P {\displaystyle M_{11}=2^{11}-1=2047\not \in \mathbb {P} } M M 11 = 2 2047 − 1 {\displaystyle M_{M_{11}}=2^{2047}-1} 617 nicht prim 47 ⋅ 131009 ⋅ 178481 ⋅ 724639 ⋅ 2529391927 ⋅ 70676429054711 ⋅ 618970019642690137449562111 ⋅ Z 549 {\displaystyle 47\cdot 131009\cdot 178481\cdot 724639\cdot 2529391927\cdot 70676429054711\cdot 618970019642690137449562111\cdot Z_{549}}
13 M 13 = 2 13 − 1 = 8191 ∈ P {\displaystyle M_{13}=2^{13}-1=8191\in \mathbb {P} } M M 13 = 2 8191 − 1 {\displaystyle M_{M_{13}}=2^{8191}-1} 2.466 nicht prim 338193759479 ⋅ 210206826754181103207028761697008013415622289 ⋅ Z 2410 {\displaystyle 338193759479\cdot 210206826754181103207028761697008013415622289\cdot Z_{2410}}
17 M 17 = 2 17 − 1 = 131071 ∈ P {\displaystyle M_{17}=2^{17}-1=131071\in \mathbb {P} } M M 17 = 2 131071 − 1 {\displaystyle M_{M_{17}}=2^{131071}-1} 39.457 nicht prim 231733529 ⋅ 64296354767 ⋅ Z 39438 {\displaystyle 231733529\cdot 64296354767\cdot Z_{39438}}
19 M 19 = 2 19 − 1 = 524287 ∈ P {\displaystyle M_{19}=2^{19}-1=524287\in \mathbb {P} } M M 19 = 2 524287 − 1 {\displaystyle M_{M_{19}}=2^{524287}-1} 157.827 nicht prim 62914441 ⋅ 5746991873407 ⋅ 2106734551102073202633922471 ⋅ 824271579602877114508714150039 ⋅ 65997004087015989956123720407169 ⋅ Z 157717 {\displaystyle 62914441\cdot 5746991873407\cdot 2106734551102073202633922471\cdot 824271579602877114508714150039\cdot 65997004087015989956123720407169\cdot Z_{157717}}
23 M 23 = 2 23 − 1 = 8388607 ∉ P {\displaystyle M_{23}=2^{23}-1=8388607\not \in \mathbb {P} } M M 23 = 2 8388607 − 1 {\displaystyle M_{M_{23}}=2^{8388607}-1} 2.525.223 nicht prim 2351 ⋅ 4513 ⋅ 13264529 ⋅ 76899609737 ⋅ Z 2525198 {\displaystyle 2351\cdot 4513\cdot 13264529\cdot 76899609737\cdot Z_{2525198}}
29 M 29 = 2 29 − 1 = 536870911 ∉ P {\displaystyle M_{29}=2^{29}-1=536870911\not \in \mathbb {P} } M M 29 = 2 536870911 − 1 {\displaystyle M_{M_{29}}=2^{536870911}-1} 161.614.249 nicht prim 1399 ⋅ 2207 ⋅ 135607 ⋅ 622577 ⋅ 16673027617 ⋅ 4126110275598714647074087 ⋅ R 161614196 {\displaystyle 1399\cdot 2207\cdot 135607\cdot 622577\cdot 16673027617\cdot 4126110275598714647074087\cdot R_{161614196}}
31 M 31 = 2 31 − 1 = 2147483647 ∈ P {\displaystyle M_{31}=2^{31}-1=2147483647\in \mathbb {P} } M M 31 = 2 2147483647 − 1 {\displaystyle M_{M_{31}}=2^{2147483647}-1} 646.456.993 nicht prim 295257526626031 ⋅ 87054709261955177 ⋅ 242557615644693265201 ⋅ 178021379228511215367151 ⋅ R 646456918 {\displaystyle 295257526626031\cdot 87054709261955177\cdot 242557615644693265201\cdot 178021379228511215367151\cdot R_{646456918}}
37 M 37 = 2 37 − 1 = 137438953471 ∉ P {\displaystyle M_{37}=2^{37}-1=137438953471\not \in \mathbb {P} } M M 37 = 2 137438953471 − 1 {\displaystyle M_{M_{37}}=2^{137438953471}-1} 41.373.247.568 nicht prim unbekannt
41 M 41 = 2 41 − 1 = 2199023255551 ∉ P {\displaystyle M_{41}=2^{41}-1=2199023255551\not \in \mathbb {P} } M M 41 = 2 2199023255551 − 1 {\displaystyle M_{M_{41}}=2^{2199023255551}-1} 661.971.961.084 nicht prim unbekannt
43 M 43 = 2 43 − 1 = 8796093022207 ∉ P {\displaystyle M_{43}=2^{43}-1=8796093022207\not \in \mathbb {P} } M M 43 = 2 8796093022207 − 1 {\displaystyle M_{M_{43}}=2^{8796093022207}-1} 2.647.887.844.335 nicht prim unbekannt
47 M 47 = 2 47 − 1 = 140737488355327 ∉ P {\displaystyle M_{47}=2^{47}-1=140737488355327\not \in \mathbb {P} } M M 47 = 2 140737488355327 − 1 {\displaystyle M_{M_{47}}=2^{140737488355327}-1} 42.366.205.509.364 nicht prim unbekannt
53 M 53 = 2 53 − 1 = 9007199254740991 ∉ P {\displaystyle M_{53}=2^{53}-1=9007199254740991\not \in \mathbb {P} } M M 53 = 2 9007199254740991 − 1 {\displaystyle M_{M_{53}}=2^{9007199254740991}-1} 2.711.437.152.599.296 nicht prim unbekannt
59 M 59 = 2 59 − 1 = 576460752303423487 ∉ P {\displaystyle M_{59}=2^{59}-1=576460752303423487\not \in \mathbb {P} } M M 59 = 2 576460752303423487 − 1 {\displaystyle M_{M_{59}}=2^{576460752303423487}-1} 173.531.977.766.354.911 nicht prim unbekannt
61 M 61 = 2 61 − 1 = 2305843009213693951 ∈ P {\displaystyle M_{61}=2^{61}-1=2305843009213693951\in \mathbb {P} } M M 61 = 2 2305843009213693951 − 1 {\displaystyle M_{M_{61}}=2^{2305843009213693951}-1} 694.127.911.065.419.642 unbekannt kein Primfaktor p < 4 ⋅ 10 33 {\displaystyle p<4\cdot 10^{33}} [1][2]

Die doppelte Mersenne-Zahl M M 61 {\displaystyle M_{M_{61}}} ist viel zu groß, als dass man einen bekannten Primzahltest (vor allem den auf Mersenne-Zahlen zugeschnittenen Lucas-Lehmer-Test) auf sie anwenden könnte. Daher weiß man nicht einmal, ob sie zusammengesetzt ist oder nicht. Für alle anderen Primzahlen p > 61 {\displaystyle p>61} weiß man ebenfalls noch nicht, ob M M p {\displaystyle M_{M_{p}}} prim ist oder nicht. Es wird allerdings vermutet, dass es keine anderen doppelten Mersenne-Primzahlen gibt mit Ausnahme der ersten vier.[3][4]

Catalan-Mersenne-Zahlen

Die folgenden rekursiv definierten Zahlen nennt man Catalan-Mersenne-Zahlen (Folge A007013 in OEIS):

C 0 = 2 C 1 = M ( 2 ) = M 2 = 2 C 0 − 1 = 2 2 − 1 = M 2 = 3 C 2 = M ( M ( 2 ) ) = M M 2 = 2 C 1 − 1 = 2 2 2 − 1 − 1 = M 3 = 7 C 3 = M ( M ( M ( 2 ) ) ) = M M M 2 = 2 C 2 − 1 = 2 2 2 2 − 1 − 1 − 1 = M 7 = 127 C 4 = M ( M ( M ( M ( 2 ) ) ) ) = M M M M 2 = 2 C 3 − 1 = 2 2 2 2 2 − 1 − 1 − 1 − 1 = M 127 = 170141183460469231731687303715884105727 C 5 = M ( M ( M ( M ( M ( 2 ) ) ) ) ) = M M M M M 2 = 2 C 4 − 1 = 2 2 2 2 2 2 − 1 − 1 − 1 − 1 − 1 = M 170141183460469231731687303715884105727 = … … C n = … = … = 2 C n − 1 − 1 {\displaystyle {\begin{aligned}C_{0}&=&2\\C_{1}&=&M(2)&=&M_{2}&=&2^{C_{0}}-1&=&2^{2}-1&=M_{2}=3\\C_{2}&=&M(M(2))&=&M_{M_{2}}&=&2^{C_{1}}-1&=&2^{2^{2}-1}-1&=M_{3}=7\\C_{3}&=&M(M(M(2)))&=&M_{M_{M_{2}}}&=&2^{C_{2}}-1&=&2^{2^{2^{2}-1}-1}-1&=M_{7}=127\\C_{4}&=&M(M(M(M(2))))&=&M_{M_{M_{M_{2}}}}&=&2^{C_{3}}-1&=&2^{2^{2^{2^{2}-1}-1}-1}-1&=M_{127}=170141183460469231731687303715884105727\\C_{5}&=&M(M(M(M(M(2)))))&=&M_{M_{M_{M_{M_{2}}}}}&=&2^{C_{4}}-1&=&2^{2^{2^{2^{2^{2}-1}-1}-1}-1}-1&=M_{170141183460469231731687303715884105727}=\ldots \\\ldots \\C_{n}&=&\ldots &=&\ldots &=&2^{C_{n-1}}-1\end{aligned}}}

Schon von C 5 {\displaystyle C_{5}} weiß man nicht, ob sie prim ist oder nicht, weil sie viel zu groß ist (viel größer als M M 61 {\displaystyle M_{M_{61}}} , welche für bekannte Primzahltests schon viel zu groß ist; sie hat 51.217.599.719.369.681.875.006.054.625.051.616.350 Stellen). Bekannt ist lediglich, dass sie keinen Primfaktor p < 5 ⋅ 10 51 {\displaystyle p<5\cdot 10^{51}} hat. Allerdings wird vermutet, dass diese Zahl C 5 {\displaystyle C_{5}} zusammengesetzt ist. Wenn aber C 5 {\displaystyle C_{5}} zusammengesetzt ist, wären alle weiteren C n {\displaystyle C_{n}} mit n ≥ 6 {\displaystyle n\geq 6} ebenfalls zusammengesetzt, weil schon weiter oben gezeigt wurde, dass M C n {\displaystyle M_{C_{n}}} (und C n {\displaystyle C_{n}} ist eine doppelte Mersenne-Zahl) nur dann eine Primzahl ist, wenn auch C n {\displaystyle C_{n}} eine Primzahl ist.[5][6]

Der Mathematiker Eugène Charles Catalan hat sich erstmals mit diesen Zahlen beschäftigt, nachdem die Primalität von M ( M ( M ( M ( 2 ) ) ) ) = M 127 {\displaystyle M(M(M(M(2))))=M_{127}} von Édouard Lucas im Jahr 1876 bewiesen wurde.[3][7] Er behauptete als erster, dass diese Zahlen bis zu einem gewissen oberen Limit C n {\displaystyle C_{n}} allesamt prim sind und danach alle weiteren zusammengesetzt.

Eigenschaften

Die Menge der Catalan-Mersenne-Zahlen sind eine Teilmenge der Menge der doppelten Mersenne-Zahlen.[5] Mit anderen Worten: Jede Catalan-Mersenne-Zahl ist auch gleichzeitig eine doppelte Mersenne-Zahl.

Trivia

In der Serie Futurama kommt die doppelte Mersenne-Zahl M M 7 {\displaystyle M_{M_{7}}} in der Folge Die Ära des Tentakels (2008) vor. Sie taucht kurz im Hintergrund auf einer Tafel in einem „elementaren Beweis der Goldbachschen Vermutung“ auf (welche in Wirklichkeit noch nicht bewiesen ist). In dieser Episode wird diese Zahl als martian prime bezeichnet.[5][8]

Weblinks

  • Eric W. Weisstein: Double Mersenne Number. In: MathWorld (englisch).
  • Eric W. Weisstein: Catalan-Mersenne Number. In: MathWorld (englisch).
  • Double Mersennes Prime Search

Einzelnachweise

  1. ↑ MM61 – A search for a factor of 2261-1-1
  2. ↑ MM61 – A search for a factor of 2261-1-1 – Listen
  3. ↑ a b Chris K. Caldwell: Mersenne Primes: History, Theorems and Lists – Conjectures and Unsolved Problems. Prime Pages, abgerufen am 25. Dezember 2018. 
  4. ↑ I. J. Good: Conjectures concerning the Mersenne numbers. (PDF) In: Mathematics of Computation. 1955, S. 120–121, abgerufen am 25. Dezember 2018 (9). 
  5. ↑ a b c Eric W. Weisstein: Catalan-Mersenne Number. In: MathWorld (englisch).
  6. ↑ Landon Curt Noll: Landon Curt Noll’s prime pages. Abgerufen am 26. Dezember 2018. 
  7. ↑ Eugène Charles Catalan: Frage 92. In: Nouvelle correspondance mathématique – Questions proposées. Imprimeur de l’academie royale de Belgique, 1878, S. 94–96 (französisch); Textarchiv – Internet Archive.
  8. ↑ Les mathématiques de Futurama – Grands théorèmes. Abgerufen am 26. Dezember 2018 (französisch).