Wagstaff-Primzahl

In der Zahlentheorie ist eine Wagstaff-Primzahl eine Primzahl $p$ der Form

p={\frac {2^{q}+1}{3}}

mit einer ungeraden Primzahl

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:

3={\frac {2^{3}+1}{3}}

,

11={\frac {2^{5}+1}{3}}

,

43={\frac {2^{7}+1}{3}}

, …

Die ersten Exponenten $q\in \mathbb {P}$ , die auf Wagstaff-Primzahlen $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, 117239 (Folge A000978 in OEIS)

Die weiteren Exponenten $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):

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

Im Februar 2010 entdeckte Tony Reix die Wagstaff-PRP ${\frac {2^{4031399}+1}{3}}$ . Sie hat $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 Juni 2021 entdeckte Ryan Propper die bis dato (Stand: 22. September 2022) größte potentielle Wagstaff-Primzahl, nämlich die Zahl ${\frac {2^{15135397}+1}{3}}$ mit $4556209$ Stellen. Diese Zahl ist die momentan drittgrößte probable prime (PRP), die bisher entdeckt wurde.^[3]

Eigenschaften

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

{\frac {2^{p}+1}{3}}

muss nicht unbedingt eine Primzahl sein

Beweis: Das kleinste Gegenbeispiel lautet:

{\frac {2^{683}+1}{3}}=1676083\cdot 26955961001\cdot Z_{189}

ist keine Primzahl.

Ungelöste Probleme

Es wird folgende Aussage vermutet:

Sei

p\in \mathbb {P}

eine Wagstaff-Primzahl mit

p>43

. Dann gilt:

{\frac {2^{p}+1}{3}}

ist immer zusammengesetzt.

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

127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531, 15135397 (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 ${\frac {2^{95369}+1}{3}}$ mit $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) von Jean Penné werden potentielle Wagstaff-Primzahl-Kandidaten gefunden.^[6]

Verallgemeinerung

Eine Wagstaff-Zahl mit Basis b hat die Form

Q(b,n)={\frac {b^{n}+1}{b+1}}

mit einer Basis

b\in \mathbb {N}

,

b\geq 2

und einer ungeraden Zahl

n\in \mathbb {N}

Eine prime Wagstaff-Zahl mit Basis $b$ nennt man Wagstaff-Primzahl mit Basis b.

Beispiele

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

$b$	Form	Potenzen $n$ , sodass Wagstaff-Primzahlen mit Basis $b$ , also der Form ${\frac {b^{n}+1}{b+1}}$ , prim oder PRP sind	OEIS-Folge
$2$	${\frac {2^{n}+1}{3}}$	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, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, … (die ursprünglichen Wagstaff-Primzahlen)	(Folge A000978 in OEIS)
$3$	${\frac {3^{n}+1}{4}}$	3, 5, 7, 13, 23, 43, 281, 359, 487, 577, 1579, 1663, 1741, 3191, 9209, 11257, 12743, 13093, 17027, 26633, 104243, 134227, 152287, 700897, 1205459, 1896463, 2533963, …	(Folge A007658 in OEIS)
$4$	${\frac {4^{n}+1}{5}}$	3 (es gibt keine weiteren Wagstaff-Primzahlen mit Basis $b=4$ , weil $4^{n}+1=(2^{n}-2^{\frac {n+1}{2}}+1)\cdot (2^{n}+2^{\frac {n+1}{2}}+1)$ )
$5$	${\frac {5^{n}+1}{6}}$	5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, 1856147, …	(Folge A057171 in OEIS)
$6$	${\frac {6^{n}+1}{7}}$	3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, 1313371, …	(Folge A057172 in OEIS)
$7$	${\frac {7^{n}+1}{8}}$	3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, 1178033, …	(Folge A057173 in OEIS)
$8$	${\frac {8^{n}+1}{9}}$	(es gibt keine Wagstaff-Primzahlen mit Basis $b=8$ )
$9$	${\frac {9^{n}+1}{10}}$	3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, …	(Folge A057175 in OEIS)
$10$	${\frac {10^{n}+1}{11}}$	5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, 1600787, …	(Folge A001562 in OEIS)
$11$	${\frac {11^{n}+1}{12}}$	5, 7, 179, 229, 439, 557, 6113, 223999, 327001, …	(Folge A057177 in OEIS)
$12$	${\frac {12^{n}+1}{13}}$	5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, …	(Folge A057178 in OEIS)
$13$	${\frac {13^{n}+1}{14}}$	3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, 1199467, …	(Folge A057179 in OEIS)
$14$	${\frac {14^{n}+1}{15}}$	7, 53, 503, 1229, 22637, 1091401, …	(Folge A057180 in OEIS)
$15$	${\frac {15^{n}+1}{16}}$	3, 7, 29, 1091, 2423, 54449, 67489, 551927, …	(Folge A057181 in OEIS)
$16$	${\frac {16^{n}+1}{17}}$	3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, …	(Folge A057182 in OEIS)
$17$	${\frac {17^{n}+1}{18}}$	7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, …	(Folge A057183 in OEIS)
$18$	${\frac {18^{n}+1}{19}}$	3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, …	(Folge A057184 in OEIS)
$19$	${\frac {19^{n}+1}{20}}$	17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, 476929, …	(Folge A057185 in OEIS)
$20$	${\frac {20^{n}+1}{21}}$	5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, 393257, …	(Folge A057186 in OEIS)
$21$	${\frac {21^{n}+1}{22}}$	3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, 394579, …	(Folge A057187 in OEIS)
$22$	${\frac {22^{n}+1}{23}}$	3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, …	(Folge A057188 in OEIS)
$23$	${\frac {23^{n}+1}{24}}$	11, 13, 67, 109, 331, 587, 24071, 29881, 44053, …	(Folge A057189 in OEIS)
$24$	${\frac {24^{n}+1}{25}}$	7, 11, 19, 2207, 2477, 4951, …	(Folge A057190 in OEIS)
$25$	${\frac {25^{n}+1}{26}}$	3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, …	(Folge A057191 in OEIS)

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

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

