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
- Es wird folgende Aussage vermutet:
- Sei eine Wagstaff-Primzahl mit . Dann gilt:
- ist immer zusammengesetzt.
- Sei eine Wagstaff-Primzahl mit . Dann gilt:
- Sind die oben schon genannten Wagstaff-Zahlen mit den folgenden Exponenten tatsächlich Wagstaff-Primzahlen, oder sind sie doch nur Pseudoprimzahlen (sogenannte PRP-Zahlen):
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 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:
- 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.
- 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
- ↑ 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.
- ↑ (295369+1)/3 auf Prime Pages
- ↑ Download Jean Penné's LLR
- ↑ 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.
- ↑ 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 (2n + 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 x2 − 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.