Wagstaff-Primzahl

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

mit einer ungeraden Primzahl

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:
, , , …
  • Die ersten Exponenten , die auf Wagstaff-Primzahlen 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 , 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 . Sie hat 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 mit Stellen. Diese Zahl ist die momentan drittgrößte probable prime (PRP), die bisher entdeckt wurde.[3]

Eigenschaften

  • Sei eine Wagstaff-Primzahl. Dann gilt:
muss nicht unbedingt eine Primzahl sein
Beweis: Das kleinste Gegenbeispiel lautet: ist keine Primzahl.

Ungelöste Probleme

Sei eine Wagstaff-Primzahl mit . Dann gilt:
ist immer zusammengesetzt.
  • Sind die oben schon genannten Wagstaff-Zahlen mit den folgenden Exponenten 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 ProvingECPP). Die bis dato größte gesicherte Wagstaff-Primzahl mit 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

mit einer Basis , und einer ungeraden Zahl

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

Beispiele

  • Es folgt eine Tabelle, der man die kleinsten Exponenten entnehmen kann, sodass man entweder eine Wagstaff-Primzahl mit Basis oder zumindest eine sehr wahrscheinliche Wagstaff-Primzahl mit Basis (also eine PRP-Zahl) enthält:[7][8][9]
Form Potenzen , sodass Wagstaff-Primzahlen mit Basis , also der Form , prim oder PRP sind OEIS-Folge
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, 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)
3 (es gibt keine weiteren Wagstaff-Primzahlen mit Basis , weil )
5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, 1856147, … (Folge A057171 in OEIS)
3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, 1313371, … (Folge A057172 in OEIS)
3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, 1178033, … (Folge A057173 in OEIS)
(es gibt keine Wagstaff-Primzahlen mit Basis )
3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, … (Folge A057175 in OEIS)
5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, 1600787, … (Folge A001562 in OEIS)
5, 7, 179, 229, 439, 557, 6113, 223999, 327001, … (Folge A057177 in OEIS)
5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, … (Folge A057178 in OEIS)
3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, 1199467, … (Folge A057179 in OEIS)
7, 53, 503, 1229, 22637, 1091401, … (Folge A057180 in OEIS)
3, 7, 29, 1091, 2423, 54449, 67489, 551927, … (Folge A057181 in OEIS)
3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, … (Folge A057182 in OEIS)
7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, … (Folge A057183 in OEIS)
3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, … (Folge A057184 in OEIS)
17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, 476929, … (Folge A057185 in OEIS)
5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, 393257, … (Folge A057186 in OEIS)
3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, 394579, … (Folge A057187 in OEIS)
3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, … (Folge A057188 in OEIS)
11, 13, 67, 109, 331, 587, 24071, 29881, 44053, … (Folge A057189 in OEIS)
7, 11, 19, 2207, 2477, 4951, … (Folge A057190 in OEIS)
3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, … (Folge A057191 in OEIS)
  • Weitere Wagstaff-Primzahlen mit Basis für kann man [7] entnehmen.
  • Die kleinsten Wagstaff-Primzahlen mit Basis (also der Form ) sind die folgenden:
9091, 909091, 909090909090909091, 909090909090909090909090909091, … (Folge A097209 in OEIS)
Die dazugehörigen kann man der obigen Tabelle entnehmen.
  • Die kleinsten Primzahlen , sodass prim ist, sind die folgenden (für ; falls keine solche Primzahl 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 ) steht eine .
Somit ist die kleinste Wagstaff-Primzahl mit Basis .
Beispiel 2: An der 26. Stelle der obigen Liste (also für ) steht eine .
Somit existieren keine Wagstaff-Primzahlen mit Basis (also ist immer )
  • Sei die -te Primzahl. Die kleinsten Basen , sodass prim ist, sind die folgenden (für ):
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 ) steht eine . Die 12. Primzahl ist 37, es ist also .
Somit ist die Wagstaff-Primzahl mit kleinster Basis , bei der die Hochzahl sein muss.
Beispiel 2: An der 24. Stelle der obigen Liste (also für ) steht eine . Die 25. Primzahl ist 97, es ist also .
Somit ist die Wagstaff-Primzahl mit kleinster Basis , bei der die Hochzahl sein muss.

Eigenschaften

  • Bei einer Wagstaff-Primzahl mit Basis (also der Form ) muss immer gelten:
ist eine ungerade Primzahl[7]
Die Umkehrung gilt nicht: wenn eine ungerade Primzahl ist, muss die dazugehörige Wagstaff-Zahl mit Basis nicht prim sein.
  • Sei eine Wagstaff-Zahl mit Basis mit , ungerade (also (Folge A070265 in OEIS)).
Dann gilt:
Die Basis--Wagstaff-Zahl ist niemals prim
In der obigen Tabelle kann man bei erkennen, dass es keine Wagstaff-Primzahlen mit Basis 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. (295369+1)/3 auf Prime Pages
  6. Download Jean Penné's LLR
  7. a b c Harvey Dubner: Primes of the Form (bn + 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.

Quellen