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.

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:

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 Zahl ${\frac {2^{4031399}+1}{3}}$ , welche alle Voraussetzungen hat, eine Wagstaff-Primzahl zu sein. Sie ist eine sogenannte probable prime (PRP). Sie hat $1213572$ Stellen und war zu diesem Zeitpunkt die drittgrößte PRP-Zahl, die je gefunden wurde. 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.

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. Mit dem Programm LLR (Lucas-Lehmer-Riesel-Test (en)) von Jean Penné werden potentielle Wagstaff-Primzahl-Kandidaten gefunden.

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:

$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 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

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.
1 2 Chris K.Caldwell: The Top Twenty: Wagstaff. Prime Pages, abgerufen am 16. Juni 2018.
1 2 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
1 2 3 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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] 1 2 Chris K.Caldwell: The Top Twenty: Wagstaff. Prime Pages, abgerufen am 16. Juni 2018.

[PRP-3] 1 2 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] 1 2 3 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.


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)