Wagstaff-Primzahl

In der Zahlentheorie ist eine Wagstaff-Primzahl eine Primzahl ${\displaystyle p}$ der Form

${\displaystyle p={\frac {2^{q}+1}{3}}}$ mit einer ungeraden Primzahl ${\displaystyle q\in \mathbb {P} }$

Diese Zahlen wurden nach dem Mathematiker Samuel Wagstaff benannt und tauchen unter anderem in der neuen Mersenne-Vermutung auf.^[1]

Beispiele

• Die ersten Wagstaff-Primzahlen sind die folgenden:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243, 62357403192785191176690552862561408838653121833643, … (Folge A000979 in OEIS)

Dabei gilt für die ersten drei dieser Primzahlen:

${\displaystyle 3={\frac {2^{3}+1}{3}}}$, ${\displaystyle 11={\frac {2^{5}+1}{3}}}$, ${\displaystyle 43={\frac {2^{7}+1}{3}}}$, …

• Die ersten Exponenten ${\displaystyle q\in \mathbb {P} }$, die auf Wagstaff-Primzahlen ${\displaystyle p={\frac {2^{q}+1}{3}}}$ führen, sind die folgenden:^[2]

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369 (Folge A000978 in OEIS)

• Die weiteren Exponenten ${\displaystyle q\in \mathbb {P} }$, die auf mögliche Wagstaff-Primzahlen führen, sind die folgenden (im Moment sind sie noch nicht bewiesene Primzahlen, also probable primes, PRP):

117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 (Folge A000978 in OEIS)

• Im Februar 2010 entdeckte Tony Reix die Zahl ${\displaystyle {\frac {2^{4031399}+1}{3}}}$, welche alle Voraussetzungen hat, eine Wagstaff-Primzahl zu sein. Sie ist eine sogenannte probable prime (PRP). Sie hat ${\displaystyle 1213572}$ Stellen und war zu diesem Zeitpunkt die drittgrößte PRP-Zahl, die je gefunden wurde.^[3] Bis heute weiß man noch nicht, ob sie wirklich eine echte Primzahl oder doch nur eine Pseudoprimzahl ist.
• Im September 2013 entdeckte Ryan Propper die zwei bis dato (Stand: 16. Juni 2018) größten potentiellen Wagstaff-Primzahlen, nämlich die beiden Zahlen ${\displaystyle {\frac {2^{13347311}+1}{3}}}$ mit ${\displaystyle 4017941}$ Stellen und die Zahl ${\displaystyle {\frac {2^{13372531}+1}{3}}}$ mit ${\displaystyle 4025533}$ Stellen. Beide Zahlen sind die momentan größten probable primes (PRP), die bisher entdeckt wurden.^[3]

Eigenschaften

• Sei ${\displaystyle p\in \mathbb {P} }$ eine Wagstaff-Primzahl. Dann gilt:

${\displaystyle {\frac {2^{p}+1}{3}}}$ muss nicht unbedingt eine Primzahl sein

Beweis: Das kleinste Gegenbeispiel lautet: ${\displaystyle {\frac {2^{683}+1}{3}}=1676083\cdot 26955961001\cdot Z_{189}}$ ist keine Primzahl.

Ungelöste Probleme

• Es wird folgende Aussage vermutet:

Sei ${\displaystyle p\in \mathbb {P} }$ eine Wagstaff-Primzahl mit ${\displaystyle p>43}$. Dann gilt:

${\displaystyle {\frac {2^{p}+1}{3}}}$ ist immer zusammengesetzt.

• Sind die oben schon genannten Wagstaff-Zahlen ${\displaystyle {\frac {2^{p}+1}{3}}}$ mit den folgenden Exponenten ${\displaystyle p}$ tatsächlich Wagstaff-Primzahlen, oder sind sie doch nur Pseudoprimzahlen (sogenannte PRP-Zahlen):

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 (Folge A000978 in OEIS)

Wissenswertes

