Prothsche Primzahl

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 <math>\ k\cdot 2^n \, + 1\ </math>, wobei <math>k</math> und <math>n</math> positive natürliche Zahlen sind und <math>k</math> eine ungerade Zahl ist, welche zugleich kleiner als die 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 Proth-Zahlen dagegen 9, 25 und 33.

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>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://primes.utm.edu/programs/gallot/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows}}}}|[{{#invoke:URLutil|getNormalized|1=https://primes.utm.edu/programs/gallot/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://primes.utm.edu/programs/gallot/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://primes.utm.edu/programs/gallot/}}%7C%7C URL ungültig}}}}{{#if:Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows|{{#if:{{#invoke:WLink|isValidLinktext|1=Yves Gallot’s Proth.exe: an implementation of Proth’s Theorem for Windows|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:178105||(?)}}}}}}{{#if: 2015-12-05|;}}}}{{#if: 2015-12-05| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2015-12-05 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2015-12-05|class=Zitationswartung}} }} {{#invoke:DateTime|format|2015-12-05|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2015-12-05 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://primes.utm.edu/programs/gallot/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://primes.utm.edu/programs/gallot/
      | {{#if:{{#invoke:URLutil|isWebURL|https://primes.utm.edu/programs/gallot/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://primes.utm.edu/programs/gallot/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://primes.utm.edu/programs/gallot/
       | {{#if:{{#invoke:URLutil|isWebURL|https://primes.utm.edu/programs/gallot/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://primes.utm.edu/programs/gallot/ }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://primes.utm.edu/programs/gallot/
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://primes.utm.edu/programs/gallot/
      | {{#if:{{#invoke:URLutil|isWebURL|https://primes.utm.edu/programs/gallot/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://primes.utm.edu/programs/gallot/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://primes.utm.edu/programs/gallot/
       | {{#if:{{#invoke:URLutil|isWebURL|https://primes.utm.edu/programs/gallot/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://primes.utm.edu/programs/gallot/ }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</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-Zahlen 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-Primzahlen (C₁ = 3, C₁₄₁ = <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 Fermatsche Primzahlen.

Primzahlen <math>N</math> nach <math>k</math> geordnet (Primzahlen mit <math>k > 2^n\ </math>, die damit keine Proth-Zahlen sind, kursiv und in Klammern)
k	Form	Primzahlen dieser Form	Folge	{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate\|Execute}}\|Vorlage:FormatDate/Wartung/Error}}\| \|}}}}{{#if:\|{{{autor}}}: }}{{#if:\|{{#if:Liste von Primzahlen nach k geordnet für k < 300\|[{{#invoke:Vorlage:Internetquelle\|archivURL\|1={{#invoke:URLutil\|getNormalized\|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle\|TitelFormat\|titel=Liste von Primzahlen nach k geordnet für k < 300}}]{{#if:\| ({{{format}}})}}{{#if:\| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle\|Endpunkt\|titel={{{titelerg}}}}}}}}}\|{{#if:http://www.prothsearch.com/riesel1.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Liste von Primzahlen nach k geordnet für k < 300}}}}\|[{{#invoke:URLutil\|getNormalized\|1=http://www.prothsearch.com/riesel1.html}} {{#invoke:Vorlage:Internetquelle\|TitelFormat\|titel={{#invoke:WLink\|getEscapedTitle\|1=Liste von Primzahlen nach k geordnet für k < 300}}}}]}}{{#if:\| ({{{format}}}{{#if:{{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}	1}}}}	)	de	1}}}}\| ;	{{{titelerg}}}{{#invoke:Vorlage:Internetquelle\|Endpunkt\|titel={{{titelerg}}}}}}}}}}}{{#if:http://www.prothsearch.com/riesel1.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://www.prothsearch.com/riesel1.html}}	URL ungültig}}}}{{#if:Liste von Primzahlen nach k geordnet für k < 300\|{{#if:{{#invoke:WLink\|isValidLinktext\|1=Liste von Primzahlen nach k geordnet für k < 300\|lines=0}}	Linktext ungültig}}}}{{#if: \| In: {{#invoke:Vorlage:Internetquelle\|TitelFormat\|titel={{{werk}}}}}}}{{#if: \| {{{hrsg}}}{{#if: \|,\|{{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}\|;\|,}}}}}}}}{{#if: \| {{#if:{{#invoke:DateTime\|format\|{{{datum}}}\|noerror=1}}	format\|{{{datum}}}\|T._Monat JJJJ}}	failure\|1=Fehler bei Vorlage:Internetquelle, `datum={{{datum}}}`\|class=Zitationswartung}} }}{{#if: \|,\|{{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}\|;\|,}}}}}}}}{{#if: \| S. {{{seiten}}}{{#if: \|,\|{{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}\|;\|,}}}}}}}}{{#if: {{#invoke:TemplUtl\|faculty\|}}\| {{#if:\|{{#if:\|archiviert\|ehemals}}\|{{#if:\|Archiviert\|Ehemals}}}} {{#if:\|vom\|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl\|faculty\|}}\| (nicht mehr online verfügbar)}}{{#if: \| am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate\|Execute}}\|Vorlage:FormatDate/Wartung/Error}}\|{{{archiv-datum}}}{{#if:178105	;}}}}{{#if: 2015-12-05\| {{#if:{{#invoke:TemplUtl\|faculty\|}}\|abgerufen\|Abgerufen}} {{#switch: {{#invoke:Str\|len\| {{#invoke:DateTime\|format\| 2015-12-05 \|ISO\|noerror=1}} }}	4=im Jahr	7=im	10=am	failure\|1=Fehler bei Vorlage:Internetquelle, `abruf=2015-12-05`\|class=Zitationswartung}} }} {{#invoke:DateTime\|format\|2015-12-05\|T._Monat JJJJ}}	failure\|1=Vorlage:Internetquelle \| `abruf=`2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de\|de	1}}}}\|{{#if:{{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}	1}}}}	(	\| (}} }}{{#ifeq:{{#if:de\|de\|de}}\|de\|\| {{#invoke:Multilingual\|format\|{{{sprache}}}\|slang=!\|split=[%s,]+\|shift=m\|separator=, }}}}{{#if: \|{{#ifeq:{{#if:de\|de\|de}}\|de\|\|, }}{{{kommentar}}}}})}}{{#if: {{#if: 2015-12-05 \| {{#if:{{#invoke:TemplUtl\|faculty\|}}\|\|1}} }}\|{{#if: \|: {{ #if:	„{{ #ifeq: {{#if:{{#if: {{#invoke:templutl\|faculty\|}}\|de-ch\|de}}\|{{#if: {{#invoke:templutl\|faculty\|}}\|de-ch\|de}}\|de}} \| de	Vorlage:Str trim	flat}} }}“	faculty\|}}\|de-ch\|de}}\|{{#if: {{#invoke:templutl\|faculty\|}}\|de-ch\|de}}\|de}} \| de	„Vorlage:Str trim“	quote	1={{#if:	flat}}	flat}} }}	faculty\|}}\|de-CH\|de}}	3=1}} }} }}{{#if:	: }}{{#if: \| , deutsch: „“ }})	{{#if:	, deutsch: „“ }})	(deutsch: „“) }} }} }}{{#if: {{{zitat}}}	{{#if:	{{#if: {{{zitat}}}	Vorlage:": `Text=` und `1=` gleichzeitig, bzw. Pipe zu viel }} }}	Vorlage:": `Text=` fehlt }}{{#if: \| {{#if: {{#invoke:Text\|unstrip\|{{{ref}}}}}	Vorlage:": Ungültiger Wert: `ref=`	{{{ref}}} }} }}\|.{{#if:{{#invoke:TemplUtl\|faculty\|}}\|{{#if:\|\|{{#ifeq: \| JaKeinHinweis \|{{#switch:	=Vorlage:Toter Link/Core{{#if: http://www.prothsearch.com/riesel1.html	[3] }} (Seite {{#switch:\|no\|0\|=\|dauerhaft }}nicht mehr abrufbar{{#if: \| , festgestellt im {{#invoke:DateTime\|format	F Y}} }}. Suche im Internet Archive (T)){{#if:	\| Vorlage:Toter Link/archivebot }} }}	(Seite {{#switch:\|no\|0\|=\|#default=dauerhaft }}nicht mehr abrufbar{{#if: \| , festgestellt im {{#invoke:DateTime\|format	F Y}} }}.) }}{{#switch:	0\|=	#default={{#if:	}} }}{{#invoke:TemplatePar\|check	opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=	cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link	errNS = 0	template = Vorlage:Toter Link	format = @@@	preview = 1 }}{{#if: http://www.prothsearch.com/riesel1.html	isWebURL\|http://www.prothsearch.com/riesel1.html}}	{{#if:	}} }}	{{#if:	{{#if:	}}	{{#if:	}} }} }}{{#if:	format	noerror=1}}	{{#if:	}} }} }}{{#switch: deadurl	deadurl\|=	#default= {{#if:	}} }}\|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.prothsearch.com/riesel1.html Die nachstehende Seite ist {{#switch:\|no\|0\|=\|dauerhaft }}nicht mehr abrufbar]{{#if: \| , festgestellt im {{#invoke:DateTime\|format\|\|F Y}} }}. (Suche im Internet Archive. (T).) {{#if:	\| Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch:	0\|=	#default= {{#if:	}} }}{{#invoke:TemplatePar\|check	all = inline= url=	opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked=	cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link	errNS = 0	template = Vorlage:Toter Link	format = @@@	preview = 1 }}{{#if: http://www.prothsearch.com/riesel1.html	isWebURL\|http://www.prothsearch.com/riesel1.html}}	{{#if:	}} }} }}{{#if:	format	noerror=1}}	{{#if:	}} }} }}{{#switch: deadurl	deadurl\|=	#default= {{#if:	}} }}[http://www.prothsearch.com/riesel1.html }}\|{{#switch:	=Vorlage:Toter Link/Core{{#if: http://www.prothsearch.com/riesel1.html	[4] }} (Seite {{#switch:\|no\|0\|=\|dauerhaft }}nicht mehr abrufbar{{#if: \| , festgestellt im {{#invoke:DateTime\|format	F Y}} }}. Suche im Internet Archive (T)){{#if:	\| Vorlage:Toter Link/archivebot }} }}	(Seite {{#switch:\|no\|0\|=\|#default=dauerhaft }}nicht mehr abrufbar{{#if: \| , festgestellt im {{#invoke:DateTime\|format	F Y}} }}.) }}{{#switch:	0\|=	#default={{#if:	}} }}{{#invoke:TemplatePar\|check	opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=	cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link	errNS = 0	template = Vorlage:Toter Link	format = @@@	preview = 1 }}{{#if: http://www.prothsearch.com/riesel1.html	isWebURL\|http://www.prothsearch.com/riesel1.html}}	{{#if:	}} }}	{{#if:	{{#if:	}}	{{#if:	}} }} }}{{#if:	format	noerror=1}}	{{#if:	}} }} }}{{#switch:	deadurl\|=	#default= {{#if:	}} }}\|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.prothsearch.com/riesel1.html Die nachstehende Seite ist {{#switch:\|no\|0\|=\|dauerhaft }}nicht mehr abrufbar]{{#if: \| , festgestellt im {{#invoke:DateTime\|format\|\|F Y}} }}. (Suche im Internet Archive. (T).) {{#if:	\| Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch:	0\|=	#default= {{#if:	}} }}{{#invoke:TemplatePar\|check	all = inline= url=	opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked=	cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link	errNS = 0	template = Vorlage:Toter Link	format = @@@	preview = 1 }}{{#if: http://www.prothsearch.com/riesel1.html	isWebURL\|http://www.prothsearch.com/riesel1.html}}	{{#if:	}} }} }}{{#if:	format	noerror=1}}	{{#if:	}} }} }}{{#switch:	deadurl\|=	#default= {{#if:	}} }}[http://www.prothsearch.com/riesel1.html }} }}}}}}}}}}{{#if:\| {{#invoke:Vorlage:Internetquelle\|archivBot\|stamp={{{archiv-bot}}}\|text={{#if:\|Vorlage:Webarchiv/archiv-bot}} }}}} {{#invoke:TemplatePar\|check	all= url= titel=	opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline=	0 \| Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}}	template= Vorlage:Internetquelle	format=0	preview=1 }}</ref> \|\| Folge
01	<math>1 \cdot 2^n+1</math>	3, 5, 17, 257, 65537 (keine weiteren bekannt)	Folge A019434 in OEIS	1, 2, 4, 8, 16 (keine weiteren bekannt)	–
03	<math>3 \cdot 2^n+1</math>	(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	<math>5 \cdot 2^n+1</math>	(11), 41, 641, 163841, …	–	(1), 3, 7, 13, 15, 25, 39, 55, 75, 85, …	Folge A002254 in OEIS
07	<math>7 \cdot 2^n+1</math>	(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	<math>9 \cdot 2^n+1</math>	(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	<math>11 \cdot 2^n+1</math>	(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	<math>13 \cdot 2^n+1</math>	(53), 3329, 13313, 13631489, 3489660929, …	Folge A300406 in OEIS	(2), 8, 10, 20, 28, 82, 188, 308, 316, …	Folge A032356 in OEIS
15	<math>15 \cdot 2^n+1</math>	(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	<math>17 \cdot 2^n+1</math>	(137), 557057, 2281701377, …	Folge A300407 in OEIS	(3), 15, 27, 51, 147, 243, 267, 347, …	Folge A002259 in OEIS
19	<math>19 \cdot 2^n+1</math>	1217, 19457, 1337006139375617, …	Folge A300408 in OEIS	6, 10, 46, 366, 1246, 2038, 4386, …	Folge A032359 in OEIS
21	<math>21 \cdot 2^n+1</math>	(43), (337), 673, 2689, 10753, …	–	(1), (4), 5, 7, 9, 12, 16, 17, 41, 124, …	Folge A032360 in OEIS
23	<math>23 \cdot 2^n+1</math>	(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

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 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, The Top Twenty: Proth</ref>

Rang	Primzahl	Dezimal- stellen	weitere Eigenschaften	Entdeckungs- datum	Entdecker	Projekt	Quelle
1	<math>10223 \cdot 2^{31172165} + 1</math>	9.383.761	größte Primzahl, die nicht zugleich Mersenne-Primzahl ist<ref>Chris Caldwell, The Top Twenty: Largest Known Primes</ref> Nachweis, dass <math>k=10223</math> keine Sierpiński-Zahl ist	31. Okt. 2016	Péter Szabolcs (HUN)	Seventeen or Bust	<ref>10223 · 2^31172165 + 1 auf Prime Pages</ref><ref>10223 · 2^31172165 + 1 auf primegrid.com (PDF)</ref>
2	<math>202705 \cdot 2^{21320516} + 1</math>	6.418.121	Nachweis, dass <math>k=202705</math> 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<ref>Welcome to the Extended Sierpinski Problem</ref>	<ref>202705 · 2^21320516 + 1 auf Prime Pages</ref><ref>202705 · 2^21320516 + 1 auf primegrid.com (PDF)</ref>
3	<math>168451 \cdot 2^{19375200} + 1</math>	5.832.522	Nachweis, dass <math>k=168451</math> keine prime Sierpiński-Zahl ist	17. Sep. 2017	Ben Maloney (AUS)	Prime Sierpinski Project	<ref>168451 · 2^19375200 + 1 auf Prime Pages</ref><ref>168451 · 2^19375200 + 1 auf primegrid.com (PDF)</ref>

Literatur

{{#invoke:Vorlage:Literatur|f}}

Weblinks

{{#if: | {{{author}}} | Eric W. Weisstein }}: Proth Prime. In: MathWorld (englisch). {{#if: | {{#ifeq: {{#property:P2812}} | {{{id}}} | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
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”
{{#if: |{{{author}}}: }}Proth prime. In: PlanetMath. (englisch)

Anmerkungen

Einzelnachweise

Vorlage:Navigationsleiste Primzahlklassen

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