www.wikidata.de-de.nina.az
Prothsche Primzahlen sind naturliche Zahlen die sowohl Proth Zahlen als auch Primzahlen sind Sie sind benannt nach Francois Proth 1852 1879 Unter Proth Zahlen versteht man hierbei naturliche Zahlen der Form k 2 n 1 displaystyle k cdot 2 n 1 wobei k displaystyle k und n displaystyle n positive naturliche Zahlen sind und k displaystyle k eine ungerade Zahl ist welche zugleich kleiner als die Potenz 2 n displaystyle 2 n ist A 1 Die kleinsten Proth Zahlen sind 3 5 9 13 17 25 33 und 41 Prothsche Primzahlen davon sind 3 5 13 17 und 41 keine Primzahlen und damit zusammengesetzte Proth Zahlen dagegen 9 25 und 33 Inhaltsverzeichnis 1 Wissenswertes 2 Beispiele 3 Grosste bekannte Proth Primzahlen 4 Literatur 5 Weblinks 6 Anmerkungen 7 EinzelnachweiseWissenswertes BearbeitenJede ungerade Zahl und damit jede Primzahl grosser als 2 lasst sich eindeutig in der Form k 2 n 1 displaystyle k cdot 2 n 1 nbsp schreiben Ist eine solche Zahl eine Primzahl und gilt zusatzlich k lt 2 n displaystyle k lt 2 n nbsp so handelt es sich um eine Prothsche Primzahl Die Bedeutung der Prothschen Primzahlen liegt darin dass Francois Proth einen einfachen Test gefunden hat Satz von Proth mit dem sich nachweisen lasst ob Proth Zahlen Primzahlen sind Viele der derzeit grossten bekannten Primzahlen wurden mit diesem Test gefunden und es gibt ein frei verfugbares Programm von Yves Gallot das den Satz von Proth implementiert und haufig fur solche Zwecke benutzt wird 1 Der Satz von Proth besagt Die Proth Zahl N displaystyle N nbsp ist prim falls es eine naturliche Zahl a displaystyle a nbsp gibt mit a N 1 2 1 mod N displaystyle a frac N 1 2 equiv 1 pmod N nbsp dd Die Prothschen Primzahlen spielen auch bei den Sierpinski Zahlen insofern eine Rolle als eine Folge von Zahlen der Form k 2 n 1 displaystyle k cdot 2 n 1 nbsp frei von Prothschen Primzahlen sein muss damit k displaystyle k nbsp eine Sierpinski Zahl sein kann Unter den Prothschen Primzahlen befinden sich auch Cullen Primzahlen C1 3 C141 141 2 141 1 displaystyle 141 cdot 2 141 1 nbsp Das sind Primzahlen der Form k 2 k 1 displaystyle k cdot 2 k 1 nbsp In der folgenden Tabelle finden sich Primzahlen nach k displaystyle k nbsp geordnet bis 10 000 000 Primzahlen mit k gt 2 n displaystyle k gt 2 n nbsp die also keine Prothschen Primzahlen sind stehen in Klammern Prothsche Primzahlen mit k 1 displaystyle k 1 nbsp nennt man auch Fermatsche Primzahlen Primzahlen N displaystyle N nbsp nach k displaystyle k nbsp geordnet Primzahlen mit k gt 2 n displaystyle k gt 2 n nbsp die damit keine Proth Zahlen sind kursiv und in Klammern k Form Primzahlen dieser Form Folge ergibt Primzahlen fur n 2 Folge0 1 1 2 n 1 displaystyle 1 cdot 2 n 1 nbsp 3 5 17 257 65537 keine weiteren bekannt Folge A019434 in OEIS 1 2 4 8 16 keine weiteren bekannt 0 3 3 2 n 1 displaystyle 3 cdot 2 n 1 nbsp 7 13 97 193 769 12289 786433 3221225473 Folge A039687 in OEIS 1 2 5 6 8 12 18 30 36 41 Folge A002253 in OEIS0 5 5 2 n 1 displaystyle 5 cdot 2 n 1 nbsp 11 41 641 163841 1 3 7 13 15 25 39 55 75 85 Folge A002254 in OEIS0 7 7 2 n 1 displaystyle 7 cdot 2 n 1 nbsp 29 113 449 114689 7340033 469762049 Folge A050527 in OEIS 2 4 6 14 20 26 50 52 92 120 Folge A032353 in OEIS0 9 9 2 n 1 displaystyle 9 cdot 2 n 1 nbsp 19 37 73 577 1153 18433 147457 1179649 Folge A050528 in OEIS 1 2 3 6 7 11 14 17 33 42 43 Folge A002256 in OEIS11 11 2 n 1 displaystyle 11 cdot 2 n 1 nbsp 23 89 353 1409 5767169 23068673 Folge A050529 in OEIS 1 3 5 7 19 21 43 81 125 127 Folge A002261 in OEIS13 13 2 n 1 displaystyle 13 cdot 2 n 1 nbsp 53 3329 13313 13631489 3489660929 Folge A300406 in OEIS 2 8 10 20 28 82 188 308 316 Folge A032356 in OEIS15 15 2 n 1 displaystyle 15 cdot 2 n 1 nbsp 31 61 241 7681 15361 61441 2013265921 Folge A195745 in OEIS 1 2 4 9 10 12 27 37 38 44 48 Folge A002258 in OEIS17 17 2 n 1 displaystyle 17 cdot 2 n 1 nbsp 137 557057 2281701377 Folge A300407 in OEIS 3 15 27 51 147 243 267 347 Folge A002259 in OEIS19 19 2 n 1 displaystyle 19 cdot 2 n 1 nbsp 1217 19457 1337006139375617 Folge A300408 in OEIS 6 10 46 366 1246 2038 4386 Folge A032359 in OEIS21 21 2 n 1 displaystyle 21 cdot 2 n 1 nbsp 43 337 673 2689 10753 1 4 5 7 9 12 16 17 41 124 Folge A032360 in OEIS23 23 2 n 1 displaystyle 23 cdot 2 n 1 nbsp 47 11777 1 9 13 29 41 49 69 73 341 Folge A032361 in OEIS Die ersten Proth Zahlen bis 500 lauten 3 5 9 13 17 25 33 41 49 57 65 81 97 113 129 145 161 177 193 209 225 241 257 289 321 353 385 417 449 481 Folge A080075 in OEIS Die ersten Proth Primzahlen bis 1000 lauten 3 5 13 17 41 97 113 193 241 257 353 449 577 641 673 769 929 Folge A080076 in OEIS Beispiele BearbeitenBeispiel 1 Prothsche Primzahl Sei k 3 displaystyle k 3 nbsp und n 2 displaystyle n 2 nbsp Dann ist N k 2 n 1 3 2 2 1 13 displaystyle N k cdot 2 n 1 3 cdot 2 2 1 13 nbsp eine Proth Zahl weil k 3 displaystyle k 3 nbsp ungerade und 3 k lt 2 n 2 2 4 displaystyle 3 k lt 2 n 2 2 4 nbsp ist N 13 displaystyle N 13 nbsp ist eine Prothsche Primzahl wenn eine naturliche Zahl a N displaystyle a in mathbb N nbsp existiert sodass a N 1 2 a 13 1 2 a 6 1 mod 13 displaystyle a frac N 1 2 a frac 13 1 2 a 6 equiv 1 pmod 13 nbsp gilt Man probiert also alle Zahlen durch bis man ein geeignetes a displaystyle a nbsp findet 1 13 1 2 1 6 1 1 mod 13 2 13 1 2 2 6 64 5 13 1 1 mod 13 displaystyle begin aligned 1 frac 13 1 2 amp amp 1 6 amp amp 1 amp amp amp equiv amp 1 pmod 13 2 frac 13 1 2 amp amp 2 6 amp amp 64 amp amp 5 cdot 13 1 amp equiv amp 1 pmod 13 end aligned nbsp dd dd Somit hat man gleich am Anfang schon ein geeignetes a 2 displaystyle a 2 nbsp gefunden das den Beweis erbringt dass N 13 displaystyle N 13 nbsp eine Prothsche Primzahl ist Auch a 5 6 7 8 11 displaystyle a 5 6 7 8 11 nbsp sind geeignete Zahlen fur diesen Beweis Beispiel 2 Primzahl aber keine Prothsche Primzahl Sei k 3 displaystyle k 3 nbsp und n 1 displaystyle n 1 nbsp Dann ist N k 2 n 1 3 2 1 1 7 displaystyle N k cdot 2 n 1 3 cdot 2 1 1 7 nbsp keine Proth Zahl weil k 3 displaystyle k 3 nbsp zwar ungerade aber 3 k 2 n 2 1 2 displaystyle 3 k not lt 2 n 2 1 2 nbsp ist Allerdings ist N 7 displaystyle N 7 nbsp eine Primzahl aber eben keine Prothsche Primzahl Beispiel 3 keine Primzahl Sei k 5 displaystyle k 5 nbsp und n 4 displaystyle n 4 nbsp Dann ist N k 2 n 1 5 2 4 1 81 displaystyle N k cdot 2 n 1 5 cdot 2 4 1 81 nbsp eine Proth Zahl weil k 5 displaystyle k 5 nbsp ungerade und 5 k lt 2 n 2 4 16 displaystyle 5 k lt 2 n 2 4 16 nbsp ist N 81 displaystyle N 81 nbsp ist eine Prothsche Primzahl wenn eine naturliche Zahl a N displaystyle a in mathbb N nbsp existiert sodass a N 1 2 a 81 1 2 a 40 1 mod 81 displaystyle a frac N 1 2 a frac 81 1 2 a 40 equiv 1 pmod 81 nbsp gilt Man probiert also wieder alle Zahlen durch bis man ein geeignetes a displaystyle a nbsp findet 1 81 1 2 1 40 1 1 mod 81 2 81 1 2 2 40 1 099 511 627 776 70 mod 81 3 81 1 2 3 40 0 mod 81 4 81 1 2 4 40 40 mod 81 5 81 1 2 5 40 4 mod 81 displaystyle begin aligned 1 frac 81 1 2 amp amp 1 40 amp amp 1 amp equiv amp 1 pmod 81 2 frac 81 1 2 amp amp 2 40 amp amp 1 099 511 627 776 amp equiv amp 70 pmod 81 3 frac 81 1 2 amp amp 3 40 amp amp amp equiv amp 0 pmod 81 4 frac 81 1 2 amp amp 4 40 amp amp amp equiv amp 40 pmod 81 5 frac 81 1 2 amp amp 5 40 amp amp amp equiv amp 4 pmod 81 end aligned nbsp dd dd Analog findet man auch bei allen anderen a displaystyle a nbsp kein geeignetes das die Bedingung a 81 1 2 1 mod 81 displaystyle a frac 81 1 2 equiv 1 pmod 81 nbsp erfullt Naturlich gibt es Rechenregeln fur die Modulorechnungen sodass man hohe Zahlen umgehen kann Somit hat man den Beweis erbracht dass N 81 displaystyle N 81 nbsp keine Prothsche Primzahl ist was eigentlich von vornherein klar war da N 3 3 3 3 displaystyle N 3 cdot 3 cdot 3 cdot 3 nbsp ist Grosste bekannte Proth Primzahlen BearbeitenDie drei grossten derzeit bekannten Proth Primzahlen sind 3 Rang Primzahl Dezimal stellen weitere Eigenschaften Entdeckungs datum Entdecker Projekt Quelle1 10223 2 31172165 1 displaystyle 10223 cdot 2 31172165 1 nbsp 9 383 761 grosste Primzahl die nicht zugleich Mersenne Primzahl ist 4 grosste Colbert ZahlNachweis dass k 10223 displaystyle k 10223 nbsp keine Sierpinski Zahl ist 31 Okt 2016 Peter Szabolcs HUN Seventeen or Bust 5 6 2 202705 2 21320516 1 displaystyle 202705 cdot 2 21320516 1 nbsp 6 418 121 Nachweis dass k 202705 displaystyle k 202705 nbsp nicht die zweitkleinste Sierpinski Zahl also keine Losung des erweiterten Sierpinski Problems ist 25 Nov 2021 Pavel Atnashev RUS Extended Sierpinski Problem 7 8 9 3 168451 2 19375200 1 displaystyle 168451 cdot 2 19375200 1 nbsp 5 832 522 Nachweis dass k 168451 displaystyle k 168451 nbsp keine prime Sierpinski Zahl ist 17 Sep 2017 Ben Maloney AUS Prime Sierpinski Project 10 11 Literatur BearbeitenHans Riesel Prime Numbers and Computer Methods for Factorization Reprint of the 1994 Edition Progress in Mathematics Band 126 Birkhauser Boston 2017 ISBN 978 0 8176 8297 2 MR1292250 Weblinks BearbeitenEric W Weisstein Proth Prime In MathWorld englisch Yves Gallot s Proth exe an implementation of Proth s Theorem for Windows Programm von Yves Gallot Proth Search Page Chris Caldwell Proth prime auf The Prime Pages List of primes k 2n 1 for k lt 300 List of primes k 2n 1 for 300 lt k lt 600 Startseite des Internet Projektes Seventeen or Bust Proth prime In PlanetMath englisch Anmerkungen Bearbeiten k displaystyle k nbsp ist im hiesigen Artikel immer ungerade es wird nicht bei jeder Verwendung erneut explizit darauf hingewiesen Einzelnachweise Bearbeiten Yves Gallot s Proth exe an implementation of Proth s Theorem for Windows Abgerufen am 5 Dezember 2015 Liste von Primzahlen nach k geordnet fur k lt 300 Abgerufen am 5 Dezember 2015 Chris Caldwell The Top Twenty Proth Chris Caldwell The Top Twenty Largest Known Primes 10223 231172165 1 auf Prime Pages 10223 231172165 1 auf primegrid com PDF Welcome to the Extended Sierpinski Problem 202705 221320516 1 auf Prime Pages 202705 221320516 1 auf primegrid com PDF 168451 219375200 1 auf Prime Pages 168451 219375200 1 auf primegrid com PDF 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 Prothsche Primzahl amp oldid 225286135