Eine Sierpiński-Zahl (benannt nach dem polnischen Mathematiker Wacław Sierpiński) ist eine natürliche, ungerade Zahl , für die die unendliche Zahlenfolge mit keine Primzahlen enthält.
Beispiele Bearbeiten
- ist eine Sierpiński-Zahl.
Beweis der Behauptung, dass 78557 eine Sierpiński-Zahl ist:
Der Beweis funktioniert direkt mittels Modulo-Rechnung.
Zu zeigen ist, dass für alle natürlichen Zahlen immer eine zusammengesetzte Zahl, also niemals eine Primzahl, ist.
Es wird gezeigt, dass es immer eine Zahl aus der Menge gibt, welche teilt (diese Menge nennt man im englischen covering set of 78557).
Beweis:
- Die folgenden Zahlen sind bekannte Sierpiński-Zahlen :
Gegenbeispiel Bearbeiten
Die Zahl ist keine Sierpiński-Zahl, da in der Folge wenigstens eine Primzahl auftritt: 39, 77, 153, 305, 609, 1217, 2433, … Das sechste Glied der Folge, 1217, ist eine Primzahl. Das genügt zum Nachweis, dass 19 keine Sierpiński-Zahl ist. Ob noch weitere Primzahlen in dieser Folge auftreten oder nicht (das zehnte Glied 19457 ist prim), ist unerheblich.
Primzahlen der Form nennt man Prothsche Primzahl.
Sierpiński-Problem Bearbeiten
Das Sierpiński-Problem lautet: Welche ist die kleinste Sierpiński-Zahl? 1962 hat John L. Selfridge gezeigt, dass 78557 eine Sierpiński-Zahl ist. Es ist jedoch noch nicht bekannt, ob 78557 die kleinste Sierpiński-Zahl ist. Es wird aber vermutet, dass es sich um die kleinste Sierpiński-Zahl handelt. Das Internet-Projekt Seventeen or Bust beschäftigt sich mit diesem Problem.
Um den Beweis durchzuführen, muss für jedes kleiner als 78557 eine Zahl gefunden werden, so dass die resultierende Proth-Zahl eine Primzahl ist. Dieser Beweis ist (Stand 8. Juli 2019) bereits für alle bis auf 5 Ausnahmen erfolgt, diese sind (Primzahlen werden fett geschrieben):
Die möglicherweise kleinste Sierpiński-Zahl ist eine zusammengesetzte Zahl.
Das prime Sierpiński-Problem beschäftigt sich damit, ob die kleinste prime Sierpiński-Zahl ist. Um dies zu überprüfen, müssen die folgenden 9 Primzahlen überprüft werden (wobei die ersten zwei Zahlen der folgenden Liste schon in obigem Problem auftauchen; die übrigen drei Zahlen der vorhergehenden Liste sind keine Primzahlen: , und ) (Stand: 31. Dezember 2019):
Das erweiterte Sierpiński-Problem beschäftigt sich damit, ob tatsächlich die zweitkleinste Sierpiński-Zahl ist. Um dies zu überprüfen, müssen neben den 9 oben genannten Primzahlen (vom primen Sierpiński-Problem) noch zusätzlich die folgenden 11 zusammengesetzten Zahlen überprüft werden (wobei die ersten drei zusammengesetzten Zahlen schon im ursprünglichen Sierpiński-Problem auftauchen) (Stand: 7. März 2022):
Riesel-Zahl Bearbeiten
Eine Riesel-Zahl (benannt nach dem schwedischen Mathematiker Hans Riesel) ist eine natürliche, ungerade Zahl , für die die unendliche Zahlenfolge mit keine Primzahlen enthält.
Beispiele Bearbeiten
- ist eine Riesel-Zahl.
Beweis der Behauptung, dass 509203 eine Riesel-Zahl ist:
Der Beweis funktioniert direkt mittels Modulo-Rechnung.
Zu zeigen ist, dass für alle natürlichen Zahlen immer eine zusammengesetzte Zahl, also niemals eine Primzahl, ist.
Es wird gezeigt, dass es immer eine Zahl aus der Menge gibt, welche teilt (diese Menge nennt man im englischen covering set of 509203).
Beweis:
- Teil 6: Teilbarkeit durch 241:
- Es ist . Somit gilt:
- teilt
Veröffentlichungsdatum:
Dieser Artikel beschaftigt sich mit den Sierpinski Zahlen Fur die nach Sierpinski benannte Konstante siehe Sierpinski Konstante Eine Sierpinski Zahl benannt nach dem polnischen Mathematiker Waclaw Sierpinski ist eine naturliche ungerade Zahl k displaystyle k fur die die unendliche Zahlenfolge k x22C5 2 n 1 displaystyle k cdot 2 n 1 mit n x2265 1 displaystyle n geq 1 keine Primzahlen enthalt Inhaltsverzeichnis 1 Beispiele 2 Gegenbeispiel 3 Sierpinski Problem 4 Riesel Zahl 4 1 Beispiele 4 2 Gegenbeispiel 4 3 Die kleinste Riesel Zahl 5 Brier Zahl 6 Duales Sierpinski Problem 7 Gerades Sierpinski Problem 8 Duales Riesel Problem 8 1 Fall 1 2n k lt 0 ist erlaubt 8 2 Fall 2 2n k lt 0 ist nicht erlaubt 9 Gerades Riesel Problem 10 Wie schnell findet man eine Primzahl fur ein gegebenes k 11 Sierpinski Zahlen zur Basis b 11 1 Bedingung 11 2 Tabelle der Sierpinski Zahlen zur Basis b 12 Riesel Zahlen zur Basis b 12 1 Bedingung 12 2 Tabelle der Riesel Zahlen zur Basis b 13 Weblinks 14 Einzelnachweise Beispiele Bearbeiten k 78557 displaystyle k 78557 ist eine Sierpinski Zahl Beweis der Behauptung dass 78557 eine Sierpinski Zahl ist Der Beweis funktioniert direkt mittels Modulo Rechnung 91 1 93 Zu zeigen ist dass 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 fur alle naturlichen Zahlen n x2208 N x2216 0 displaystyle n in mathbb N backslash 0 immer eine zusammengesetzte Zahl also niemals eine Primzahl ist Es wird gezeigt dass es immer eine Zahl aus der Menge 3 5 7 13 19 37 73 displaystyle 3 5 7 13 19 37 73 gibt welche 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 teilt diese Menge nennt man im englischen covering set of 78557 Beweis Teil 1 Teilbarkeit durch 3 Es ist 78557 26185 x22C5 3 2 x2261 2 mod 3 displaystyle 78557 26185 cdot 3 2 equiv 2 pmod 3 Somit gilt 3 displaystyle 3 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 3 mod 3 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 3 pmod 3 genau dann wenn 78557 x22C5 2 n x2261 2 mod 3 displaystyle 78557 cdot 2 n equiv 2 pmod 3 genau dann wenn 2 x22C5 2 n x2261 2 mod 3 displaystyle 2 cdot 2 n equiv 2 pmod 3 genau dann wenn 2 n x2261 1 mod 3 displaystyle 2 n equiv 1 pmod 3 ist Es ist also 3 displaystyle 3 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 1 mod 3 displaystyle 2 n equiv 1 pmod 3 ist Es gilt 2 1 2 x2261 2 x005F mod 3 2 2 4 x2261 1 x005F mod 3 2 3 8 x2261 2 x005F mod 3 2 4 16 x2261 1 x005F mod 3 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 3 2 2 amp amp 4 amp equiv amp underline 1 pmod 3 2 3 amp amp 8 amp equiv amp underline 2 pmod 3 2 4 amp amp 16 amp equiv amp underline 1 pmod 3 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 3 displaystyle 3 immer einen Zykel der Lange 2 displaystyle 2 der Form 2 1 displaystyle 2 1 Es ist also 2 n x2261 1 mod 3 displaystyle 2 n equiv 1 pmod 3 genau dann wenn n displaystyle n gerade ist also wenn n x2261 0 mod 2 displaystyle n equiv 0 pmod 2 ist dd 3 displaystyle 3 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 0 mod 2 displaystyle n equiv 0 pmod 2 ist dd Teil 2 Teilbarkeit durch 5 Es ist 78557 15711 x22C5 5 2 x2261 2 mod 5 displaystyle 78557 15711 cdot 5 2 equiv 2 pmod 5 Somit gilt 5 displaystyle 5 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 5 mod 5 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 5 pmod 5 genau dann wenn 78557 x22C5 2 n x2261 4 mod 5 displaystyle 78557 cdot 2 n equiv 4 pmod 5 genau dann wenn 2 x22C5 2 n x2261 4 mod 5 displaystyle 2 cdot 2 n equiv 4 pmod 5 genau dann wenn 2 n x2261 2 mod 5 displaystyle 2 n equiv 2 pmod 5 ist Es ist also 5 displaystyle 5 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 2 mod 5 displaystyle 2 n equiv 2 pmod 5 ist Es gilt 2 1 2 x2261 2 x005F mod 5 2 2 4 x2261 4 x005F mod 5 2 3 8 x2261 3 x005F mod 5 2 4 16 x2261 1 x005F mod 5 2 5 32 x2261 2 x005F mod 5 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 5 2 2 amp amp 4 amp equiv amp underline 4 pmod 5 2 3 amp amp 8 amp equiv amp underline 3 pmod 5 2 4 amp amp 16 amp equiv amp underline 1 pmod 5 2 5 amp amp 32 amp equiv amp underline 2 pmod 5 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 5 displaystyle 5 immer einen Zykel der Lange 4 displaystyle 4 der Form 2 4 3 1 displaystyle 2 4 3 1 Es ist also 2 n x2261 2 mod 5 displaystyle 2 n equiv 2 pmod 5 genau dann wenn n x2261 1 mod 4 displaystyle n equiv 1 pmod 4 ist dd 5 displaystyle 5 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 1 mod 4 displaystyle n equiv 1 pmod 4 ist dd Teil 3 Teilbarkeit durch 7 Es ist 78557 11222 x22C5 7 3 x2261 3 mod 7 displaystyle 78557 11222 cdot 7 3 equiv 3 pmod 7 Somit gilt 7 displaystyle 7 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 7 mod 7 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 7 pmod 7 genau dann wenn 78557 x22C5 2 n x2261 6 mod 7 displaystyle 78557 cdot 2 n equiv 6 pmod 7 genau dann wenn 3 x22C5 2 n x2261 6 mod 7 displaystyle 3 cdot 2 n equiv 6 pmod 7 genau dann wenn 2 n x2261 2 mod 7 displaystyle 2 n equiv 2 pmod 7 ist Es ist also 7 displaystyle 7 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 2 mod 7 displaystyle 2 n equiv 2 pmod 7 ist Es gilt 2 1 2 x2261 2 x005F mod 7 2 2 4 x2261 4 x005F mod 7 2 3 8 x2261 1 x005F mod 7 2 4 16 x2261 2 x005F mod 7 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 7 2 2 amp amp 4 amp equiv amp underline 4 pmod 7 2 3 amp amp 8 amp equiv amp underline 1 pmod 7 2 4 amp amp 16 amp equiv amp underline 2 pmod 7 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 7 displaystyle 7 immer einen Zykel der Lange 3 displaystyle 3 der Form 2 4 1 displaystyle 2 4 1 Es ist also 2 n x2261 2 mod 7 displaystyle 2 n equiv 2 pmod 7 genau dann wenn n x2261 1 mod 3 displaystyle n equiv 1 pmod 3 ist dd 7 displaystyle 7 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 1 mod 3 displaystyle n equiv 1 pmod 3 ist dd Teil 4 Teilbarkeit durch 13 Es ist 78557 6042 x22C5 13 11 x2261 11 mod 13 displaystyle 78557 6042 cdot 13 11 equiv 11 pmod 13 Somit gilt 13 displaystyle 13 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 13 mod 13 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 13 pmod 13 genau dann wenn 78557 x22C5 2 n x2261 12 mod 13 displaystyle 78557 cdot 2 n equiv 12 pmod 13 genau dann wenn 11 x22C5 2 n x2261 12 mod 13 displaystyle 11 cdot 2 n equiv 12 pmod 13 Multipliziert man diese Modulo Rechnung mit der Inversen von 11 displaystyle 11 modulo 13 displaystyle 13 namlich mit 6 displaystyle 6 es ist 11 x22C5 6 66 x2261 1 mod 13 displaystyle 11 cdot 6 66 equiv 1 pmod 13 so erhalt man 66 x22C5 2 n x2261 72 mod 13 displaystyle 66 cdot 2 n equiv 72 pmod 13 was gleichwertig ist mit 1 x22C5 2 n x2261 7 mod 13 displaystyle 1 cdot 2 n equiv 7 pmod 13 Es ist also 13 displaystyle 13 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 7 mod 13 displaystyle 2 n equiv 7 pmod 13 ist Es gilt 2 1 2 x2261 2 x005F mod 13 2 2 4 x2261 4 x005F mod 13 2 3 8 x2261 8 x005F mod 13 2 4 16 x2261 3 x005F mod 13 2 5 32 x2261 6 x005F mod 13 2 6 64 x2261 12 x005F mod 13 2 7 128 x2261 11 x005F mod 13 2 8 256 x2261 9 x005F mod 13 2 9 512 x2261 5 x005F mod 13 2 10 1024 x2261 10 x005F mod 13 2 11 2048 x2261 7 x005F mod 13 2 12 4096 x2261 1 x005F mod 13 2 13 8192 x2261 2 x005F mod 13 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 13 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 13 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 13 2 4 amp amp 16 amp equiv amp underline 3 amp pmod 13 2 5 amp amp 32 amp equiv amp underline 6 amp pmod 13 2 6 amp amp 64 amp equiv amp underline 12 amp pmod 13 2 7 amp amp 128 amp equiv amp underline 11 amp pmod 13 2 8 amp amp 256 amp equiv amp underline 9 amp pmod 13 2 9 amp amp 512 amp equiv amp underline 5 amp pmod 13 2 10 amp amp 1024 amp equiv amp underline 10 amp pmod 13 2 11 amp amp 2048 amp equiv amp underline 7 amp pmod 13 2 12 amp amp 4096 amp equiv amp underline 1 amp pmod 13 2 13 amp amp 8192 amp equiv amp underline 2 amp pmod 13 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 13 displaystyle 13 immer einen Zykel der Lange 12 displaystyle 12 der Form 2 4 8 3 6 12 11 9 5 10 7 1 displaystyle 2 4 8 3 6 12 11 9 5 10 7 1 Es ist also 2 n x2261 7 mod 13 displaystyle 2 n equiv 7 pmod 13 genau dann wenn n x2261 11 mod 12 displaystyle n equiv 11 pmod 12 ist dd 13 displaystyle 13 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 11 mod 12 displaystyle n equiv 11 pmod 12 ist dd Teil 5 Teilbarkeit durch 19 Es ist 78557 4134 x22C5 19 11 x2261 11 mod 19 displaystyle 78557 4134 cdot 19 11 equiv 11 pmod 19 Somit gilt 19 displaystyle 19 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 19 mod 19 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 19 pmod 19 genau dann wenn 78557 x22C5 2 n x2261 18 mod 19 displaystyle 78557 cdot 2 n equiv 18 pmod 19 genau dann wenn 11 x22C5 2 n x2261 18 mod 19 displaystyle 11 cdot 2 n equiv 18 pmod 19 Multipliziert man diese Modulo Rechnung mit der Inversen von 11 displaystyle 11 modulo 19 displaystyle 19 namlich mit 7 displaystyle 7 es ist 11 x22C5 7 77 x2261 1 mod 19 displaystyle 11 cdot 7 77 equiv 1 pmod 19 so erhalt man 77 x22C5 2 n x2261 126 mod 19 displaystyle 77 cdot 2 n equiv 126 pmod 19 was gleichwertig ist mit 1 x22C5 2 n x2261 12 mod 19 displaystyle 1 cdot 2 n equiv 12 pmod 19 Es ist also 19 displaystyle 19 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 12 mod 19 displaystyle 2 n equiv 12 pmod 19 ist Es gilt 2 1 2 x2261 2 x005F mod 19 2 2 4 x2261 4 x005F mod 19 2 3 8 x2261 8 x005F mod 19 2 4 16 x2261 16 x005F mod 19 2 5 32 x2261 13 x005F mod 19 2 6 64 x2261 7 x005F mod 19 2 7 128 x2261 14 x005F mod 19 2 8 256 x2261 9 x005F mod 19 2 9 512 x2261 18 x005F mod 19 2 10 1024 x2261 17 x005F mod 19 2 11 2048 x2261 15 x005F mod 19 2 12 4096 x2261 11 x005F mod 19 2 13 8192 x2261 3 x005F mod 19 2 14 16384 x2261 6 x005F mod 19 2 15 32768 x2261 12 x005F mod 19 2 16 65536 x2261 5 x005F mod 19 2 17 131072 x2261 10 x005F mod 19 2 18 262144 x2261 1 x005F mod 19 2 19 524288 x2261 2 x005F mod 19 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 19 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 19 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 19 2 4 amp amp 16 amp equiv amp underline 16 amp pmod 19 2 5 amp amp 32 amp equiv amp underline 13 amp pmod 19 2 6 amp amp 64 amp equiv amp underline 7 amp pmod 19 2 7 amp amp 128 amp equiv amp underline 14 amp pmod 19 2 8 amp amp 256 amp equiv amp underline 9 amp pmod 19 2 9 amp amp 512 amp equiv amp underline 18 amp pmod 19 2 10 amp amp 1024 amp equiv amp underline 17 amp pmod 19 2 11 amp amp 2048 amp equiv amp underline 15 amp pmod 19 2 12 amp amp 4096 amp equiv amp underline 11 amp pmod 19 2 13 amp amp 8192 amp equiv amp underline 3 amp pmod 19 2 14 amp amp 16384 amp equiv amp underline 6 amp pmod 19 2 15 amp amp 32768 amp equiv amp underline 12 amp pmod 19 2 16 amp amp 65536 amp equiv amp underline 5 amp pmod 19 2 17 amp amp 131072 amp equiv amp underline 10 amp pmod 19 2 18 amp amp 262144 amp equiv amp underline 1 amp pmod 19 2 19 amp amp 524288 amp equiv amp underline 2 amp pmod 19 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 19 displaystyle 19 immer einen Zykel der Lange 18 displaystyle 18 der Form 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 displaystyle 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 Es ist also 2 n x2261 12 mod 19 displaystyle 2 n equiv 12 pmod 19 genau dann wenn n x2261 15 mod 18 displaystyle n equiv 15 pmod 18 ist dd 19 displaystyle 19 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 15 mod 18 displaystyle n equiv 15 pmod 18 ist dd Teil 6 Teilbarkeit durch 37 Es ist 78557 2123 x22C5 37 6 x2261 6 mod 37 displaystyle 78557 2123 cdot 37 6 equiv 6 pmod 37 Somit gilt 37 displaystyle 37 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 37 mod 37 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 37 pmod 37 genau dann wenn 78557 x22C5 2 n x2261 36 mod 37 displaystyle 78557 cdot 2 n equiv 36 pmod 37 genau dann wenn 6 x22C5 2 n x2261 36 mod 37 displaystyle 6 cdot 2 n equiv 36 pmod 37 Multipliziert man diese Modulo Rechnung mit der Inversen von 6 displaystyle 6 modulo 37 displaystyle 37 namlich mit 31 displaystyle 31 es ist 6 x22C5 31 186 x2261 1 mod 37 displaystyle 6 cdot 31 186 equiv 1 pmod 37 so erhalt man 186 x22C5 2 n x2261 1116 mod 37 displaystyle 186 cdot 2 n equiv 1116 pmod 37 was gleichwertig ist mit 1 x22C5 2 n x2261 6 mod 37 displaystyle 1 cdot 2 n equiv 6 pmod 37 Es ist also 37 displaystyle 37 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 6 mod 37 displaystyle 2 n equiv 6 pmod 37 ist Es gilt 2 1 2 x2261 2 x005F mod 37 2 2 4 x2261 4 x005F mod 37 2 3 8 x2261 8 x005F mod 37 2 4 16 x2261 16 x005F mod 37 2 5 32 x2261 32 x005F mod 37 2 6 64 x2261 27 x005F mod 37 2 7 128 x2261 17 x005F mod 37 2 8 256 x2261 34 x005F mod 37 2 9 512 x2261 31 x005F mod 37 2 10 1024 x2261 25 x005F mod 37 2 11 2048 x2261 13 x005F mod 37 2 12 4096 x2261 26 x005F mod 37 2 13 8192 x2261 15 x005F mod 37 2 14 16384 x2261 30 x005F mod 37 2 15 32768 x2261 23 x005F mod 37 2 16 65536 x2261 9 x005F mod 37 2 17 131072 x2261 18 x005F mod 37 2 18 262144 x2261 36 x005F mod 37 2 19 524288 x2261 35 x005F mod 37 2 20 1048576 x2261 33 x005F mod 37 2 21 2097152 x2261 29 x005F mod 37 2 22 4194304 x2261 21 x005F mod 37 2 23 8388608 x2261 5 x005F mod 37 2 24 16777216 x2261 10 x005F mod 37 2 25 33554432 x2261 20 x005F mod 37 2 26 67108864 x2261 3 x005F mod 37 2 27 134217728 x2261 6 x005F mod 37 2 28 268435456 x2261 12 x005F mod 37 2 29 536870912 x2261 24 x005F mod 37 2 30 1073741824 x2261 11 x005F mod 37 2 31 2147483648 x2261 22 x005F mod 37 2 32 4294967296 x2261 7 x005F mod 37 2 33 8589934592 x2261 14 x005F mod 37 2 34 17179869184 x2261 28 x005F mod 37 2 35 34359738368 x2261 19 x005F mod 37 2 36 68719476736 x2261 1 x005F mod 37 2 37 137438953472 x2261 2 x005F mod 37 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 37 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 37 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 37 2 4 amp amp 16 amp equiv amp underline 16 amp pmod 37 2 5 amp amp 32 amp equiv amp underline 32 amp pmod 37 2 6 amp amp 64 amp equiv amp underline 27 amp pmod 37 2 7 amp amp 128 amp equiv amp underline 17 amp pmod 37 2 8 amp amp 256 amp equiv amp underline 34 amp pmod 37 2 9 amp amp 512 amp equiv amp underline 31 amp pmod 37 2 10 amp amp 1024 amp equiv amp underline 25 amp pmod 37 2 11 amp amp 2048 amp equiv amp underline 13 amp pmod 37 2 12 amp amp 4096 amp equiv amp underline 26 amp pmod 37 2 13 amp amp 8192 amp equiv amp underline 15 amp pmod 37 2 14 amp amp 16384 amp equiv amp underline 30 amp pmod 37 2 15 amp amp 32768 amp equiv amp underline 23 amp pmod 37 2 16 amp amp 65536 amp equiv amp underline 9 amp pmod 37 2 17 amp amp 131072 amp equiv amp underline 18 amp pmod 37 2 18 amp amp 262144 amp equiv amp underline 36 amp pmod 37 2 19 amp amp 524288 amp equiv amp underline 35 amp pmod 37 2 20 amp amp 1048576 amp equiv amp underline 33 amp pmod 37 2 21 amp amp 2097152 amp equiv amp underline 29 amp pmod 37 2 22 amp amp 4194304 amp equiv amp underline 21 amp pmod 37 2 23 amp amp 8388608 amp equiv amp underline 5 amp pmod 37 2 24 amp amp 16777216 amp equiv amp underline 10 amp pmod 37 2 25 amp amp 33554432 amp equiv amp underline 20 amp pmod 37 2 26 amp amp 67108864 amp equiv amp underline 3 amp pmod 37 2 27 amp amp 134217728 amp equiv amp underline 6 amp pmod 37 2 28 amp amp 268435456 amp equiv amp underline 12 amp pmod 37 2 29 amp amp 536870912 amp equiv amp underline 24 amp pmod 37 2 30 amp amp 1073741824 amp equiv amp underline 11 amp pmod 37 2 31 amp amp 2147483648 amp equiv amp underline 22 amp pmod 37 2 32 amp amp 4294967296 amp equiv amp underline 7 amp pmod 37 2 33 amp amp 8589934592 amp equiv amp underline 14 amp pmod 37 2 34 amp amp 17179869184 amp equiv amp underline 28 amp pmod 37 2 35 amp amp 34359738368 amp equiv amp underline 19 amp pmod 37 2 36 amp amp 68719476736 amp equiv amp underline 1 amp pmod 37 2 37 amp amp 137438953472 amp equiv amp underline 2 amp pmod 37 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 37 displaystyle 37 immer einen Zykel der Lange 36 displaystyle 36 der Form 2 4 8 16 32 27 17 34 31 25 13 26 15 30 23 9 18 36 35 33 29 21 5 10 20 3 6 12 24 11 22 7 14 28 19 1 displaystyle 2 4 8 16 32 27 17 34 31 25 13 26 15 30 23 9 18 36 35 33 29 21 5 10 20 3 6 12 24 11 22 7 14 28 19 1 Es ist also 2 n x2261 6 mod 37 displaystyle 2 n equiv 6 pmod 37 genau dann wenn n x2261 27 mod 36 displaystyle n equiv 27 pmod 36 ist dd 37 displaystyle 37 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 27 mod 36 displaystyle n equiv 27 pmod 36 ist dd Teil 7 Teilbarkeit durch 73 Es ist 78557 1076 x22C5 73 9 x2261 9 mod 73 displaystyle 78557 1076 cdot 73 9 equiv 9 pmod 73 Somit gilt 73 displaystyle 73 teilt 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 78557 x22C5 2 n 1 x2261 0 x2261 73 mod 73 displaystyle 78557 cdot 2 n 1 equiv 0 equiv 73 pmod 73 genau dann wenn 78557 x22C5 2 n x2261 72 mod 73 displaystyle 78557 cdot 2 n equiv 72 pmod 73 genau dann wenn 9 x22C5 2 n x2261 72 mod 73 displaystyle 9 cdot 2 n equiv 72 pmod 73 Multipliziert man diese Modulo Rechnung mit der Inversen von 9 displaystyle 9 modulo 73 displaystyle 73 namlich mit 65 displaystyle 65 es ist 9 x22C5 65 585 x2261 1 mod 73 displaystyle 9 cdot 65 585 equiv 1 pmod 73 so erhalt man 585 x22C5 2 n x2261 4680 mod 73 displaystyle 585 cdot 2 n equiv 4680 pmod 73 was gleichwertig ist mit 1 x22C5 2 n x2261 8 mod 73 displaystyle 1 cdot 2 n equiv 8 pmod 73 Es ist also 73 displaystyle 73 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn 2 n x2261 8 mod 73 displaystyle 2 n equiv 8 pmod 73 ist Es gilt 2 1 2 x2261 2 x005F mod 73 2 2 4 x2261 4 x005F mod 73 2 3 8 x2261 8 x005F mod 73 2 4 16 x2261 16 x005F mod 73 2 5 32 x2261 32 x005F mod 73 2 6 64 x2261 64 x005F mod 73 2 7 128 x2261 55 x005F mod 73 2 8 256 x2261 37 x005F mod 73 2 9 512 x2261 1 x005F mod 73 2 10 1024 x2261 2 x005F mod 73 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 73 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 73 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 73 2 4 amp amp 16 amp equiv amp underline 16 amp pmod 73 2 5 amp amp 32 amp equiv amp underline 32 amp pmod 73 2 6 amp amp 64 amp equiv amp underline 64 amp pmod 73 2 7 amp amp 128 amp equiv amp underline 55 amp pmod 73 2 8 amp amp 256 amp equiv amp underline 37 amp pmod 73 2 9 amp amp 512 amp equiv amp underline 1 amp pmod 73 2 10 amp amp 1024 amp equiv amp underline 2 amp pmod 73 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 73 displaystyle 73 immer einen Zykel der Lange 9 displaystyle 9 der Form 2 4 8 16 32 64 55 37 1 displaystyle 2 4 8 16 32 64 55 37 1 Es ist also 2 n x2261 8 mod 73 displaystyle 2 n equiv 8 pmod 73 genau dann wenn n x2261 3 mod 9 displaystyle n equiv 3 pmod 9 ist dd 73 displaystyle 73 ist somit ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann wenn n x2261 3 mod 9 displaystyle n equiv 3 pmod 9 ist dd Teil 8 Zusammenfassung In den vergangenen sieben Teilen dieses Beweises wurden alle moglichen Kongruenzen modulo 36 displaystyle 36 abgedeckt Es wurde zum Beispiel gezeigt dass 3 displaystyle 3 ein Teiler von 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 genau dann ist wenn n x2261 0 mod 2 displaystyle n equiv 0 pmod 2 gilt also wenn n x2261 k mod 36 displaystyle n equiv k pmod 36 mit k x2208 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 displaystyle k in 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 ist Zusammenfassend gilt also 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 ist abhangig von n x2208 N x2216 0 displaystyle n in mathbb N backslash 0 unter anderem durch folgende Primzahlen teilbar n x2261 0 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 1 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 und xA0 7 xA0 teilbar n x2261 2 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 3 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 73 xA0 teilbar n x2261 4 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 5 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 teilbar n x2261 6 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 7 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 7 xA0 teilbar n x2261 8 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 9 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 teilbar n x2261 10 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 11 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 13 xA0 teilbar n x2261 12 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 73 xA0 teilbar n x2261 13 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 und xA0 7 xA0 teilbar n x2261 14 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 15 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 19 xA0 teilbar n x2261 16 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 17 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 teilbar n x2261 18 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 19 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 7 xA0 teilbar n x2261 20 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 21 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 und xA0 73 xA0 teilbar n x2261 22 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 23 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 13 xA0 teilbar n x2261 24 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 25 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 und xA0 7 xA0 teilbar n x2261 26 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 27 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 37 xA0 teilbar n x2261 28 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 29 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 teilbar n x2261 30 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 73 xA0 teilbar n x2261 31 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 7 xA0 teilbar n x2261 32 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 teilbar n x2261 33 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 5 xA0 und xA0 19 xA0 teilbar n x2261 34 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 3 xA0 und xA0 7 xA0 teilbar n x2261 35 mod 36 x27F9 78557 x22C5 2 n 1 xA0 ist durch xA0 13 xA0 teilbar displaystyle begin array rcl n equiv 0 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 1 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text und 7 text teilbar n equiv 2 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 3 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 73 text teilbar n equiv 4 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 5 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text teilbar n equiv 6 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 7 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 7 text teilbar n equiv 8 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 9 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text teilbar n equiv 10 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 11 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 13 text teilbar n equiv 12 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 73 text teilbar n equiv 13 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text und 7 text teilbar n equiv 14 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 15 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 19 text teilbar n equiv 16 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 17 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text teilbar n equiv 18 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 19 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 7 text teilbar n equiv 20 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 21 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text und 73 text teilbar n equiv 22 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 23 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 13 text teilbar n equiv 24 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 25 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text und 7 text teilbar n equiv 26 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 27 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 37 text teilbar n equiv 28 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 29 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text teilbar n equiv 30 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 73 text teilbar n equiv 31 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 7 text teilbar n equiv 32 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text teilbar n equiv 33 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 5 text und 19 text teilbar n equiv 34 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 3 text und 7 text teilbar n equiv 35 pmod 36 amp Longrightarrow amp 78557 cdot 2 n 1 text ist durch 13 text teilbar end array dd dd Damit werden alle moglichen n displaystyle n abgedeckt Somit ist 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 immer durch mindestens eine Primzahl teilbar welche in der Menge 3 5 7 13 19 37 73 displaystyle 3 5 7 13 19 37 73 liegt Weil 78557 x22C5 2 n 1 gt 73 displaystyle 78557 cdot 2 n 1 gt 73 fur alle n x2208 N x2216 0 displaystyle n in mathbb N backslash 0 ist ist 78557 x22C5 2 n 1 displaystyle 78557 cdot 2 n 1 fur alle n x2208 N x2216 0 displaystyle n in mathbb N backslash 0 immer eine zusammengesetzte Zahl was zu beweisen war x25FB displaystyle Box dd Die folgenden Zahlen sind bekannte Sierpinski Zahlen k displaystyle k 78557 271129 271577 322523 327739 482719 575041 603713 903983 934909 965431 Folge A076336 in OEIS dd Ist k displaystyle k eine dieser Zahlen so ist k x22C5 2 n 1 displaystyle k cdot 2 n 1 fur alle n displaystyle n zusammengesetzt Man erhalt niemals eine Primzahl Gegenbeispiel Bearbeiten Die Zahl k 19 displaystyle k 19 ist keine Sierpinski Zahl da in der Folge 19 x22C5 2 n 1 displaystyle 19 cdot 2 n 1 wenigstens eine Primzahl auftritt 39 77 153 305 609 1217 2433 Das sechste Glied der Folge 1217 ist eine Primzahl Das genugt zum Nachweis dass 19 keine Sierpinski Zahl ist Ob noch weitere Primzahlen in dieser Folge auftreten oder nicht das zehnte Glied 19457 ist prim ist unerheblich Primzahlen der Form k x22C5 2 n 1 displaystyle k cdot 2 n 1 nennt man Prothsche Primzahl Sierpinski Problem Bearbeiten Das Sierpinski Problem lautet Welche ist die kleinste Sierpinski Zahl 1962 hat John L Selfridge gezeigt dass 78557 eine Sierpinski Zahl ist 91 1 93 Es ist jedoch noch nicht bekannt ob 78557 die kleinste Sierpinski Zahl ist Es wird aber vermutet dass es sich um die kleinste Sierpinski Zahl handelt Das Internet Projekt Seventeen or Bust beschaftigt sich mit diesem Problem Um den Beweis durchzufuhren muss fur jedes k displaystyle k kleiner als 78557 eine Zahl n displaystyle n gefunden werden so dass die resultierende Proth Zahl N k x22C5 2 n 1 displaystyle N k cdot 2 n 1 eine Primzahl ist Dieser Beweis ist Stand 8 Juli 2019 bereits fur alle k displaystyle k bis auf 5 Ausnahmen erfolgt diese sind Primzahlen werden fett geschrieben 21181 22699 24737 55459 und 67607 91 1 93 91 2 93 91 3 93 Die moglicherweise kleinste Sierpinski Zahl k 78557 17 x22C5 4621 displaystyle k 78557 17 cdot 4621 ist eine zusammengesetzte Zahl Das prime Sierpinski Problem beschaftigt sich damit ob k 271129 displaystyle k 271129 die kleinste prime Sierpinski Zahl ist 91 4 93 Um dies zu uberprufen mussen die folgenden 9 Primzahlen uberpruft werden wobei die ersten zwei Zahlen der folgenden Liste schon in obigem Problem auftauchen die ubrigen drei Zahlen der vorhergehenden Liste sind keine Primzahlen 21181 59 x22C5 359 displaystyle 21181 59 cdot 359 24737 29 x22C5 853 displaystyle 24737 29 cdot 853 und 55459 31 x22C5 1789 displaystyle 55459 31 cdot 1789 Stand 31 Dezember 2019 k 22699 67607 79309 79817 152267 156511 222113 225931 237019 Das erweiterte Sierpinski Problem beschaftigt sich damit ob k 271129 displaystyle k 271129 tatsachlich die zweitkleinste Sierpinski Zahl ist 91 4 93 91 5 93 Um dies zu uberprufen mussen neben den 9 oben genannten Primzahlen vom primen Sierpinski Problem noch zusatzlich die folgenden 11 zusammengesetzten Zahlen uberpruft werden wobei die ersten drei zusammengesetzten Zahlen schon im ursprunglichen Sierpinski Problem auftauchen Stand 7 Marz 2022 k 21181 24737 55459 91549 131179 163187 200749 209611 227723 229673 238411 Riesel Zahl Bearbeiten Eine Riesel Zahl benannt nach dem schwedischen Mathematiker Hans Riesel ist eine naturliche ungerade Zahl k displaystyle k fur die die unendliche Zahlenfolge k x22C5 2 n x2212 1 displaystyle k cdot 2 n 1 mit n x2265 1 displaystyle n geq 1 keine Primzahlen enthalt Beispiele Bearbeiten k 509203 displaystyle k 509203 ist eine Riesel Zahl Beweis der Behauptung dass 509203 eine Riesel Zahl ist Der Beweis funktioniert direkt mittels Modulo Rechnung Zu zeigen ist dass 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 fur alle naturlichen Zahlen n x2208 N x2216 0 displaystyle n in mathbb N backslash 0 immer eine zusammengesetzte Zahl also niemals eine Primzahl ist Es wird gezeigt dass es immer eine Zahl aus der Menge 3 5 7 13 17 241 displaystyle 3 5 7 13 17 241 gibt welche 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 teilt diese Menge nennt man im englischen covering set of 509203 Beweis Teil 1 Teilbarkeit durch 3 Es ist 509203 169734 x22C5 3 1 x2261 1 mod 3 displaystyle 509203 169734 cdot 3 1 equiv 1 pmod 3 Somit gilt 3 displaystyle 3 teilt 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 509203 x22C5 2 n x2212 1 x2261 0 mod 3 displaystyle 509203 cdot 2 n 1 equiv 0 pmod 3 genau dann wenn 509203 x22C5 2 n x2261 1 mod 3 displaystyle 509203 cdot 2 n equiv 1 pmod 3 genau dann wenn 1 x22C5 2 n x2261 1 mod 3 displaystyle 1 cdot 2 n equiv 1 pmod 3 ist Es ist also 3 displaystyle 3 ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 2 n x2261 1 mod 3 displaystyle 2 n equiv 1 pmod 3 ist Es gilt 2 1 2 x2261 2 x005F mod 3 2 2 4 x2261 1 x005F mod 3 2 3 8 x2261 2 x005F mod 3 2 4 16 x2261 1 x005F mod 3 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 3 2 2 amp amp 4 amp equiv amp underline 1 pmod 3 2 3 amp amp 8 amp equiv amp underline 2 pmod 3 2 4 amp amp 16 amp equiv amp underline 1 pmod 3 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 3 displaystyle 3 immer einen Zykel der Lange 2 displaystyle 2 der Form 2 1 displaystyle 2 1 Es ist also 2 n x2261 1 mod 3 displaystyle 2 n equiv 1 pmod 3 genau dann wenn n displaystyle n gerade ist also wenn n x2261 0 mod 2 displaystyle n equiv 0 pmod 2 ist dd 3 displaystyle 3 ist somit ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn n x2261 0 mod 2 displaystyle n equiv 0 pmod 2 ist dd Teil 2 Teilbarkeit durch 5 Es ist 509203 101840 x22C5 5 3 x2261 3 mod 5 displaystyle 509203 101840 cdot 5 3 equiv 3 pmod 5 Somit gilt 5 displaystyle 5 teilt 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 509203 x22C5 2 n x2212 1 x2261 0 mod 5 displaystyle 509203 cdot 2 n 1 equiv 0 pmod 5 genau dann wenn 509203 x22C5 2 n x2261 1 mod 5 displaystyle 509203 cdot 2 n equiv 1 pmod 5 genau dann wenn 3 x22C5 2 n x2261 1 mod 5 displaystyle 3 cdot 2 n equiv 1 pmod 5 Multipliziert man diese Modulo Rechnung mit der Inversen von 3 displaystyle 3 modulo 5 displaystyle 5 namlich mit 2 displaystyle 2 es ist 3 x22C5 2 6 x2261 1 mod 5 displaystyle 3 cdot 2 6 equiv 1 pmod 5 so erhalt man 6 x22C5 2 n x2261 2 mod 5 displaystyle 6 cdot 2 n equiv 2 pmod 5 was gleichwertig ist mit 1 x22C5 2 n x2261 2 mod 5 displaystyle 1 cdot 2 n equiv 2 pmod 5 Es ist also 5 displaystyle 5 ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 2 n x2261 2 mod 5 displaystyle 2 n equiv 2 pmod 5 ist Es gilt 2 1 2 x2261 2 x005F mod 5 2 2 4 x2261 4 x005F mod 5 2 3 8 x2261 3 x005F mod 5 2 4 16 x2261 1 x005F mod 5 2 5 32 x2261 2 x005F mod 5 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 5 2 2 amp amp 4 amp equiv amp underline 4 pmod 5 2 3 amp amp 8 amp equiv amp underline 3 pmod 5 2 4 amp amp 16 amp equiv amp underline 1 pmod 5 2 5 amp amp 32 amp equiv amp underline 2 pmod 5 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 5 displaystyle 5 immer einen Zykel der Lange 4 displaystyle 4 der Form 2 4 3 1 displaystyle 2 4 3 1 Es ist also 2 n x2261 2 mod 5 displaystyle 2 n equiv 2 pmod 5 genau dann wenn n x2261 1 mod 4 displaystyle n equiv 1 pmod 4 ist dd 5 displaystyle 5 ist somit ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn n x2261 1 mod 4 displaystyle n equiv 1 pmod 4 ist dd Teil 3 Teilbarkeit durch 7 Es ist 509203 72743 x22C5 7 2 x2261 2 mod 7 displaystyle 509203 72743 cdot 7 2 equiv 2 pmod 7 Somit gilt 7 displaystyle 7 teilt 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 509203 x22C5 2 n x2212 1 x2261 0 mod 7 displaystyle 509203 cdot 2 n 1 equiv 0 pmod 7 genau dann wenn 509203 x22C5 2 n x2261 1 mod 7 displaystyle 509203 cdot 2 n equiv 1 pmod 7 genau dann wenn 2 x22C5 2 n x2261 1 mod 7 displaystyle 2 cdot 2 n equiv 1 pmod 7 Multipliziert man diese Modulo Rechnung mit der Inversen von 2 displaystyle 2 modulo 7 displaystyle 7 namlich mit 4 displaystyle 4 es ist 2 x22C5 4 8 x2261 1 mod 7 displaystyle 2 cdot 4 8 equiv 1 pmod 7 so erhalt man 8 x22C5 2 n x2261 4 mod 7 displaystyle 8 cdot 2 n equiv 4 pmod 7 was gleichwertig ist mit 1 x22C5 2 n x2261 4 mod 7 displaystyle 1 cdot 2 n equiv 4 pmod 7 Es ist also 7 displaystyle 7 ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 2 n x2261 4 mod 7 displaystyle 2 n equiv 4 pmod 7 ist Es gilt 2 1 2 x2261 2 x005F mod 7 2 2 4 x2261 4 x005F mod 7 2 3 8 x2261 1 x005F mod 7 2 4 16 x2261 2 x005F mod 7 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 pmod 7 2 2 amp amp 4 amp equiv amp underline 4 pmod 7 2 3 amp amp 8 amp equiv amp underline 1 pmod 7 2 4 amp amp 16 amp equiv amp underline 2 pmod 7 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 7 displaystyle 7 immer einen Zykel der Lange 3 displaystyle 3 der Form 2 4 1 displaystyle 2 4 1 Es ist also 2 n x2261 4 mod 7 displaystyle 2 n equiv 4 pmod 7 genau dann wenn n x2261 2 mod 3 displaystyle n equiv 2 pmod 3 ist dd 7 displaystyle 7 ist somit ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn n x2261 2 mod 3 displaystyle n equiv 2 pmod 3 ist dd Teil 4 Teilbarkeit durch 13 Es ist 509203 39169 x22C5 13 6 x2261 6 mod 13 displaystyle 509203 39169 cdot 13 6 equiv 6 pmod 13 Somit gilt 13 displaystyle 13 teilt 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 509203 x22C5 2 n x2212 1 x2261 0 mod 13 displaystyle 509203 cdot 2 n 1 equiv 0 pmod 13 genau dann wenn 509203 x22C5 2 n x2261 1 mod 13 displaystyle 509203 cdot 2 n equiv 1 pmod 13 genau dann wenn 6 x22C5 2 n x2261 1 mod 13 displaystyle 6 cdot 2 n equiv 1 pmod 13 Multipliziert man diese Modulo Rechnung mit der Inversen von 6 displaystyle 6 modulo 13 displaystyle 13 namlich mit 11 displaystyle 11 es ist 6 x22C5 11 66 x2261 1 mod 13 displaystyle 6 cdot 11 66 equiv 1 pmod 13 so erhalt man 66 x22C5 2 n x2261 11 mod 13 displaystyle 66 cdot 2 n equiv 11 pmod 13 was gleichwertig ist mit 1 x22C5 2 n x2261 11 mod 13 displaystyle 1 cdot 2 n equiv 11 pmod 13 Es ist also 13 displaystyle 13 ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 2 n x2261 11 mod 13 displaystyle 2 n equiv 11 pmod 13 ist Es gilt 2 1 2 x2261 2 x005F mod 13 2 2 4 x2261 4 x005F mod 13 2 3 8 x2261 8 x005F mod 13 2 4 16 x2261 3 x005F mod 13 2 5 32 x2261 6 x005F mod 13 2 6 64 x2261 12 x005F mod 13 2 7 128 x2261 11 x005F mod 13 2 8 256 x2261 9 x005F mod 13 2 9 512 x2261 5 x005F mod 13 2 10 1024 x2261 10 x005F mod 13 2 11 2048 x2261 7 x005F mod 13 2 12 4096 x2261 1 x005F mod 13 2 13 8192 x2261 2 x005F mod 13 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 13 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 13 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 13 2 4 amp amp 16 amp equiv amp underline 3 amp pmod 13 2 5 amp amp 32 amp equiv amp underline 6 amp pmod 13 2 6 amp amp 64 amp equiv amp underline 12 amp pmod 13 2 7 amp amp 128 amp equiv amp underline 11 amp pmod 13 2 8 amp amp 256 amp equiv amp underline 9 amp pmod 13 2 9 amp amp 512 amp equiv amp underline 5 amp pmod 13 2 10 amp amp 1024 amp equiv amp underline 10 amp pmod 13 2 11 amp amp 2048 amp equiv amp underline 7 amp pmod 13 2 12 amp amp 4096 amp equiv amp underline 1 amp pmod 13 2 13 amp amp 8192 amp equiv amp underline 2 amp pmod 13 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 13 displaystyle 13 immer einen Zykel der Lange 12 displaystyle 12 der Form 2 4 8 3 6 12 11 9 5 10 7 1 displaystyle 2 4 8 3 6 12 11 9 5 10 7 1 Es ist also 2 n x2261 11 mod 13 displaystyle 2 n equiv 11 pmod 13 genau dann wenn n x2261 7 mod 12 displaystyle n equiv 7 pmod 12 ist dd 13 displaystyle 13 ist somit ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn n x2261 7 mod 12 displaystyle n equiv 7 pmod 12 ist dd Teil 5 Teilbarkeit durch 17 Es ist 509203 29953 x22C5 17 2 x2261 2 mod 17 displaystyle 509203 29953 cdot 17 2 equiv 2 pmod 17 Somit gilt 17 displaystyle 17 teilt 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 509203 x22C5 2 n x2212 1 x2261 0 mod 17 displaystyle 509203 cdot 2 n 1 equiv 0 pmod 17 genau dann wenn 509203 x22C5 2 n x2261 1 mod 17 displaystyle 509203 cdot 2 n equiv 1 pmod 17 genau dann wenn 2 x22C5 2 n x2261 1 mod 17 displaystyle 2 cdot 2 n equiv 1 pmod 17 Multipliziert man diese Modulo Rechnung mit der Inversen von 2 displaystyle 2 modulo 17 displaystyle 17 namlich mit 9 displaystyle 9 es ist 2 x22C5 9 18 x2261 1 mod 17 displaystyle 2 cdot 9 18 equiv 1 pmod 17 so erhalt man 18 x22C5 2 n x2261 9 mod 17 displaystyle 18 cdot 2 n equiv 9 pmod 17 was gleichwertig ist mit 1 x22C5 2 n x2261 9 mod 17 displaystyle 1 cdot 2 n equiv 9 pmod 17 Es ist also 17 displaystyle 17 ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn 2 n x2261 9 mod 17 displaystyle 2 n equiv 9 pmod 17 ist Es gilt 2 1 2 x2261 2 x005F mod 17 2 2 4 x2261 4 x005F mod 17 2 3 8 x2261 8 x005F mod 17 2 4 16 x2261 16 x005F mod 17 2 5 32 x2261 15 x005F mod 17 2 6 64 x2261 13 x005F mod 17 2 7 128 x2261 9 x005F mod 17 2 8 256 x2261 1 x005F mod 17 2 9 512 x2261 2 x005F mod 17 displaystyle begin aligned 2 1 amp amp 2 amp equiv amp underline 2 amp pmod 17 2 2 amp amp 4 amp equiv amp underline 4 amp pmod 17 2 3 amp amp 8 amp equiv amp underline 8 amp pmod 17 2 4 amp amp 16 amp equiv amp underline 16 amp pmod 17 2 5 amp amp 32 amp equiv amp underline 15 amp pmod 17 2 6 amp amp 64 amp equiv amp underline 13 amp pmod 17 2 7 amp amp 128 amp equiv amp underline 9 amp pmod 17 2 8 amp amp 256 amp equiv amp underline 1 amp pmod 17 2 9 amp amp 512 amp equiv amp underline 2 amp pmod 17 end aligned etc dd Somit durchlaufen die Zweierpotenzen modulo 17 displaystyle 17 immer einen Zykel der Lange 8 displaystyle 8 der Form 2 4 8 16 15 13 9 1 displaystyle 2 4 8 16 15 13 9 1 Es ist also 2 n x2261 9 mod 17 displaystyle 2 n equiv 9 pmod 17 genau dann wenn n x2261 7 mod 8 displaystyle n equiv 7 pmod 8 ist dd 17 displaystyle 17 ist somit ein Teiler von 509203 x22C5 2 n x2212 1 displaystyle 509203 cdot 2 n 1 genau dann wenn n x2261 7 mod 8 displaystyle n equiv 7 pmod 8 ist dd Teil 6 Teilbarkeit durch 241 Es ist 509203 2112 x22C5 241 211 x2261 211 mod 241 displaystyle 509203 2112 cdot 241 211 equiv 211 pmod 241 Somit gilt 241 displaystyle 241 teilt 509203 x22C5 2 m