Prothsche Primzahl

Art von Zahl
(Weitergeleitet von Satz von Proth)

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.[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.

Wissenswertes

Bearbeiten

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[1].

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=[2] Folge
01   3, 5, 17, 257, 65537   (keine weiteren bekannt) Folge A019434 in OEIS 1, 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
19   1217, 19457, 1337006139375617, … Folge A300408 in OEIS 6, 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 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

Bearbeiten

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

Bearbeiten

Die drei größten derzeit bekannten Proth-Primzahlen sind:[3]

Rang Primzahl Dezimal-
stellen
weitere Eigenschaften Entdeckungs-
datum
Entdecker Projekt Quelle
1   9.383.761 größte Primzahl, die nicht zugleich 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   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 Problem[7] [8][9]
3   5.832.522 Nachweis, dass   keine prime Sierpiński-Zahl ist 17. Sep. 2017 Ben Maloney (AUS) Prime Sierpinski Project [10][11]

Literatur

Bearbeiten
Bearbeiten

Anmerkungen

Bearbeiten
  1.   ist im hiesigen Artikel immer ungerade, es wird nicht bei jeder Verwendung erneut explizit darauf hingewiesen.

Einzelnachweise

Bearbeiten
  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. Welcome to the Extended Sierpinski Problem
  8. 202705 · 221320516 + 1 auf Prime Pages
  9. 202705  · 221320516 + 1 auf primegrid.com (PDF)
  10. 168451 · 219375200 + 1 auf Prime Pages
  11. 168451 · 219375200 + 1 auf primegrid.com (PDF)