Prothsche Primzahl

Prothsche Primzahlen sind Zahlen, die Proth-Zahlen und gleichzeitig Primzahlen sind.
Proth-Zahlen sind Zahlen der Form ${\displaystyle \ k\cdot 2^{n}+1\ }$, wobei ${\displaystyle k}$ und ${\displaystyle n}$ positive natürliche Zahlen sind und ${\displaystyle k}$ sowohl ungerade als auch kleiner als ${\displaystyle 2^{n}}$ 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: ${\displaystyle k}$ 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 ${\displaystyle k\cdot 2^{n}+1}$ schreiben. Ist die Zahl eine Primzahl und gilt zusätzlich ${\displaystyle k<2^{n}\ }$, 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 ${\displaystyle N}$ ist prim, falls es eine natürliche Zahl ${\displaystyle a}$ gibt mit:

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

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

Unter den Prothschen Primzahlen befinden sich auch Cullen-Primzahlen (C₁ = 3, C₁₄₁ = ${\displaystyle 141\cdot 2^{141}+1}$, ...). Das sind Primzahlen der Form ${\displaystyle k\cdot 2^{k}+1}$.

In der folgenden Tabelle finden sich Primzahlen nach ${\displaystyle k}$ geordnet bis 10.000.000. Primzahlen mit ${\displaystyle k>2^{n}\ }$, die also keine Prothschen Primzahlen sind, stehen in Klammern. Prothsche Primzahlen mit ${\displaystyle k=1}$ nennt man auch Fermatsche Primzahlen.

