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, … (Vorlage: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 (Vorlage: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 (Vorlage: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. 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 (Vorlage: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) 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\ge 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)	(Vorlage: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, …	(Vorlage: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, …	(Vorlage:OEIS)
$6$	$\frac{6^n+1}{7}$	3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, 1313371, …	(Vorlage:OEIS)
$7$	$\frac{7^n+1}{8}$	3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, 1178033, …	(Vorlage: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, …	(Vorlage:OEIS)
$10$	$\frac{10^n+1}{11}$	5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, 1600787, …	(Vorlage:OEIS)
$11$	$\frac{11^n+1}{12}$	5, 7, 179, 229, 439, 557, 6113, 223999, 327001, …	(Vorlage:OEIS)
$12$	$\frac{12^n+1}{13}$	5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, …	(Vorlage:OEIS)
$13$	$\frac{13^n+1}{14}$	3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, 1199467, …	(Vorlage:OEIS)
$14$	$\frac{14^n+1}{15}$	7, 53, 503, 1229, 22637, 1091401, …	(Vorlage:OEIS)
$15$	$\frac{15^n+1}{16}$	3, 7, 29, 1091, 2423, 54449, 67489, 551927, …	(Vorlage:OEIS)
$16$	$\frac{16^n+1}{17}$	3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, …	(Vorlage:OEIS)
$17$	$\frac{17^n+1}{18}$	7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, …	(Vorlage:OEIS)
$18$	$\frac{18^n+1}{19}$	3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, …	(Vorlage:OEIS)
$19$	$\frac{19^n+1}{20}$	17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, 476929, …	(Vorlage:OEIS)
$20$	$\frac{20^n+1}{21}$	5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, 393257, …	(Vorlage:OEIS)
$21$	$\frac{21^n+1}{22}$	3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, 394579, …	(Vorlage:OEIS)
$22$	$\frac{22^n+1}{23}$	3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, …	(Vorlage:OEIS)
$23$	$\frac{23^n+1}{24}$	11, 13, 67, 109, 331, 587, 24071, 29881, 44053, …	(Vorlage:OEIS)
$24$	$\frac{24^n+1}{25}$	7, 11, 19, 2207, 2477, 4951, …	(Vorlage:OEIS)
$25$	$\frac{25^n+1}{26}$	3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, …	(Vorlage:OEIS)

• Weitere Wagstaff-Primzahlen mit Basis $b$ für $25<b\le 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, … (Vorlage: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,\dots$; 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, … (Vorlage: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}\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,\dots$):

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, … (Vorlage: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,\dots \}$ (Vorlage: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.

Weblinks

• Vorlage:Internetquelle
• Vorlage:Internetquelle
• Vorlage:Internetquelle
• Vorlage:PlanetMath
• Vorlage:MathWorld
• Vorlage:MathWorld

Quellen

• Vorlage:Literatur