In der Zahlentheorie ist eine Wagstaff Primzahl eine Primzahl p displaystyle p der Form p 2 q 1 3 displaystyle p frac 2 q 1 3 mit einer ungeraden Primzahl q P displaystyle q in mathbb P Diese Zahlen wurden nach dem Mathematiker Samuel Wagstaff benannt und tauchen unter anderem in der neuen Mersenne Vermutung auf 1 Inhaltsverzeichnis 1 Beispiele 2 Eigenschaften 3 Ungeloste Probleme 4 Wissenswertes 5 Verallgemeinerung 5 1 Beispiele 5 2 Eigenschaften 6 Einzelnachweise 7 Weblinks 8 QuellenBeispiele BearbeitenDie 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 dd Dabei gilt fur die ersten drei dieser Primzahlen 3 2 3 1 3 displaystyle 3 frac 2 3 1 3 nbsp 11 2 5 1 3 displaystyle 11 frac 2 5 1 3 nbsp 43 2 7 1 3 displaystyle 43 frac 2 7 1 3 nbsp dd Die ersten Exponenten q P displaystyle q in mathbb P nbsp die auf Wagstaff Primzahlen p 2 q 1 3 displaystyle p frac 2 q 1 3 nbsp fuhren 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 q P displaystyle q in mathbb P nbsp die auf mogliche Wagstaff Primzahlen fuhren 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 2 4031399 1 3 displaystyle frac 2 4031399 1 3 nbsp Sie hat 1213572 displaystyle 1213572 nbsp Stellen und war zu diesem Zeitpunkt die drittgrosste PRP Zahl die je gefunden wurde 3 Bis heute weiss 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 grosste potentielle Wagstaff Primzahl namlich die Zahl 2 15135397 1 3 displaystyle frac 2 15135397 1 3 nbsp mit 4556209 displaystyle 4556209 nbsp Stellen Diese Zahl ist die momentan drittgrosste probable prime PRP die bisher entdeckt wurde 3 Eigenschaften BearbeitenSei p P displaystyle p in mathbb P nbsp eine Wagstaff Primzahl Dann gilt 2 p 1 3 displaystyle frac 2 p 1 3 nbsp muss nicht unbedingt eine Primzahl sein dd Beweis Das kleinste Gegenbeispiel lautet 2 683 1 3 1676083 26955961001 Z 189 displaystyle frac 2 683 1 3 1676083 cdot 26955961001 cdot Z 189 nbsp ist keine Primzahl Ungeloste Probleme BearbeitenEs wird folgende Aussage vermutet Sei p P displaystyle p in mathbb P nbsp eine Wagstaff Primzahl mit p gt 43 displaystyle p gt 43 nbsp Dann gilt 2 p 1 3 displaystyle frac 2 p 1 3 nbsp ist immer zusammengesetzt dd dd Sind die oben schon genannten Wagstaff Zahlen 2 p 1 3 displaystyle frac 2 p 1 3 nbsp mit den folgenden Exponenten p displaystyle p nbsp tatsachlich 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 dd Wissenswertes BearbeitenDer Nachweis dass Wagstaff Zahlen tatsachlich Primzahlen sind ist ausserst schwierig Dies erklart die vielen PRP Zahlen die noch nicht eindeutig als Primzahlen identifiziert wurden Sie erfullen viele Eigenschaften von Primzahlen aber es konnten auch Pseudoprimzahlen sein Momentan ist der schnellste Algorithmus mit dem man Wagstaff Zahlen als Primzahlen erkennen kann das Programm ECPP welches dafur elliptische Kurven benotigt daher der Name des Programms Elliptic Curve Primality Proving ECPP Die bis dato grosste gesicherte Wagstaff Primzahl 2 95369 1 3 displaystyle frac 2 95369 1 3 nbsp mit 28709 displaystyle 28709 nbsp Stellen gehort zu den 10 grossten Primzahlen die bisher mit dieser Methode gefunden wurden 2 4 5 Mit dem Programm LLR Lucas Lehmer Riesel Test en von Jean Penne werden potentielle Wagstaff Primzahl Kandidaten gefunden 6 Verallgemeinerung BearbeitenEine Wagstaff Zahl mit Basis b hat die Form Q b n b n 1 b 1 displaystyle Q b n frac b n 1 b 1 nbsp mit einer Basis b N displaystyle b in mathbb N nbsp b 2 displaystyle b geq 2 nbsp und einer ungeraden Zahl n N displaystyle n in mathbb N nbsp Eine prime Wagstaff Zahl mit Basis b displaystyle b nbsp nennt man Wagstaff Primzahl mit Basis b Beispiele Bearbeiten Es folgt eine Tabelle der man die kleinsten Exponenten n P displaystyle n in mathbb P nbsp entnehmen kann sodass man entweder eine Wagstaff Primzahl mit Basis b displaystyle b nbsp oder zumindest eine sehr wahrscheinliche Wagstaff Primzahl mit Basis b displaystyle b nbsp also eine PRP Zahl enthalt 7 8 9 b displaystyle b nbsp Form Potenzen n displaystyle n nbsp sodass Wagstaff Primzahlen mit Basis b displaystyle b nbsp also der Form b n 1 b 1 displaystyle frac b n 1 b 1 nbsp prim oder PRP sind OEIS Folge2 displaystyle 2 nbsp 2 n 1 3 displaystyle frac 2 n 1 3 nbsp 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 ursprunglichen Wagstaff Primzahlen Folge A000978 in OEIS 3 displaystyle 3 nbsp 3 n 1 4 displaystyle frac 3 n 1 4 nbsp 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 displaystyle 4 nbsp 4 n 1 5 displaystyle frac 4 n 1 5 nbsp 3 es gibt keine weiteren Wagstaff Primzahlen mit Basis b 4 displaystyle b 4 nbsp weil 4 n 1 2 n 2 n 1 2 1 2 n 2 n 1 2 1 displaystyle 4 n 1 2 n 2 frac n 1 2 1 cdot 2 n 2 frac n 1 2 1 nbsp 5 displaystyle 5 nbsp 5 n 1 6 displaystyle frac 5 n 1 6 nbsp 5 67 101 103 229 347 4013 23297 30133 177337 193939 266863 277183 335429 1856147 Folge A057171 in OEIS 6 displaystyle 6 nbsp 6 n 1 7 displaystyle frac 6 n 1 7 nbsp 3 11 31 43 47 59 107 811 2819 4817 9601 33581 38447 41341 131891 196337 1313371 Folge A057172 in OEIS 7 displaystyle 7 nbsp 7 n 1 8 displaystyle frac 7 n 1 8 nbsp 3 17 23 29 47 61 1619 18251 106187 201653 1178033 Folge A057173 in OEIS 8 displaystyle 8 nbsp 8 n 1 9 displaystyle frac 8 n 1 9 nbsp es gibt keine Wagstaff Primzahlen mit Basis b 8 displaystyle b 8 nbsp 9 displaystyle 9 nbsp 9 n 1 10 displaystyle frac 9 n 1 10 nbsp 3 59 223 547 773 1009 1823 3803 49223 193247 703393 Folge A057175 in OEIS 10 displaystyle 10 nbsp 10 n 1 11 displaystyle frac 10 n 1 11 nbsp 5 7 19 31 53 67 293 641 2137 3011 268207 1600787 Folge A001562 in OEIS 11 displaystyle 11 nbsp 11 n 1 12 displaystyle frac 11 n 1 12 nbsp 5 7 179 229 439 557 6113 223999 327001 Folge A057177 in OEIS 12 displaystyle 12 nbsp 12 n 1 13 displaystyle frac 12 n 1 13 nbsp 5 11 109 193 1483 11353 21419 21911 24071 106859 139739 495953 Folge A057178 in OEIS 13 displaystyle 13 nbsp 13 n 1 14 displaystyle frac 13 n 1 14 nbsp 3 11 17 19 919 1151 2791 9323 56333 1199467 Folge A057179 in OEIS 14 displaystyle 14 nbsp 14 n 1 15 displaystyle frac 14 n 1 15 nbsp 7 53 503 1229 22637 1091401 Folge A057180 in OEIS 15 displaystyle 15 nbsp 15 n 1 16 displaystyle frac 15 n 1 16 nbsp 3 7 29 1091 2423 54449 67489 551927 Folge A057181 in OEIS 16 displaystyle 16 nbsp 16 n 1 17 displaystyle frac 16 n 1 17 nbsp 3 5 7 23 37 89 149 173 251 307 317 30197 1025393 Folge A057182 in OEIS 17 displaystyle 17 nbsp 17 n 1 18 displaystyle frac 17 n 1 18 nbsp 7 17 23 47 967 6653 8297 41221 113621 233689 348259 Folge A057183 in OEIS 18 displaystyle 18 nbsp 18 n 1 19 displaystyle frac 18 n 1 19 nbsp 3 7 23 73 733 941 1097 1933 4651 481147 Folge A057184 in OEIS 19 displaystyle 19 nbsp 19 n 1 20 displaystyle frac 19 n 1 20 nbsp 17 37 157 163 631 7351 26183 30713 41201 77951 476929 Folge A057185 in OEIS 20 displaystyle 20 nbsp 20 n 1 21 displaystyle frac 20 n 1 21 nbsp 5 79 89 709 797 1163 6971 140053 177967 393257 Folge A057186 in OEIS 21 displaystyle 21 nbsp 21 n 1 22 displaystyle frac 21 n 1 22 nbsp 3 5 7 13 37 347 17597 59183 80761 210599 394579 Folge A057187 in OEIS 22 displaystyle 22 nbsp 22 n 1 23 displaystyle frac 22 n 1 23 nbsp 3 5 13 43 79 101 107 227 353 7393 50287 Folge A057188 in OEIS 23 displaystyle 23 nbsp 23 n 1 24 displaystyle frac 23 n 1 24 nbsp 11 13 67 109 331 587 24071 29881 44053 Folge A057189 in OEIS 24 displaystyle 24 nbsp 24 n 1 25 displaystyle frac 24 n 1 25 nbsp 7 11 19 2207 2477 4951 Folge A057190 in OEIS 25 displaystyle 25 nbsp 25 n 1 26 displaystyle frac 25 n 1 26 nbsp 3 7 23 29 59 1249 1709 1823 1931 3433 8863 43201 78707 Folge A057191 in OEIS Weitere Wagstaff Primzahlen mit Basis b displaystyle b nbsp fur 25 lt b 200 displaystyle 25 lt b leq 200 nbsp kann man 7 entnehmen Die kleinsten Wagstaff Primzahlen mit Basis b 10 displaystyle b 10 nbsp also der Form 10 n 1 11 displaystyle frac 10 n 1 11 nbsp sind die folgenden 9091 909091 909090909090909091 909090909090909090909090909091 Folge A097209 in OEIS dd Die dazugehorigen n displaystyle n nbsp kann man der obigen Tabelle entnehmen Die kleinsten Primzahlen p P displaystyle p in mathbb P nbsp sodass Q b p b p 1 b 1 displaystyle Q b p frac b p 1 b 1 nbsp prim ist sind die folgenden fur b 2 3 4 displaystyle b 2 3 4 ldots nbsp falls keine solche Primzahl p displaystyle p nbsp 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 dd Beispiel 1 An der 25 Stelle der obigen Liste also fur b 26 displaystyle b 26 nbsp steht eine 11 displaystyle 11 nbsp Somit ist Q 26 11 26 11 1 26 1 135938684703251 P displaystyle Q 26 11 frac 26 11 1 26 1 135938684703251 in mathbb P nbsp die kleinste Wagstaff Primzahl mit Basis b 26 displaystyle b 26 nbsp dd Beispiel 2 An der 26 Stelle der obigen Liste also fur b 27 displaystyle b 27 nbsp steht eine 0 displaystyle 0 nbsp Somit existieren keine Wagstaff Primzahlen mit Basis b 27 displaystyle b 27 nbsp also ist immer Q 27 n 27 n 1 27 1 P displaystyle Q 27 n frac 27 n 1 27 1 not in mathbb P nbsp dd Sei P r i m n displaystyle Prim n nbsp die n displaystyle n nbsp te Primzahl Die kleinsten Basen b N displaystyle b in mathbb N nbsp sodass Q b P r i m n b P r i m n 1 b 1 displaystyle Q b Prim n frac b Prim n 1 b 1 nbsp prim ist sind die folgenden fur n 2 3 4 displaystyle n 2 3 4 ldots nbsp 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 dd Beispiel 1 An der 11 Stelle der obigen Liste also fur n 12 displaystyle n 12 nbsp steht eine 16 displaystyle 16 nbsp Die 12 Primzahl ist 37 es ist also P r i m n P r i m 12 37 displaystyle Prim n Prim 12 37 nbsp Somit ist Q 16 37 16 37 1 16 1 P displaystyle Q 16 37 frac 16 37 1 16 1 in mathbb P nbsp die Wagstaff Primzahl mit kleinster Basis b 16 displaystyle b 16 nbsp bei der die Hochzahl 37 displaystyle 37 nbsp sein muss dd Beispiel 2 An der 24 Stelle der obigen Liste also fur n 25 displaystyle n 25 nbsp steht eine 70 displaystyle 70 nbsp Die 25 Primzahl ist 97 es ist also P r i m n P r i m 25 97 displaystyle Prim n Prim 25 97 nbsp Somit ist Q 70 97 70 97 1 70 1 P displaystyle Q 70 97 frac 70 97 1 70 1 in mathbb P nbsp die Wagstaff Primzahl mit kleinster Basis b 70 displaystyle b 70 nbsp bei der die Hochzahl 97 displaystyle 97 nbsp sein muss dd Eigenschaften Bearbeiten Bei einer Wagstaff Primzahl mit Basis b displaystyle b nbsp also der Form Q b n b n 1 b 1 displaystyle Q b n frac b n 1 b 1 nbsp muss immer gelten n P displaystyle n in mathbb P nbsp ist eine ungerade Primzahl 7 dd Die Umkehrung gilt nicht wenn n P displaystyle n in mathbb P nbsp eine ungerade Primzahl ist muss die dazugehorige Wagstaff Zahl mit Basis b displaystyle b nbsp nicht prim sein Sei Q b n b n 1 b 1 displaystyle Q b n frac b n 1 b 1 nbsp eine Wagstaff Zahl mit Basis b displaystyle b nbsp mit b a m displaystyle b a m nbsp m gt 1 displaystyle m gt 1 nbsp ungerade also b 1 8 27 32 64 125 128 displaystyle b in 1 8 27 32 64 125 128 ldots nbsp Folge A070265 in OEIS Dann gilt Die Basis b displaystyle b nbsp Wagstaff Zahl Q a m n a m n 1 a m 1 displaystyle Q a m n frac a m n 1 a m 1 nbsp ist niemals prim dd In der obigen Tabelle kann man bei b 8 displaystyle b 8 nbsp erkennen dass es keine Wagstaff Primzahlen mit Basis b 8 displaystyle b 8 nbsp gibt Einzelnachweise Bearbeiten 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 Penne 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 BearbeitenChris 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 BearbeitenP T Bateman J L Selfridge S S Wagstaff Jr The New Mersenne Conjecture In The American Mathematical Monthly Band 109 1989 S 125 128 V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend 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 Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Wagstaff Primzahl amp oldid 238491337