Der Nachweis, dass Wagstaff-Zahlen tatsächlich Primzahlen sind, ist äußerst schwierig. Dies erklärt die vielen PRP-Zahlen, die noch nicht eindeutig als Primzahlen identifiziert wurden. Sie erfüllen viele Eigenschaften von Primzahlen, aber es könnten auch Pseudoprimzahlen sein. Momentan ist der schnellste Algorithmus, mit dem man Wagstaff-Zahlen als Primzahlen erkennen kann, das Programm ECPP, welches dafür elliptische Kurven benötigt (daher der Name des Programms: Elliptic Curve Primality Proving – ECPP). Die bis dato größte gesicherte Wagstaff-Primzahl ${\displaystyle {\frac {2^{95369}+1}{3}}}$ mit ${\displaystyle 28709}$ Stellen gehört zu den 10 größten Primzahlen, die bisher mit dieser Methode gefunden wurden.^[2][4][5] Mit dem Programm LLR (Lucas-Lehmer-Riesel-Test (en)) von Jean Penné werden potentielle Wagstaff-Primzahl-Kandidaten gefunden.^[6]

Verallgemeinerung

Eine Wagstaff-Zahl mit Basis b hat die Form

${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$ mit einer Basis ${\displaystyle b\in \mathbb {N} }$, ${\displaystyle b\geq 2}$ und einer ungeraden Zahl ${\displaystyle n\in \mathbb {N} }$

Eine prime Wagstaff-Zahl mit Basis ${\displaystyle b}$ nennt man Wagstaff-Primzahl mit Basis b.

Beispiele

• Es folgt eine Tabelle, der man die kleinsten Exponenten ${\displaystyle n\in \mathbb {P} }$ entnehmen kann, sodass man entweder eine Wagstaff-Primzahl mit Basis ${\displaystyle b}$ oder zumindest eine sehr wahrscheinliche Wagstaff-Primzahl mit Basis ${\displaystyle b}$ (also eine PRP-Zahl) enthält:^[7][8][9]

• Weitere Wagstaff-Primzahlen mit Basis ${\displaystyle b}$ für ${\displaystyle 25<b\leq 200}$ kann man ^[7] entnehmen.
• Die kleinsten Wagstaff-Primzahlen mit Basis ${\displaystyle b=10}$ (also der Form ${\displaystyle {\frac {10^{n}+1}{11}}}$) sind die folgenden:

9091, 909091, 909090909090909091, 909090909090909090909090909091, … (Folge A097209 in OEIS)

Die dazugehörigen ${\displaystyle n}$ kann man der obigen Tabelle entnehmen.

• Die kleinsten Primzahlen ${\displaystyle p\in \mathbb {P} }$, sodass ${\displaystyle Q(b,p)={\frac {b^{p}+1}{b+1}}}$ prim ist, sind die folgenden (für ${\displaystyle b=2,3,4,\ldots }$; falls keine solche Primzahl ${\displaystyle p}$ existiert, steht 0):

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)

Beispiel 1: An der 25. Stelle der obigen Liste (also für ${\displaystyle b=26}$) steht eine ${\displaystyle 11}$.

Somit ist ${\displaystyle Q(26,11)={\frac {26^{11}+1}{26+1}}=135938684703251\in \mathbb {P} }$ die kleinste Wagstaff-Primzahl mit Basis ${\displaystyle b=26}$.

Beispiel 2: An der 26. Stelle der obigen Liste (also für ${\displaystyle b=27}$) steht eine ${\displaystyle 0}$.

Somit existieren keine Wagstaff-Primzahlen mit Basis ${\displaystyle b=27}$ (also ist immer ${\displaystyle Q(27,n)={\frac {27^{n}+1}{27+1}}\not \in \mathbb {P} }$)

• Sei ${\displaystyle Prim(n)}$ die ${\displaystyle n}$-te Primzahl. Die kleinsten Basen ${\displaystyle b\in \mathbb {N} }$, sodass ${\displaystyle Q(b,Prim(n))={\frac {b^{Prim(n)}+1}{b+1}}}$ prim ist, sind die folgenden (für ${\displaystyle n=2,3,4,\ldots }$):

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, 159, … (Folge A103795 in OEIS)

Beispiel 1: An der 11. Stelle der obigen Liste (also für ${\displaystyle n=12}$) steht eine ${\displaystyle 16}$. Die 12. Primzahl ist 37, es ist also ${\displaystyle Prim(n)=Prim(12)=37}$.

