Prothsche Primzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Prothsche Primzahlen sind Primzahlen der Form k\cdot 2^n+1, wobei 2^n > k\ und k\ ungerade sein muss (solche Zahlen heißen allgemein Proth-Zahlen, auch wenn sie keine Primzahlen sind). Jede Primzahl lässt sich eindeutig in der Form k\cdot 2^n+1 schreiben; damit eine Primzahl eine Prothsche Primzahl ist, muss aber zusätzlich 2^n > k\ gelten.

Die Bedeutung der Prothschen Primzahlen liegt darin, dass François Proth (1852–1879) 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, dass den Satz von Proth implementiert und häufig für solche Zwecke benutzt wird.

Der Satz von Proth besagt: Die Proth-Zahl N ist prim, falls es eine natürliche Zahl a gibt mit:

a^{\frac{N-1}{2}}\equiv -1\ \pmod{N}

Die Prothschen Primzahlen spielen auch bei den Sierpinski-Zahlen insofern eine Rolle, als eine Folge von Zahlen der Form k \cdot 2^n+1\ frei von Prothschen Primzahlen sein muss, damit k\ eine Sierpinski-Zahl sein kann.

Unter den prothschen Primzahlen befinden sich auch Cullen-Primzahlen. Das sind Primzahlen der Form n\cdot 2^n+1.

In der folgenden Tabelle finden sich Primzahlen nach k geordnet. Primzahlen mit 2^n < k\ , die also keine Prothschen Primzahlen sind, stehen in Klammern.

Primzahlen nach k geordnet
k
1: 3, 5, 17, 257, 65537, …
3: (7), 13, 97, 193, 769, 12289, …
5: (11), 41, 641, 163841, …
7: (29), 113, 449, 114689, …
9: (19), (37), (73), 577, 1153, 18433, …
11: (23), (89), 353, 1409, 5767169, …
13: (53), 3329, 13313, …
15: (31), (61), 241, 7681, 15361, …
17: (137), 557057, …
19: 1217, 19457, …
21: (43), (337), 673, 2689, 10753, …
23: (47), 11777, …

Die größte bisher bekannte Proth-Primzahl ist 19249 \cdot 2^{13018586} + 1 (Konstantin Agafonov 2007)[1].

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Chris Caldwell, Top Twenty: Proth