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.

Beispiele Die ersten Wagstaff-Primzahlen sind die folgenden: 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243, 62357403192785191176690552862561408838653121833643, … () Dabei gilt für die ersten drei dieser Primzahlen: , , , … Die ersten Exponenten , die auf Wagstaff-Primzahlen 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 () 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 () 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. 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.

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. 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 ()

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.(295369+1)/3 auf Prime Pages Mit dem Programm LLR (Lucas-Lehmer-Riesel-Test) von Jean Penné werden potentielle Wagstaff-Primzahl-Kandidaten gefunden.Download Jean Penné's LLR

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: 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) () 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, … () 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, … () 3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, 1313371, … () 3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, 1178033, … () (es gibt keine Wagstaff-Primzahlen mit Basis ) 3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, … () 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, 1600787, … () 5, 7, 179, 229, 439, 557, 6113, 223999, 327001, … () 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, … () 3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, 1199467, … () 7, 53, 503, 1229, 22637, 1091401, … () 3, 7, 29, 1091, 2423, 54449, 67489, 551927, … () 3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, … () 7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, … () 3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, … () 17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, 476929, … () 5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, 393257, … () 3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, 394579, … () 3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, … () 11, 13, 67, 109, 331, 587, 24071, 29881, 44053, … () 7, 11, 19, 2207, 2477, 4951, … () 3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, … () Weitere Wagstaff-Primzahlen mit Basis für kann man entnehmen. Die kleinsten Wagstaff-Primzahlen mit Basis (also der Form ) sind die folgenden: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … () 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, … () 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, … () 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 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 ()). 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

Weblinks

Quellen

Kategorie:Ganzzahlmenge Kategorie:Primzahl Kategorie:Zahlentheorie