Somit ist ${\displaystyle Q(16,37)={\frac {16^{37}+1}{16+1}}\in \mathbb {P} }$ die Wagstaff-Primzahl mit kleinster Basis ${\displaystyle b=16}$, bei der die Hochzahl ${\displaystyle 37}$ sein muss.

Beispiel 2: An der 24. Stelle der obigen Liste (also für ${\displaystyle n=25}$) steht eine ${\displaystyle 70}$. Die 25. Primzahl ist 97, es ist also ${\displaystyle Prim(n)=Prim(25)=97}$.

Somit ist ${\displaystyle Q(70,97)={\frac {70^{97}+1}{70+1}}\in \mathbb {P} }$ die Wagstaff-Primzahl mit kleinster Basis ${\displaystyle b=70}$, bei der die Hochzahl ${\displaystyle 97}$ sein muss.

Eigenschaften

• Bei einer Wagstaff-Primzahl mit Basis ${\displaystyle b}$ (also der Form ${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$) muss immer gelten:

${\displaystyle n\in \mathbb {P} }$ ist eine ungerade Primzahl^[7]

Die Umkehrung gilt nicht: wenn ${\displaystyle n\in \mathbb {P} }$ eine ungerade Primzahl ist, muss die dazugehörige Wagstaff-Zahl mit Basis ${\displaystyle b}$ nicht prim sein.

• Sei ${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$ eine Wagstaff-Zahl mit Basis ${\displaystyle b}$ mit ${\displaystyle b=a^{m}}$, ${\displaystyle m>1}$ ungerade (also ${\displaystyle b\in \{1,8,27,32,64,125,128,\ldots \}}$ (Folge A070265 in OEIS)).

Dann gilt:

Die Basis-${\displaystyle b}$-Wagstaff-Zahl ${\displaystyle Q(a^{m},n)={\frac {(a^{m})^{n}+1}{a^{m}+1}}}$ ist niemals prim

In der obigen Tabelle kann man bei ${\displaystyle b=8}$ erkennen, dass es keine Wagstaff-Primzahlen mit Basis ${\displaystyle b=8}$ gibt.

Einzelnachweise

1. ↑ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr.: The New Mersenne Conjecture. The American Mathematical Monthly 96, 1989, S. 125–128, abgerufen am 16. Juni 2018. 
2. ↑ ^{a b} Chris K.Caldwell: The Top Twenty: Wagstaff. Prime Pages, abgerufen am 16. Juni 2018. 
3. ↑ ^{a b} Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, abgerufen am 16. Juni 2018. 
4. ↑ Chris K.Caldwell: The Top Twenty: Elliptic Curve Primality Proof. Prime Pages, abgerufen am 16. Juni 2018. 
5. ↑ (2⁹⁵³⁶⁹+1)/3 auf Prime Pages
6. ↑ Download Jean Penné's LLR
7. ↑ ^{a b c} Harvey Dubner: Primes of the Form (bⁿ + 1)/(b + 1). Journal of Integer Sequences 3, 2000, S. 1–9, abgerufen am 16. Juni 2018. 
8. ↑ Henri Lifchitz: Mersenne and Fermat primes field. Abgerufen am 17. Juni 2018. 
9. ↑ Richard Fischer: Allgemeine Repunitpaar-Primzahlen (B^N+1)/(B+1). Abgerufen am 17. Juni 2018. 

Weblinks

• Chris K. Caldwell: Wagstaff Prime. The Prime Glossary, abgerufen am 13. Juni 2018 (englisch). 
• Renaud Lifchitz, Henri Lifchitz: An efficient probable prime test for numbers of the form (2ⁿ + 1)/3. Abgerufen am 17. Juni 2018 (englisch). 
• Tony Reix: Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x² − 2 modulo a prime. Abgerufen am 17. Juni 2018 (englisch). 
• Wagstaff Prime. In: PlanetMath. (englisch)
• Eric W. Weisstein: Wagstaff Prime. In: MathWorld (englisch).
• Eric W. Weisstein: New Mersenne Prime Conjecture. In: MathWorld (englisch).

Quellen

• P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr.: The New Mersenne Conjecture. In: The American Mathematical Monthly. Band 109, 1989, S. 125–128.