Prothsche Primzahlen sind natürliche Zahlen, die sowohl Proth-Zahlen als auch Primzahlen sind. Sie sind benannt nach François Proth (1852–1879). Unter Proth-Zahlen versteht man hierbei natürliche Zahlen der Form , wobei und positive natürliche Zahlen sind und eine ungerade Zahl ist, welche zugleich kleiner als die Potenz ist. ist im hiesigen Artikel immer ungerade, es wird nicht bei jeder Verwendung erneut explizit darauf hingewiesen.
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.
Wissenswertes Jede ungerade Zahl und damit jede Primzahl größer als 2 lässt sich eindeutig in der Form schreiben. Ist eine solche Zahl eine Primzahl und gilt zusätzlich , so handelt es sich um eine Prothsche Primzahl.
Die Bedeutung der Prothschen Primzahlen liegt darin, dass François Proth einen einfachen Test gefunden hat (Satz von Proth), mit dem sich nachweisen lässt, ob Proth-Zahlen Primzahlen sind. Viele der derzeit größten bekannten Primzahlen wurden mit diesem Test gefunden und es gibt ein frei verfügbares Programm von Yves Gallot, das den Satz von Proth implementiert und häufig für solche Zwecke benutzt wird.
Der Satz von Proth besagt:
Die Proth-Zahl ist prim, falls es eine natürliche Zahl gibt mit:
Die Prothschen Primzahlen spielen auch bei den Sierpiński-Zahlen insofern eine Rolle, als eine Folge von Zahlen der Form frei von Prothschen Primzahlen sein muss, damit eine Sierpiński-Zahl sein kann.
Unter den Prothschen Primzahlen befinden sich auch Cullen-Primzahlen (C1 = 3, C141 = , ...). Das sind Primzahlen der Form .
In der folgenden Tabelle finden sich Primzahlen nach geordnet bis 10.000.000. Primzahlen mit , die also keine Prothschen Primzahlen sind, stehen in Klammern. Prothsche Primzahlen mit nennt man auch Fermatsche Primzahlen.
Primzahlen nach geordnet (Primzahlen mit , die damit keine Proth-Zahlen sind, kursiv und in Klammern)k Form Primzahlen dieser Form Folge ergibt Primzahlen für n= Folge1 3, 5, 17, 257, 65537 (keine weiteren bekannt) 1, 2, 4, 8, 16 (keine weiteren bekannt) –3 (7), 13, 97, 193, 769, 12289, 786433, 3221225473, … (1), 2, 5, 6, 8, 12, 18, 30, 36, 41, … 5 (11), 41, 641, 163841, … – (1), 3, 7, 13, 15, 25, 39, 55, 75, 85, … 7 (29), 113, 449, 114689, 7340033, 469762049, … (2), 4, 6, 14, 20, 26, 50, 52, 92, 120, … 9 (19), (37), (73), 577, 1153, 18433, 147457, 1179649, … (1), (2), (3), 6, 7, 11, 14, 17, 33, 42, 43, … 11 (23), (89), 353, 1409, 5767169, 23068673, … (1), (3), 5, 7, 19, 21, 43, 81, 125, 127, … 13 (53), 3329, 13313, 13631489, 3489660929, … (2), 8, 10, 20, 28, 82, 188, 308, 316, … 15 (31), (61), 241, 7681, 15361, 61441, 2013265921, … (1), (2), 4, 9, 10, 12, 27, 37, 38, 44, 48, … 17 (137), 557057, 2281701377, … (3), 15, 27, 51, 147, 243, 267, 347, … 19 1217, 19457, 1337006139375617, … 6, 10, 46, 366, 1246, 2038, 4386, … 21 (43), (337), 673, 2689, 10753, … – (1), (4), 5, 7, 9, 12, 16, 17, 41, 124, … 23 (47), 11777, … – (1), 9, 13, 29, 41, 49, 69, 73, 341, … … … … … … … 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, … ()
Die ersten Proth-Primzahlen bis 1000 lauten: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, … ()
Beispiele Beispiel 1: (Prothsche Primzahl)
Sei und Dann ist eine Proth-Zahl, weil ungerade und ist.
ist eine Prothsche Primzahl, wenn eine natürliche Zahl existiert, sodass gilt. Man probiert also alle Zahlen durch, bis man ein geeignetes findet:
Somit hat man gleich am Anfang schon ein geeignetes gefunden, das den Beweis erbringt, dass eine Prothsche Primzahl ist. Auch sind geeignete Zahlen für diesen Beweis.
Beispiel 2: (Primzahl, aber keine Prothsche Primzahl)
Sei und Dann ist keine Proth-Zahl, weil zwar ungerade, aber ist. Allerdings ist eine Primzahl, aber eben keine Prothsche Primzahl.
Beispiel 3: (keine Primzahl)
Sei und Dann ist eine Proth-Zahl, weil ungerade und ist.
ist eine Prothsche Primzahl, wenn eine natürliche Zahl existiert, sodass gilt. Man probiert also wieder alle Zahlen durch, bis man ein geeignetes findet:
Analog findet man auch bei allen anderen kein geeignetes, das die Bedingung erfüllt. Natürlich gibt es Rechenregeln für die Modulorechnungen, sodass man hohe Zahlen umgehen kann. Somit hat man den Beweis erbracht, dass keine Prothsche Primzahl ist (was eigentlich von vornherein klar war, da ist).
Größte bekannte Proth-Primzahlen Die drei größten derzeit bekannten Proth-Primzahlen sind:Chris Caldwell, The Top Twenty: Proth
Rang Primzahl Dezimal-stellen weitere Eigenschaften Entdeckungs-datum Entdecker Projekt Quelle 1 9.383.761 größte Primzahl, die nicht zugleich Mersenne-Primzahl istChris Caldwell, The Top Twenty: Largest Known PrimesNachweis, dass keine Sierpiński-Zahl ist 31. Okt. 2016 Péter Szabolcs (HUN) Seventeen or Bust10223 · 231172165 + 1 auf Prime Pages10223 · 231172165 + 1 auf primegrid.com (PDF) 2 6.418.121 Nachweis, dass nicht die zweitkleinste Sierpiński-Zahl,also keine Lösung des erweiterten Sierpiński-Problems ist 25. Nov. 2021 Pavel Atnashev (RUS) Extended Sierpinski ProblemWelcome to the Extended Sierpinski Problem202705 · 221320516 + 1 auf Prime Pages202705 · 221320516 + 1 auf primegrid.com (PDF) 3 5.832.522 Nachweis, dass keine prime Sierpiński-Zahl ist 17. Sep. 2017 Ben Maloney (AUS) Prime Sierpinski Project168451 · 219375200 + 1 auf Prime Pages168451 · 219375200 + 1 auf primegrid.com (PDF)
Literatur
Weblinks
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 < 300 List of primes k · 2n + 1 for 300 < k < 600 Startseite des Internet-Projektes “Seventeen or Bust”
Anmerkungen
Einzelnachweise
Kategorie:Ganzzahlmenge Kategorie:Primzahl Kategorie:Zahlentheorie
fi:Prothin teoreema it:Teorema di Proth ko:프로트의 정리 vi:Kiểm tra Proth