imported>SchlurcherBot: Bot: http → https

2025-12-15T16:15:26Z

Bot: http → https

Neue Seite

'''Prothsche Primzahlen''' sind [[natürliche Zahl]]en, die sowohl ''Proth-Zahlen'' als auch ''[[Primzahl]]en'' sind. Sie sind benannt nach [[François Proth]] (1852–1879). 
Unter ''Proth-Zahlen'' versteht man hierbei natürliche Zahlen der Form <math>\ k\cdot 2^n \, + 1\ </math>, wobei <math>k</math> und <math>n</math> [[Positive Zahl|positive]] natürliche Zahlen sind und <math>k</math> eine [[ungerade Zahl]] ist, welche zugleich [[Transitive Relation#Ordnung der reellen Zahlen|kleiner]] als die [[Potenz (Mathematik)|Potenz]] <math>2^n</math> ist.<ref group="A"><math>k</math> ist im hiesigen Artikel immer ungerade, es wird nicht bei jeder Verwendung erneut explizit darauf hingewiesen.</ref>

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 Zahl|zusammengesetzte]] Proth-Zahlen dagegen <abbr title="3·3">9</abbr>, <abbr title="5·5">25</abbr> und <abbr title="3·11">33</abbr>.

== Wissenswertes ==
Jede ungerade Zahl und damit jede Primzahl größer als 2 lässt sich eindeutig in der Form <math>k\cdot 2^n+1</math> schreiben. Ist eine solche Zahl eine Primzahl und gilt zusätzlich <math>k < 2^n \ </math>, 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<ref>{{Internetquelle |url=https://primes.utm.edu/programs/gallot/ |titel=Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows |zugriff=2015-12-05}}</ref>.

Der ''Satz von Proth'' besagt:

: Die Proth-Zahl <math>N</math> ist prim, falls es eine [[natürliche Zahl]] <math>a</math> gibt mit:
:: <math>a^{\frac{N-1}{2}}\equiv -1\ \pmod{N}</math>

Die Prothschen Primzahlen spielen auch bei den [[Sierpiński-Zahl]]en insofern eine Rolle, als eine Folge von Zahlen der Form <math>k \cdot 2^n+1\ </math> frei von Prothschen Primzahlen sein muss, damit <math>k\ </math> eine ''Sierpiński-Zahl'' sein kann.

Unter den Prothschen Primzahlen befinden sich auch [[Cullen-Zahl|Cullen-Primzahlen]] (C1 = 3, C141 = <math>141 \cdot 2^{141} + 1</math>, ...). Das sind Primzahlen der Form <math>k\cdot 2^k+1</math>.

In der folgenden Tabelle finden sich Primzahlen nach <math>k</math> geordnet bis 10.000.000.
Primzahlen mit <math>k > 2^n\ </math>, die also keine Prothschen Primzahlen sind, stehen in Klammern. Prothsche Primzahlen mit <math>k=1</math> nennt man auch [[Fermat-Zahl#Fermatsche Primzahlen|Fermatsche Primzahlen]].

{| class="wikitable"
| colspan="6" | Primzahlen <math>N</math> nach <math>k</math> geordnet &emsp;&emsp;&emsp;&emsp; (Primzahlen mit <math>k > 2^n\ </math>, die damit keine Proth-Zahlen sind, ''kursiv'' und in Klammern)
|- class="hintergrundfarbe6"
!k || Form || Primzahlen dieser Form || Folge || ergibt Primzahlen für n=<ref>{{Internetquelle |url=http://www.prothsearch.com/riesel1.html |titel=Liste von Primzahlen nach k geordnet für k < 300 |zugriff=2015-12-05}}</ref> || Folge
|-
|{{0}}1 ||style="text-align:center"| &ensp;<math>1 \cdot 2^n+1</math> || 3, 5, 17, 257, 65537 &emsp; ''(keine weiteren bekannt)'' || {{OEIS|A019434}} || 1, 2, 4, 8, 16 &emsp; ''(keine weiteren bekannt)'' || –
|-
|{{0}}3 ||style="text-align:center"| &ensp;<math>3 \cdot 2^n+1</math> || ''(7)'',  13, 97, 193, 769, 12289, 786433, 3221225473, … || {{OEIS|A039687}} || ''(1)'',  2, 5, 6, 8, 12, 18, 30, 36, 41, … || {{OEIS|A002253}}
|-
|{{0}}5 ||style="text-align:center"| &ensp;<math>5 \cdot 2^n+1</math> || ''(11)'',  41, 641, 163841, … || – || ''(1)'',  3, 7, 13, 15, 25, 39, 55, 75, 85, … || {{OEIS|A002254}}
|-
|{{0}}7 ||style="text-align:center"| &ensp;<math>7 \cdot 2^n+1</math> || ''(29)'',  113, 449, 114689, 7340033, 469762049, … || {{OEIS|A050527}} || ''(2)'',  4, 6, 14, 20, 26, 50, 52, 92, 120, … || {{OEIS|A032353}}
|-
|{{0}}9 ||style="text-align:center"| &ensp;<math>9 \cdot 2^n+1</math> || ''(19)'', ''(37)'', ''(73)'',  577, 1153, 18433, 147457, 1179649, … || {{OEIS|A050528}} || ''(1)'', ''(2)'', ''(3)'',  6, 7, 11, 14, 17, 33, 42, 43, … || {{OEIS|A002256}}
|-
| 11 ||style="text-align:center"| <math>11 \cdot 2^n+1</math>|| ''(23)'', ''(89)'',  353, 1409, 5767169, 23068673, … || {{OEIS|A050529}} || ''(1)'', ''(3)'',  5, 7, 19, 21, 43, 81, 125, 127, … || {{OEIS|A002261}}
|-
| 13 ||style="text-align:center"| <math>13 \cdot 2^n+1</math>|| ''(53)'',  3329, 13313, 13631489, 3489660929, … || {{OEIS|A300406}} || ''(2)'',  8, 10, 20, 28, 82, 188, 308, 316, … || {{OEIS|A032356}}
|-
| 15 ||style="text-align:center"| <math>15 \cdot 2^n+1</math>|| ''(31)'', ''(61)'',  241, 7681, 15361, 61441, 2013265921, … || {{OEIS|A195745}} || ''(1)'', ''(2)'',  4, 9, 10, 12, 27, 37, 38, 44, 48, … || {{OEIS|A002258}}
|-
| 17 ||style="text-align:center"| <math>17 \cdot 2^n+1</math>|| ''(137)'',  557057, 2281701377, … || {{OEIS|A300407}} || ''(3)'',  15, 27, 51, 147, 243, 267, 347, … || {{OEIS|A002259}}
|-
| 19 ||style="text-align:center"| <math>19 \cdot 2^n+1</math>|| 1217, 19457, 1337006139375617, … || {{OEIS|A300408}} || 6, 10, 46, 366, 1246, 2038, 4386, … || {{OEIS|A032359}}
|-
| 21 ||style="text-align:center"| <math>21 \cdot 2^n+1</math>|| ''(43)'', ''(337)'',  673, 2689, 10753, … || – || ''(1)'', ''(4)'',  5, 7, 9, 12, 16, 17, 41, 124, … || {{OEIS|A032360}}
|-
| 23 ||style="text-align:center"| <math>23 \cdot 2^n+1</math>|| ''(47)'',  11777, … || – || ''(1)'',  9, 13, 29, 41, 49, 69, 73, 341, … || {{OEIS|A032361}}
|-
| … || … || … || … || … || …
|}
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, … ({{OEIS| A080075}})

Die ersten Proth-Primzahlen bis 1000 lauten:
: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, … ({{OEIS|A080076}})

== Beispiele ==
'''Beispiel 1:''' (Prothsche Primzahl)

: Sei <math>k:=3</math> und <math>n:=2.</math> Dann ist <math>N=k \cdot 2^n+1=3 \cdot 2^2+1=13</math> eine Proth-Zahl, weil <math>k=3</math> ungerade und <math>3=k<2^n=2^2=4</math> ist.

: <math>N=13</math> ist eine Prothsche Primzahl, wenn eine natürliche Zahl <math>a \in \mathbb N</math> existiert, sodass <math>a^{\frac{N-1}{2}}= a^{\frac{13-1}{2}}=a^6\equiv -1 \pmod{13}</math> gilt. Man probiert also alle Zahlen durch, bis man ein geeignetes <math>a</math> findet:
:::<math>
\begin{align}
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{align}
</math>
: Somit hat man gleich am Anfang schon ein geeignetes <math>a=2</math> gefunden, das den Beweis erbringt, dass <math>N=13</math> eine Prothsche Primzahl ist. Auch <math>a=5, 6, 7, 8, 11</math> sind geeignete Zahlen für diesen Beweis.

'''Beispiel 2:''' (Primzahl, aber keine Prothsche Primzahl)

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

'''Beispiel 3:''' (keine Primzahl)

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

: <math>N=81</math> ist eine Prothsche Primzahl, wenn eine natürliche Zahl <math>a \in \mathbb N</math> existiert, sodass <math>a^{\frac{N-1}{2}}= a^{\frac{81-1}{2}}=a^{40}\equiv -1 \pmod{81}</math> gilt. Man probiert also wieder alle Zahlen durch, bis man ein geeignetes <math>a</math> findet:
:::<math>
\begin{align}
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{align}
</math>
: Analog findet man auch bei allen anderen <math>a</math> kein geeignetes, das die Bedingung <math> a^{\frac{81-1}{2}} \equiv -1 \pmod{81}</math> erfüllt. Natürlich gibt es Rechenregeln für die [[Division mit Rest#Modulo|Modulorechnungen]], sodass man hohe Zahlen umgehen kann.
: Somit hat man den Beweis erbracht, dass <math>N=81</math> ''keine'' Prothsche Primzahl ist (was eigentlich von vornherein klar war, da <math>N=3 \cdot 3 \cdot 3 \cdot 3</math> ist).

== Größte bekannte Proth-Primzahlen ==
Die drei größten derzeit bekannten Proth-Primzahlen sind:<ref>Chris Caldwell, [https://primes.utm.edu/top20/page.php?id=66 The Top Twenty: Proth]</ref>

{| class="wikitable"
|- class="hintergrundfarbe6"
! Rang || Primzahl || Dezimal- stellen || weitere Eigenschaften || Entdeckungs- datum || Entdecker || Projekt || Quelle
|-
|style="text-align:center"| 1
|style="text-align:right"| <math>10223 \cdot 2^{31172165} + 1</math>
|style="text-align:center"| 9.383.761
| größte Primzahl, die nicht zugleich [[Mersenne-Primzahl]] ist<ref>Chris Caldwell, [https://primes.utm.edu/top20/page.php?id=3 The Top Twenty: Largest Known Primes]</ref> Nachweis, dass <math>k=10223</math> keine [[Sierpiński-Zahl]] ist
|style="text-align:right"| 31. Okt. 2016
| style="max-width:100px;" | Péter Szabolcs ([[Ungarn|HUN]])
| [[Seventeen or Bust]]
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=122473 10223 · 231172165 + 1 auf Prime Pages]</ref><ref>[https://www.primegrid.com/download/SOB-31172165.pdf 10223 · 231172165 + 1 auf primegrid.com] (PDF)</ref>
|-
|style="text-align:center"| 2
|style="text-align:right"| <math>202705 \cdot 2^{21320516} + 1</math>
|style="text-align:center"| 6.418.121
| Nachweis, dass <math>k=202705</math> nicht die zweitkleinste Sierpiński-Zahl, also keine Lösung des [[Sierpiński-Zahl#Sierpiński-Problem|erweiterten Sierpiński-Problems]] ist
|style="text-align:right"| 25. Nov. 2021
| Pavel Atnashev ([[Russland|RUS]])
| [[Seventeen or Bust#Erweitertes Sierpiński-Problem|Extended Sierpinski Problem]]<ref>[https://www.primegrid.com/forum_thread.php?id=5758 Welcome to the Extended Sierpinski Problem]</ref>
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=133011 202705 · 221320516 + 1 auf Prime Pages]</ref><ref>[https://www.primegrid.com/download/ESP-202705.pdf 202705 · 221320516 + 1 auf primegrid.com] (PDF)</ref>
|-
|style="text-align:center"| 3
|style="text-align:right"| <math>168451 \cdot 2^{19375200} + 1</math>
|style="text-align:center"| 5.832.522
| Nachweis, dass <math>k=168451</math> keine [[Sierpiński-Zahl#Sierpiński-Problem|prime Sierpiński-Zahl]] ist
|style="text-align:right"| 17. Sep. 2017
| Ben Maloney ([[Australien|AUS]])
| [[Seventeen or Bust#Prime-Sierpiński-Problem|Prime Sierpinski Project]]
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=123905 168451 · 219375200 + 1 auf Prime Pages]</ref><ref>[https://www.primegrid.com/download/PSP_168451.pdf 168451 · 219375200 + 1 auf primegrid.com] (PDF)</ref>
|}

== Literatur ==
* {{Literatur
|Autor=[[Hans Riesel]]
|Titel=Prime Numbers and Computer Methods for Factorization
|TitelErg=Reprint of the 1994 Edition
|Reihe=Progress in Mathematics
|BandReihe=126
|Verlag=[[Birkhäuser]]
|Ort=Boston
|Datum=2017
|ISBN=978-0-8176-8297-2
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=1994&co4=AND&co5=AND&co6=AND&co7=AND&dr=pubyear&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Riesel&s5=&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=2&mx-pid=1292250 MR1292250]}}

== Weblinks ==
*{{MathWorld|ProthPrime|Proth Prime}}
* [https://primes.utm.edu/programs/gallot/index.html#download Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows] – Programm von Yves Gallot
* [http://www.prothsearch.com/ Proth Search Page]
* Chris Caldwell: [https://primes.utm.edu/glossary/page.php?sort=ProthPrime Proth prime] auf ''The Prime Pages''
* [http://www.prothsearch.com/riesel1.html List of primes k · 2n + 1 for k < 300]
* [http://www.prothsearch.com/riesel1a.html List of primes k · 2n + 1 for 300 < k < 600]
* [http://www.seventeenorbust.com/ Startseite] des Internet-Projektes “Seventeen or Bust”
* {{PlanetMath
| id = prothprime
| title = Proth prime
}}

== Anmerkungen ==
<references group="A" />

== Einzelnachweise ==
<references />

{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheorie]]

[[fi:Prothin teoreema]]
[[it:Teorema di Proth]]
[[ko:프로트의 정리]]
[[vi:Kiểm tra Proth]]

Prothsche Primzahl - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https