Die dazugehörigen

n

kann man der obigen Tabelle entnehmen.

Die kleinsten Primzahlen $p\in \mathbb {P}$ , sodass $Q(b,p)={\frac {b^{p}+1}{b+1}}$ prim ist, sind die folgenden (für $b=2,3,4,\ldots$ ; falls keine solche Primzahl $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

b=26

) steht eine

11

.

Somit ist

Q(26,11)={\frac {26^{11}+1}{26+1}}=135938684703251\in \mathbb {P}

die kleinste Wagstaff-Primzahl mit Basis

b=26

.

Beispiel 2: An der 26. Stelle der obigen Liste (also für

b=27

) steht eine

0

.

Somit existieren keine Wagstaff-Primzahlen mit Basis

b=27

(also ist immer

Q(27,n)={\frac {27^{n}+1}{27+1}}\not \in \mathbb {P}

)

Sei $Prim(n)$ die $n$ -te Primzahl. Die kleinsten Basen $b\in \mathbb {N}$ , sodass $Q(b,Prim(n))={\frac {b^{Prim(n)}+1}{b+1}}$ prim ist, sind die folgenden (für $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

n=12

) steht eine

16

. Die 12. Primzahl ist 37, es ist also

Prim(n)=Prim(12)=37

.

Somit ist

Q(16,37)={\frac {16^{37}+1}{16+1}}\in \mathbb {P}

die Wagstaff-Primzahl mit kleinster Basis

b=16

, bei der die Hochzahl

37

sein muss.

Beispiel 2: An der 24. Stelle der obigen Liste (also für

n=25

) steht eine

70

. Die 25. Primzahl ist 97, es ist also

Prim(n)=Prim(25)=97

.

Somit ist

Q(70,97)={\frac {70^{97}+1}{70+1}}\in \mathbb {P}

die Wagstaff-Primzahl mit kleinster Basis

b=70

, bei der die Hochzahl

97

sein muss.

Eigenschaften

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

n\in \mathbb {P}

ist eine ungerade Primzahl^[7]

Die Umkehrung gilt nicht: wenn

n\in \mathbb {P}

eine ungerade Primzahl ist, muss die dazugehörige Wagstaff-Zahl mit Basis

b

nicht prim sein.

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

Dann gilt:

Die Basis-

b

-Wagstaff-Zahl

Q(a^{m},n)={\frac {(a^{m})^{n}+1}{a^{m}+1}}

ist niemals prim

In der obigen Tabelle kann man bei

b=8

erkennen, dass es keine Wagstaff-Primzahlen mit Basis

b=8

gibt.

Einzelnachweise

↑ 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.
↑ ^a ^b Chris K.Caldwell: The Top Twenty: Wagstaff. Prime Pages, abgerufen am 16. Juni 2018.
↑ ^a ^b Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, abgerufen am 16. Juni 2018.
↑ Chris K.Caldwell: The Top Twenty: Elliptic Curve Primality Proof. Prime Pages, abgerufen am 16. Juni 2018.
↑ (2⁹⁵³⁶⁹+1)/3 auf Prime Pages
↑ Download Jean Penné's LLR
↑ ^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.
↑ Henri Lifchitz: Mersenne and Fermat primes field. Abgerufen am 17. Juni 2018.
↑ 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.

[Hardy-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.

[Top20-2] Chris K.Caldwell: The Top Twenty: Wagstaff. Prime Pages, abgerufen am 16. Juni 2018.

[PRP-3] Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, abgerufen am 16. Juni 2018.

[Top20.2-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

[Dubner-7] Harvey Dubner: Primes of the Form (bⁿ + 1)/(b + 1). Journal of Integer Sequences 3, 2000, S. 1–9, abgerufen am 16. Juni 2018.

[Fermat-8] Henri Lifchitz: Mersenne and Fermat primes field. Abgerufen am 17. Juni 2018.

[Fischer-9] Richard Fischer: Allgemeine Repunitpaar-Primzahlen (B^N+1)/(B+1). Abgerufen am 17. Juni 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 1)
Primzahlfolgen	Bell \| Fibonacci \| Lucas \| Motzkin \| Pell \| Perrin
eigenschaftsbasiert	Elitär \| Fortunate \| Gut \| Glücklich \| Higgs \| Hochkototient \| Isoliert \| Pillai \| Ramanujan \| Regulär \| Stark \| Stern \| Wall–Sun–Sun \| Wieferich \| Wilson
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 1)/9) \| Schwach \| Smarandache–Wellin \| Strobogrammatisch \| Tetradisch \| Trunkierbar \| Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) \| Chen \| Cousin (p, p + 4) \| Cunningham (p, 2p ± 1, …) \| Drilling (p, p + 2 oder p + 4, p + 6) \| Konstellation \| Sexy (p, p + 6) \| Sichere (p, (p − 1)/2) \| Sophie Germain (p, 2p + 1) \| Vierling (p, p + 2, p + 6, p + 8) \| Zwilling (p, p + 2) \| Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) \| Gigantisch (10.000+ Stellen) \| Mega (1.000.000+ Stellen) \| Beva (1.000.000.000+ Stellen)

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Wagstaff-Primzahl

Inhaltsverzeichnis

Beispiele

Eigenschaften

Ungelöste Probleme

Wissenswertes

Verallgemeinerung

Beispiele

Eigenschaften

Einzelnachweise

Weblinks

Quellen