Primzahlen ${\displaystyle N}$ nach ${\displaystyle k}$ geordnet      (Primzahlen mit ${\displaystyle k>2^{n}\ }$, die damit keine Proth-Zahlen sind, kursiv und in Klammern)
k	Form	Primzahlen dieser Form	Folge	ergibt Primzahlen für n=[2]	Folge
01	${\displaystyle 1\cdot 2^{n}+1}$	3, 5, 17, 257, 65537   (keine weiteren bekannt)	Folge A019434 in OEIS	1, 2, 4, 8, 16   (keine weiteren bekannt)	–
03	${\displaystyle 3\cdot 2^{n}+1}$	(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	${\displaystyle 5\cdot 2^{n}+1}$	(11),  41, 641, 163841, …	–	(1),  3, 7, 13, 15, 25, 39, 55, 75, 85, …	Folge A002254 in OEIS
07	${\displaystyle 7\cdot 2^{n}+1}$	(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	${\displaystyle 9\cdot 2^{n}+1}$	(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	${\displaystyle 11\cdot 2^{n}+1}$	(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	${\displaystyle 13\cdot 2^{n}+1}$	(53),  3329, 13313, 13631489, 3489660929, …	Folge A300406 in OEIS	(2),  8, 10, 20, 28, 82, 188, 308, 316, …	Folge A032356 in OEIS
15	${\displaystyle 15\cdot 2^{n}+1}$	(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	${\displaystyle 17\cdot 2^{n}+1}$	(137),  557057, 2281701377, …	Folge A300407 in OEIS	(3),  15, 27, 51, 147, 243, 267, 347, …	Folge A002259 in OEIS
19	${\displaystyle 19\cdot 2^{n}+1}$	1217, 19457, 1337006139375617, …	Folge A300408 in OEIS	6, 10, 46, 366, 1246, 2038, 4386, …	Folge A032359 in OEIS
21	${\displaystyle 21\cdot 2^{n}+1}$	(43), (337),  673, 2689, 10753, …	–	(1), (4),  5, 7, 9, 12, 16, 17, 41, 124, …	Folge A032360 in OEIS
23	${\displaystyle 23\cdot 2^{n}+1}$	(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 ${\displaystyle k:=3}$ und ${\displaystyle n:=2.}$ Dann ist ${\displaystyle N=k\cdot 2^{n}+1=3\cdot 2^{2}+1=13}$ eine Proth-Zahl, weil ${\displaystyle k=3}$ ungerade und ${\displaystyle 3=k<2^{n}=2^{2}=4}$ ist.

${\displaystyle N=13}$ ist eine Prothsche Primzahl, wenn eine natürliche Zahl ${\displaystyle a\in \mathbb {N} }$ existiert, sodass ${\displaystyle a^{\frac {N-1}{2}}=a^{\frac {13-1}{2}}=a^{6}\equiv -1{\pmod {13}}}$ gilt. Man probiert also alle Zahlen durch, bis man ein geeignetes ${\displaystyle a}$ findet:

${\displaystyle {\begin{aligned}1^{\frac {13-1}{2}}&=&1^{6}&=&1&&&\equiv &1{\pmod {13}}\\2^{\frac {13-1}{2}}&=&2^{6}&=&64&=&5\cdot 13-1&\equiv &-1{\pmod {13}}\end{aligned}}}$

Somit hat man gleich am Anfang schon ein geeignetes ${\displaystyle a=2}$ gefunden, das den Beweis erbringt, dass ${\displaystyle N=13}$ eine Prothsche Primzahl ist. Auch ${\displaystyle a=5,6,7,8,11}$ sind geeignete Zahlen für diesen Beweis.

Beispiel 2: (Primzahl, a​ber keine Prothsche Primzahl)

Sei ${\displaystyle k:=3}$ und ${\displaystyle n:=1.}$ Dann ist ${\displaystyle N=k\cdot 2^{n}+1=3\cdot 2^{1}+1=7}$ keine Proth-Zahl, weil ${\displaystyle k=3}$ zwar ungerade, aber ${\displaystyle 3=k\not <2^{n}=2^{1}=2}$ ist. Allerdings ist ${\displaystyle N=7}$ eine Primzahl, aber eben keine Prothsche Primzahl.

Beispiel 3: (keine Primzahl)

Sei ${\displaystyle k:=5}$ und ${\displaystyle n:=4.}$ Dann ist ${\displaystyle N=k\cdot 2^{n}+1=5\cdot 2^{4}+1=81}$ eine Proth-Zahl, weil ${\displaystyle k=5}$ ungerade und ${\displaystyle 5=k<2^{n}=2^{4}=16}$ ist.

${\displaystyle N=81}$ ist eine Prothsche Primzahl, wenn eine natürliche Zahl ${\displaystyle a\in \mathbb {N} }$ existiert, sodass ${\displaystyle a^{\frac {N-1}{2}}=a^{\frac {81-1}{2}}=a^{40}\equiv -1{\pmod {81}}}$ gilt. Man probiert also wieder alle Zahlen durch, bis man ein geeignetes ${\displaystyle a}$ findet:

${\displaystyle {\begin{aligned}1^{\frac {81-1}{2}}&=&1^{40}&=&1&\equiv \ &1{\pmod {81}}\\2^{\frac {81-1}{2}}&=&2^{40}&=&1.099.511.627.776&\equiv \ &70{\pmod {81}}\\3^{\frac {81-1}{2}}&=&3^{40}&=&&\equiv \ &0{\pmod {81}}\\4^{\frac {81-1}{2}}&=&4^{40}&=&&\equiv \ &40{\pmod {81}}\\5^{\frac {81-1}{2}}&=&5^{40}&=&&\equiv \ &4{\pmod {81}}\end{aligned}}}$

Analog findet man auch bei allen anderen ${\displaystyle a}$ kein geeignetes, das die Bedingung ${\displaystyle a^{\frac {81-1}{2}}\equiv -1{\pmod {81}}}$ erfüllt. Natürlich gibt es Rechenregeln für die Modulorechnungen, sodass man hohe Zahlen umgehen kann.

Somit hat man den Beweis erbracht, dass ${\displaystyle N=81}$ keine Prothsche Primzahl ist (was eigentlich von vornherein klar war, da ${\displaystyle N=3\cdot 3\cdot 3\cdot 3}$ ist).

Größte bekannte Proth-Primzahlen

Die d​rei größten derzeitig bekannten Proth-Primzahlen sind:[3]

Rang	Primzahl	Dezimal- stellen	weitere Eigenschaften	Entdeckungs- datum	Entdecker	Projekt	Quelle
1	${\displaystyle 10223\cdot 2^{31172165}+1}$	9.383.761	größte Primzahl, die nicht gleichzeitig auch Mersenne-Primzahl ist[4] größte Colbert-Zahl Nachweis, dass ${\displaystyle k=10223}$ keine Sierpiński-Zahl ist	31. Okt. 2016	Péter Szabolcs (HUN)	Seventeen or Bust	[5][6]
2	${\displaystyle 168451\cdot 2^{19375200}+1}$	5.832.522	Nachweis, dass ${\displaystyle k=168451}$ keine prime Sierpiński-Zahl ist	17. Sep. 2017	Ben Maloney (AUS)	Prime Sierpinski Project	[7][8]
3	${\displaystyle 99739\cdot 2^{14019102}+1}$	4.220.176	Nachweis, dass ${\displaystyle k=99739}$ 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]

Weblinks

• Eric 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 · 2ⁿ + 1 for k < 300
• List of primes k · 2ⁿ + 1 for 300 < k < 600
• Startseite des Internet-Projektes “Seventeen or Bust”
• Proth prime. In: PlanetMath. (englisch)

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 · 2^31172165 + 1 auf Prime Pages
6. 10223 · 2^31172165 + 1 auf primegrid.com (PDF)
7. 168451 · 2^19375200 + 1 auf Prime Pages
8. 168451 · 2^19375200 + 1 auf primegrid.com (PDF)
9. 99739 · 2^14019102 + 1 auf Prime Pages