Prothsche Primzahl

Prothsche Primzahlen sind Zahlen, die Proth-Zahlen und gleichzeitig Primzahlen sind.
Proth-Zahlen sind Zahlen der Form , wobei und positive natürliche Zahlen sind und sowohl ungerade als auch kleiner als ist.

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 „nur“ Proth-Zahlen dagegen 9, 25 und 33.

Wissenswertes

Bemerkung: ist im folgenden Artikel immer ungerade, es wird nicht bei jeder Verwendung erneut explizit darauf hingewiesen.

Jede ungerade Zahl und damit jede Primzahl größer als 2 lässt sich eindeutig in der Form schreiben. Ist die Zahl eine Primzahl und gilt zusätzlich , so handelt es sich um eine Prothsche Primzahl.

Die Bedeutung d​er Prothschen Primzahlen l​iegt darin, d​ass François Proth (1852–1879) e​inen einfachen Test gefunden h​at (Satz v​on Proth), m​it dem s​ich nachweisen lässt, o​b Proth-Zahlen Primzahlen sind. Viele d​er derzeit größten bekannten Primzahlen wurden m​it diesem Test gefunden u​nd es g​ibt ein f​rei verfügbares Programm v​on Yves Gallot, d​as den Satz v​on Proth implementiert u​nd häufig für solche Zwecke benutzt wird[1].

Der Satz v​on 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)
kFormPrimzahlen dieser FormFolgeergibt Primzahlen für n=[2]Folge
013, 5, 17, 257, 65537 (keine weiteren bekannt)Folge A019434 in OEIS1, 2, 4, 8, 16 (keine weiteren bekannt)
03(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 OEIS
05(11),  41, 641, 163841, …(1),  3, 7, 13, 15, 25, 39, 55, 75, 85, …Folge A002254 in OEIS
07(29),  113, 449, 114689, 7340033, 469762049, …Folge A050527 in OEIS(2),  4, 6, 14, 20, 26, 50, 52, 92, 120, …Folge A032353 in OEIS
09(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 OEIS
11(23), (89),  353, 1409, 5767169, 23068673, …Folge A050529 in OEIS(1), (3),  5, 7, 19, 21, 43, 81, 125, 127, …Folge A002261 in OEIS
13(53),  3329, 13313, 13631489, 3489660929, …Folge A300406 in OEIS(2),  8, 10, 20, 28, 82, 188, 308, 316, …Folge A032356 in OEIS
15(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 OEIS
17(137),  557057, 2281701377, …Folge A300407 in OEIS(3),  15, 27, 51, 147, 243, 267, 347, …Folge A002259 in OEIS
191217, 19457, 1337006139375617, …Folge A300408 in OEIS6, 10, 46, 366, 1246, 2038, 4386, …Folge A032359 in OEIS
21(43), (337),  673, 2689, 10753, …(1), (4),  5, 7, 9, 12, 16, 17, 41, 124, …Folge A032360 in OEIS
23(47),  11777, …(1),  9, 13, 29, 41, 49, 69, 73, 341, …Folge A032361 in OEIS

Die ersten Proth-Zahlen b​is 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 b​is 1000 lauten:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, … (Folge A080076 in OEIS)

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, a​ber 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 d​rei größten derzeitig bekannten Proth-Primzahlen sind:[3]

RangPrimzahlDezimal-
stellen
weitere EigenschaftenEntdeckungs-
datum
EntdeckerProjektQuelle
1 9.383.761 größte Primzahl, die nicht gleichzeitig auch Mersenne-Primzahl ist[4]
größte Colbert-Zahl
Nachweis, dass keine Sierpiński-Zahl ist
31. Okt. 2016 Péter Szabolcs (HUN) Seventeen or Bust [5][6]
2 5.832.522 Nachweis, dass keine prime Sierpiński-Zahl ist 17. Sep. 2017 Ben Maloney (AUS) Prime Sierpinski Project [7][8]
3 4.220.176 Nachweis, dass nicht die zweitkleinste Sierpiński-Zahl,
also keine Lösung des erweiterten Sierpiński-Problems ist
24. Dez. 2019 Brian D. Niegocki Extended Sierpinski Problem [9]

Einzelnachweise

  1. Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows. Abgerufen am 5. Dezember 2015.
  2. Liste von Primzahlen nach k geordnet für k < 300. Abgerufen am 5. Dezember 2015.
  3. Chris Caldwell, The Top Twenty: Proth
  4. Chris Caldwell, The Top Twenty: Largest Known Primes
  5. 10223 · 231172165 + 1 auf Prime Pages
  6. 10223 · 231172165 + 1 auf primegrid.com (PDF)
  7. 168451 · 219375200 + 1 auf Prime Pages
  8. 168451 · 219375200 + 1 auf primegrid.com (PDF)
  9. 99739 · 214019102 + 1 auf Prime Pages
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.