Sierpiński-Zahl

Dieser Artikel beschäftigt sich mit den Sierpiński-Zahlen. Für die nach Sierpiński benannte Konstante siehe Sierpiński-Konstante.

Eine Sierpiński-Zahl (benannt nach dem polnischen Mathematiker Wacław Sierpiński) ist eine natürliche, ungerade Zahl k {\displaystyle k} , für die die unendliche Zahlenfolge k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} mit n ≥ 1 {\displaystyle n\geq 1} keine Primzahlen enthält.

Beispiele

  • k = 78557 {\displaystyle k=78557} ist eine Sierpiński-Zahl.
Beweis der Behauptung, dass 78557 eine Sierpiński-Zahl ist:

Der Beweis funktioniert direkt mittels Modulo-Rechnung.[1]

Zu zeigen ist, dass 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} für alle natürlichen Zahlen n ∈ N ∖ { 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 ⋅ 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 ⋅ 3 + 2 ≡ 2 ( mod 3 ) {\displaystyle 78557=26185\cdot 3+2\equiv 2{\pmod {3}}} . Somit gilt:
3 {\displaystyle 3} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 3 ( mod 3 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 3{\pmod {3}}} genau dann, wenn 78557 ⋅ 2 n ≡ 2 ( mod 3 ) {\displaystyle 78557\cdot 2^{n}\equiv 2{\pmod {3}}} genau dann, wenn 2 ⋅ 2 n ≡ 2 ( mod 3 ) {\displaystyle 2\cdot 2^{n}\equiv 2{\pmod {3}}} genau dann, wenn 2 n ≡ 1 ( mod 3 ) {\displaystyle 2^{n}\equiv 1{\pmod {3}}} ist.
Es ist also 3 {\displaystyle 3} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 1 ( mod 3 ) {\displaystyle 2^{n}\equiv 1{\pmod {3}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 3 ) 2 2 = 4 ≡ 1 _ ( mod 3 ) 2 3 = 8 ≡ 2 _ ( mod 3 ) 2 4 = 16 ≡ 1 _ ( mod 3 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {3}}\\2^{2}&=&4&\equiv &{\underline {1}}{\pmod {3}}\\2^{3}&=&8&\equiv &{\underline {2}}{\pmod {3}}\\2^{4}&=&16&\equiv &{\underline {1}}{\pmod {3}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 3 {\displaystyle 3} immer einen Zykel der Länge 2 {\displaystyle 2} der Form ( 2 , 1 ) {\displaystyle (2,1)} .
Es ist also 2 n ≡ 1 ( mod 3 ) {\displaystyle 2^{n}\equiv 1{\pmod {3}}} genau dann, wenn n {\displaystyle n} gerade ist, also wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} ist.
3 {\displaystyle 3} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} ist.
Teil 2: Teilbarkeit durch 5:
Es ist 78557 = 15711 ⋅ 5 + 2 ≡ 2 ( mod 5 ) {\displaystyle 78557=15711\cdot 5+2\equiv 2{\pmod {5}}} . Somit gilt:
5 {\displaystyle 5} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 5 ( mod 5 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 5{\pmod {5}}} genau dann, wenn 78557 ⋅ 2 n ≡ 4 ( mod 5 ) {\displaystyle 78557\cdot 2^{n}\equiv 4{\pmod {5}}} genau dann, wenn 2 ⋅ 2 n ≡ 4 ( mod 5 ) {\displaystyle 2\cdot 2^{n}\equiv 4{\pmod {5}}} genau dann, wenn 2 n ≡ 2 ( mod 5 ) {\displaystyle 2^{n}\equiv 2{\pmod {5}}} ist.
Es ist also 5 {\displaystyle 5} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 2 ( mod 5 ) {\displaystyle 2^{n}\equiv 2{\pmod {5}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 5 ) 2 2 = 4 ≡ 4 _ ( mod 5 ) 2 3 = 8 ≡ 3 _ ( mod 5 ) 2 4 = 16 ≡ 1 _ ( mod 5 ) 2 5 = 32 ≡ 2 _ ( mod 5 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {5}}\\2^{2}&=&4&\equiv &{\underline {4}}{\pmod {5}}\\2^{3}&=&8&\equiv &{\underline {3}}{\pmod {5}}\\2^{4}&=&16&\equiv &{\underline {1}}{\pmod {5}}\\2^{5}&=&32&\equiv &{\underline {2}}{\pmod {5}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 5 {\displaystyle 5} immer einen Zykel der Länge 4 {\displaystyle 4} der Form ( 2 , 4 , 3 , 1 ) {\displaystyle (2,4,3,1)} .
Es ist also 2 n ≡ 2 ( mod 5 ) {\displaystyle 2^{n}\equiv 2{\pmod {5}}} genau dann, wenn n ≡ 1 ( mod 4 ) {\displaystyle n\equiv 1{\pmod {4}}} ist.
5 {\displaystyle 5} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 1 ( mod 4 ) {\displaystyle n\equiv 1{\pmod {4}}} ist.
Teil 3: Teilbarkeit durch 7:
Es ist 78557 = 11222 ⋅ 7 + 3 ≡ 3 ( mod 7 ) {\displaystyle 78557=11222\cdot 7+3\equiv 3{\pmod {7}}} . Somit gilt:
7 {\displaystyle 7} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 7 ( mod 7 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 7{\pmod {7}}} genau dann, wenn 78557 ⋅ 2 n ≡ 6 ( mod 7 ) {\displaystyle 78557\cdot 2^{n}\equiv 6{\pmod {7}}} genau dann, wenn 3 ⋅ 2 n ≡ 6 ( mod 7 ) {\displaystyle 3\cdot 2^{n}\equiv 6{\pmod {7}}} genau dann, wenn 2 n ≡ 2 ( mod 7 ) {\displaystyle 2^{n}\equiv 2{\pmod {7}}} ist.
Es ist also 7 {\displaystyle 7} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 2 ( mod 7 ) {\displaystyle 2^{n}\equiv 2{\pmod {7}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 7 ) 2 2 = 4 ≡ 4 _ ( mod 7 ) 2 3 = 8 ≡ 1 _ ( mod 7 ) 2 4 = 16 ≡ 2 _ ( mod 7 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {7}}\\2^{2}&=&4&\equiv &{\underline {4}}{\pmod {7}}\\2^{3}&=&8&\equiv &{\underline {1}}{\pmod {7}}\\2^{4}&=&16&\equiv &{\underline {2}}{\pmod {7}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 7 {\displaystyle 7} immer einen Zykel der Länge 3 {\displaystyle 3} der Form ( 2 , 4 , 1 ) {\displaystyle (2,4,1)} .
Es ist also 2 n ≡ 2 ( mod 7 ) {\displaystyle 2^{n}\equiv 2{\pmod {7}}} genau dann, wenn n ≡ 1 ( mod 3 ) {\displaystyle n\equiv 1{\pmod {3}}} ist.
7 {\displaystyle 7} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 1 ( mod 3 ) {\displaystyle n\equiv 1{\pmod {3}}} ist.
Teil 4: Teilbarkeit durch 13:
Es ist 78557 = 6042 ⋅ 13 + 11 ≡ 11 ( mod 13 ) {\displaystyle 78557=6042\cdot 13+11\equiv 11{\pmod {13}}} . Somit gilt:
13 {\displaystyle 13} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 13 ( mod 13 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 13{\pmod {13}}} genau dann, wenn 78557 ⋅ 2 n ≡ 12 ( mod 13 ) {\displaystyle 78557\cdot 2^{n}\equiv 12{\pmod {13}}} genau dann, wenn 11 ⋅ 2 n ≡ 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} , nämlich mit 6 {\displaystyle 6} (es ist 11 ⋅ 6 = 66 ≡ 1 ( mod 13 ) {\displaystyle 11\cdot 6=66\equiv 1{\pmod {13}}} ), so erhält man 66 ⋅ 2 n ≡ 72 ( mod 13 ) {\displaystyle 66\cdot 2^{n}\equiv 72{\pmod {13}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 7 ( mod 13 ) {\displaystyle 1\cdot 2^{n}\equiv 7{\pmod {13}}} .
Es ist also 13 {\displaystyle 13} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 7 ( mod 13 ) {\displaystyle 2^{n}\equiv 7{\pmod {13}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 13 ) 2 2 = 4 ≡ 4 _ ( mod 13 ) 2 3 = 8 ≡ 8 _ ( mod 13 ) 2 4 = 16 ≡ 3 _ ( mod 13 ) 2 5 = 32 ≡ 6 _ ( mod 13 ) 2 6 = 64 ≡ 12 _ ( mod 13 ) 2 7 = 128 ≡ 11 _ ( mod 13 ) 2 8 = 256 ≡ 9 _ ( mod 13 ) 2 9 = 512 ≡ 5 _ ( mod 13 ) 2 10 = 1024 ≡ 10 _ ( mod 13 ) 2 11 = 2048 ≡ 7 _ ( mod 13 ) 2 12 = 4096 ≡ 1 _ ( mod 13 ) 2 13 = 8192 ≡ 2 _ ( mod 13 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {13}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {13}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {13}}\\2^{4}&=&16&\equiv &{\underline {3}}&{\pmod {13}}\\2^{5}&=&32&\equiv &{\underline {6}}&{\pmod {13}}\\2^{6}&=&64&\equiv &{\underline {12}}&{\pmod {13}}\\2^{7}&=&128&\equiv &{\underline {11}}&{\pmod {13}}\\2^{8}&=&256&\equiv &{\underline {9}}&{\pmod {13}}\\2^{9}&=&512&\equiv &{\underline {5}}&{\pmod {13}}\\2^{10}&=&1024&\equiv &{\underline {10}}&{\pmod {13}}\\2^{11}&=&2048&\equiv &{\underline {7}}&{\pmod {13}}\\2^{12}&=&4096&\equiv &{\underline {1}}&{\pmod {13}}\\2^{13}&=&8192&\equiv &{\underline {2}}&{\pmod {13}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 13 {\displaystyle 13} immer einen Zykel der Länge 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 ≡ 7 ( mod 13 ) {\displaystyle 2^{n}\equiv 7{\pmod {13}}} genau dann, wenn n ≡ 11 ( mod 12 ) {\displaystyle n\equiv 11{\pmod {12}}} ist.
13 {\displaystyle 13} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 11 ( mod 12 ) {\displaystyle n\equiv 11{\pmod {12}}} ist.
Teil 5: Teilbarkeit durch 19:
Es ist 78557 = 4134 ⋅ 19 + 11 ≡ 11 ( mod 19 ) {\displaystyle 78557=4134\cdot 19+11\equiv 11{\pmod {19}}} . Somit gilt:
19 {\displaystyle 19} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 19 ( mod 19 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 19{\pmod {19}}} genau dann, wenn 78557 ⋅ 2 n ≡ 18 ( mod 19 ) {\displaystyle 78557\cdot 2^{n}\equiv 18{\pmod {19}}} genau dann, wenn 11 ⋅ 2 n ≡ 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} , nämlich mit 7 {\displaystyle 7} (es ist 11 ⋅ 7 = 77 ≡ 1 ( mod 19 ) {\displaystyle 11\cdot 7=77\equiv 1{\pmod {19}}} ), so erhält man 77 ⋅ 2 n ≡ 126 ( mod 19 ) {\displaystyle 77\cdot 2^{n}\equiv 126{\pmod {19}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 12 ( mod 19 ) {\displaystyle 1\cdot 2^{n}\equiv 12{\pmod {19}}} .
Es ist also 19 {\displaystyle 19} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 12 ( mod 19 ) {\displaystyle 2^{n}\equiv 12{\pmod {19}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 19 ) 2 2 = 4 ≡ 4 _ ( mod 19 ) 2 3 = 8 ≡ 8 _ ( mod 19 ) 2 4 = 16 ≡ 16 _ ( mod 19 ) 2 5 = 32 ≡ 13 _ ( mod 19 ) 2 6 = 64 ≡ 7 _ ( mod 19 ) 2 7 = 128 ≡ 14 _ ( mod 19 ) 2 8 = 256 ≡ 9 _ ( mod 19 ) 2 9 = 512 ≡ 18 _ ( mod 19 ) 2 10 = 1024 ≡ 17 _ ( mod 19 ) 2 11 = 2048 ≡ 15 _ ( mod 19 ) 2 12 = 4096 ≡ 11 _ ( mod 19 ) 2 13 = 8192 ≡ 3 _ ( mod 19 ) 2 14 = 16384 ≡ 6 _ ( mod 19 ) 2 15 = 32768 ≡ 12 _ ( mod 19 ) 2 16 = 65536 ≡ 5 _ ( mod 19 ) 2 17 = 131072 ≡ 10 _ ( mod 19 ) 2 18 = 262144 ≡ 1 _ ( mod 19 ) 2 19 = 524288 ≡ 2 _ ( mod 19 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {19}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {19}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {19}}\\2^{4}&=&16&\equiv &{\underline {16}}&{\pmod {19}}\\2^{5}&=&32&\equiv &{\underline {13}}&{\pmod {19}}\\2^{6}&=&64&\equiv &{\underline {7}}&{\pmod {19}}\\2^{7}&=&128&\equiv &{\underline {14}}&{\pmod {19}}\\2^{8}&=&256&\equiv &{\underline {9}}&{\pmod {19}}\\2^{9}&=&512&\equiv &{\underline {18}}&{\pmod {19}}\\2^{10}&=&1024&\equiv &{\underline {17}}&{\pmod {19}}\\2^{11}&=&2048&\equiv &{\underline {15}}&{\pmod {19}}\\2^{12}&=&4096&\equiv &{\underline {11}}&{\pmod {19}}\\2^{13}&=&8192&\equiv &{\underline {3}}&{\pmod {19}}\\2^{14}&=&16384&\equiv &{\underline {6}}&{\pmod {19}}\\2^{15}&=&32768&\equiv &{\underline {12}}&{\pmod {19}}\\2^{16}&=&65536&\equiv &{\underline {5}}&{\pmod {19}}\\2^{17}&=&131072&\equiv &{\underline {10}}&{\pmod {19}}\\2^{18}&=&262144&\equiv &{\underline {1}}&{\pmod {19}}\\2^{19}&=&524288&\equiv &{\underline {2}}&{\pmod {19}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 19 {\displaystyle 19} immer einen Zykel der Länge 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 ≡ 12 ( mod 19 ) {\displaystyle 2^{n}\equiv 12{\pmod {19}}} genau dann, wenn n ≡ 15 ( mod 18 ) {\displaystyle n\equiv 15{\pmod {18}}} ist.
19 {\displaystyle 19} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 15 ( mod 18 ) {\displaystyle n\equiv 15{\pmod {18}}} ist.
Teil 6: Teilbarkeit durch 37:
Es ist 78557 = 2123 ⋅ 37 + 6 ≡ 6 ( mod 37 ) {\displaystyle 78557=2123\cdot 37+6\equiv 6{\pmod {37}}} . Somit gilt:
37 {\displaystyle 37} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 37 ( mod 37 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 37{\pmod {37}}} genau dann, wenn 78557 ⋅ 2 n ≡ 36 ( mod 37 ) {\displaystyle 78557\cdot 2^{n}\equiv 36{\pmod {37}}} genau dann, wenn 6 ⋅ 2 n ≡ 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} , nämlich mit 31 {\displaystyle 31} (es ist 6 ⋅ 31 = 186 ≡ 1 ( mod 37 ) {\displaystyle 6\cdot 31=186\equiv 1{\pmod {37}}} ), so erhält man 186 ⋅ 2 n ≡ 1116 ( mod 37 ) {\displaystyle 186\cdot 2^{n}\equiv 1116{\pmod {37}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 6 ( mod 37 ) {\displaystyle 1\cdot 2^{n}\equiv 6{\pmod {37}}} .
Es ist also 37 {\displaystyle 37} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 6 ( mod 37 ) {\displaystyle 2^{n}\equiv 6{\pmod {37}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 37 ) 2 2 = 4 ≡ 4 _ ( mod 37 ) 2 3 = 8 ≡ 8 _ ( mod 37 ) 2 4 = 16 ≡ 16 _ ( mod 37 ) 2 5 = 32 ≡ 32 _ ( mod 37 ) 2 6 = 64 ≡ 27 _ ( mod 37 ) 2 7 = 128 ≡ 17 _ ( mod 37 ) 2 8 = 256 ≡ 34 _ ( mod 37 ) 2 9 = 512 ≡ 31 _ ( mod 37 ) 2 10 = 1024 ≡ 25 _ ( mod 37 ) 2 11 = 2048 ≡ 13 _ ( mod 37 ) 2 12 = 4096 ≡ 26 _ ( mod 37 ) 2 13 = 8192 ≡ 15 _ ( mod 37 ) 2 14 = 16384 ≡ 30 _ ( mod 37 ) 2 15 = 32768 ≡ 23 _ ( mod 37 ) 2 16 = 65536 ≡ 9 _ ( mod 37 ) 2 17 = 131072 ≡ 18 _ ( mod 37 ) 2 18 = 262144 ≡ 36 _ ( mod 37 ) 2 19 = 524288 ≡ 35 _ ( mod 37 ) 2 20 = 1048576 ≡ 33 _ ( mod 37 ) 2 21 = 2097152 ≡ 29 _ ( mod 37 ) 2 22 = 4194304 ≡ 21 _ ( mod 37 ) 2 23 = 8388608 ≡ 5 _ ( mod 37 ) 2 24 = 16777216 ≡ 10 _ ( mod 37 ) 2 25 = 33554432 ≡ 20 _ ( mod 37 ) 2 26 = 67108864 ≡ 3 _ ( mod 37 ) 2 27 = 134217728 ≡ 6 _ ( mod 37 ) 2 28 = 268435456 ≡ 12 _ ( mod 37 ) 2 29 = 536870912 ≡ 24 _ ( mod 37 ) 2 30 = 1073741824 ≡ 11 _ ( mod 37 ) 2 31 = 2147483648 ≡ 22 _ ( mod 37 ) 2 32 = 4294967296 ≡ 7 _ ( mod 37 ) 2 33 = 8589934592 ≡ 14 _ ( mod 37 ) 2 34 = 17179869184 ≡ 28 _ ( mod 37 ) 2 35 = 34359738368 ≡ 19 _ ( mod 37 ) 2 36 = 68719476736 ≡ 1 _ ( mod 37 ) 2 37 = 137438953472 ≡ 2 _ ( mod 37 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {37}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {37}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {37}}\\2^{4}&=&16&\equiv &{\underline {16}}&{\pmod {37}}\\2^{5}&=&32&\equiv &{\underline {32}}&{\pmod {37}}\\2^{6}&=&64&\equiv &{\underline {27}}&{\pmod {37}}\\2^{7}&=&128&\equiv &{\underline {17}}&{\pmod {37}}\\2^{8}&=&256&\equiv &{\underline {34}}&{\pmod {37}}\\2^{9}&=&512&\equiv &{\underline {31}}&{\pmod {37}}\\2^{10}&=&1024&\equiv &{\underline {25}}&{\pmod {37}}\\2^{11}&=&2048&\equiv &{\underline {13}}&{\pmod {37}}\\2^{12}&=&4096&\equiv &{\underline {26}}&{\pmod {37}}\\2^{13}&=&8192&\equiv &{\underline {15}}&{\pmod {37}}\\2^{14}&=&16384&\equiv &{\underline {30}}&{\pmod {37}}\\2^{15}&=&32768&\equiv &{\underline {23}}&{\pmod {37}}\\2^{16}&=&65536&\equiv &{\underline {9}}&{\pmod {37}}\\2^{17}&=&131072&\equiv &{\underline {18}}&{\pmod {37}}\\2^{18}&=&262144&\equiv &{\underline {36}}&{\pmod {37}}\\2^{19}&=&524288&\equiv &{\underline {35}}&{\pmod {37}}\\2^{20}&=&1048576&\equiv &{\underline {33}}&{\pmod {37}}\\2^{21}&=&2097152&\equiv &{\underline {29}}&{\pmod {37}}\\2^{22}&=&4194304&\equiv &{\underline {21}}&{\pmod {37}}\\2^{23}&=&8388608&\equiv &{\underline {5}}&{\pmod {37}}\\2^{24}&=&16777216&\equiv &{\underline {10}}&{\pmod {37}}\\2^{25}&=&33554432&\equiv &{\underline {20}}&{\pmod {37}}\\2^{26}&=&67108864&\equiv &{\underline {3}}&{\pmod {37}}\\2^{27}&=&134217728&\equiv &{\underline {6}}&{\pmod {37}}\\2^{28}&=&268435456&\equiv &{\underline {12}}&{\pmod {37}}\\2^{29}&=&536870912&\equiv &{\underline {24}}&{\pmod {37}}\\2^{30}&=&1073741824&\equiv &{\underline {11}}&{\pmod {37}}\\2^{31}&=&2147483648&\equiv &{\underline {22}}&{\pmod {37}}\\2^{32}&=&4294967296&\equiv &{\underline {7}}&{\pmod {37}}\\2^{33}&=&8589934592&\equiv &{\underline {14}}&{\pmod {37}}\\2^{34}&=&17179869184&\equiv &{\underline {28}}&{\pmod {37}}\\2^{35}&=&34359738368&\equiv &{\underline {19}}&{\pmod {37}}\\2^{36}&=&68719476736&\equiv &{\underline {1}}&{\pmod {37}}\\2^{37}&=&137438953472&\equiv &{\underline {2}}&{\pmod {37}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 37 {\displaystyle 37} immer einen Zykel der Länge 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 ≡ 6 ( mod 37 ) {\displaystyle 2^{n}\equiv 6{\pmod {37}}} genau dann, wenn n ≡ 27 ( mod 36 ) {\displaystyle n\equiv 27{\pmod {36}}} ist.
37 {\displaystyle 37} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 27 ( mod 36 ) {\displaystyle n\equiv 27{\pmod {36}}} ist.
Teil 7: Teilbarkeit durch 73:
Es ist 78557 = 1076 ⋅ 73 + 9 ≡ 9 ( mod 73 ) {\displaystyle 78557=1076\cdot 73+9\equiv 9{\pmod {73}}} . Somit gilt:
73 {\displaystyle 73} teilt 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 78557 ⋅ 2 n + 1 ≡ 0 ≡ 73 ( mod 73 ) {\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 73{\pmod {73}}} genau dann, wenn 78557 ⋅ 2 n ≡ 72 ( mod 73 ) {\displaystyle 78557\cdot 2^{n}\equiv 72{\pmod {73}}} genau dann, wenn 9 ⋅ 2 n ≡ 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} , nämlich mit 65 {\displaystyle 65} (es ist 9 ⋅ 65 = 585 ≡ 1 ( mod 73 ) {\displaystyle 9\cdot 65=585\equiv 1{\pmod {73}}} ), so erhält man 585 ⋅ 2 n ≡ 4680 ( mod 73 ) {\displaystyle 585\cdot 2^{n}\equiv 4680{\pmod {73}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 8 ( mod 73 ) {\displaystyle 1\cdot 2^{n}\equiv 8{\pmod {73}}} .
Es ist also 73 {\displaystyle 73} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn 2 n ≡ 8 ( mod 73 ) {\displaystyle 2^{n}\equiv 8{\pmod {73}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 73 ) 2 2 = 4 ≡ 4 _ ( mod 73 ) 2 3 = 8 ≡ 8 _ ( mod 73 ) 2 4 = 16 ≡ 16 _ ( mod 73 ) 2 5 = 32 ≡ 32 _ ( mod 73 ) 2 6 = 64 ≡ 64 _ ( mod 73 ) 2 7 = 128 ≡ 55 _ ( mod 73 ) 2 8 = 256 ≡ 37 _ ( mod 73 ) 2 9 = 512 ≡ 1 _ ( mod 73 ) 2 10 = 1024 ≡ 2 _ ( mod 73 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {73}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {73}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {73}}\\2^{4}&=&16&\equiv &{\underline {16}}&{\pmod {73}}\\2^{5}&=&32&\equiv &{\underline {32}}&{\pmod {73}}\\2^{6}&=&64&\equiv &{\underline {64}}&{\pmod {73}}\\2^{7}&=&128&\equiv &{\underline {55}}&{\pmod {73}}\\2^{8}&=&256&\equiv &{\underline {37}}&{\pmod {73}}\\2^{9}&=&512&\equiv &{\underline {1}}&{\pmod {73}}\\2^{10}&=&1024&\equiv &{\underline {2}}&{\pmod {73}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 73 {\displaystyle 73} immer einen Zykel der Länge 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 ≡ 8 ( mod 73 ) {\displaystyle 2^{n}\equiv 8{\pmod {73}}} genau dann, wenn n ≡ 3 ( mod 9 ) {\displaystyle n\equiv 3{\pmod {9}}} ist.
73 {\displaystyle 73} ist somit ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann, wenn n ≡ 3 ( mod 9 ) {\displaystyle n\equiv 3{\pmod {9}}} ist.
Teil 8: Zusammenfassung:
In den vergangenen sieben Teilen dieses Beweises wurden alle möglichen Kongruenzen modulo 36 {\displaystyle 36} abgedeckt. Es wurde zum Beispiel gezeigt, dass 3 {\displaystyle 3} ein Teiler von 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} genau dann ist, wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} gilt, also wenn n ≡ k ( mod 36 ) {\displaystyle n\equiv k{\pmod {36}}} mit k ∈ { 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 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} ist, abhängig von n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} , unter anderem durch folgende Primzahlen teilbar:
n ≡ 0 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 1 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  und  7  teilbar n ≡ 2 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 3 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  73  teilbar n ≡ 4 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 5 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  teilbar n ≡ 6 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 7 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  7  teilbar n ≡ 8 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 9 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  teilbar n ≡ 10 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 11 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  13  teilbar n ≡ 12 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  73  teilbar n ≡ 13 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  und  7  teilbar n ≡ 14 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 15 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  19  teilbar n ≡ 16 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 17 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  teilbar n ≡ 18 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 19 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  7  teilbar n ≡ 20 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 21 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  und  73  teilbar n ≡ 22 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 23 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  13  teilbar n ≡ 24 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 25 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  und  7  teilbar n ≡ 26 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 27 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  37  teilbar n ≡ 28 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 29 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  teilbar n ≡ 30 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  73  teilbar n ≡ 31 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  7  teilbar n ≡ 32 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  teilbar n ≡ 33 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  5  und  19  teilbar n ≡ 34 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  3  und  7  teilbar n ≡ 35 ( mod 36 ) ⟹ 78557 ⋅ 2 n + 1  ist durch  13  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 0{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 1{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ und }}7{\text{ teilbar}}\\n\equiv 2{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 3{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}73{\text{ teilbar}}\\n\equiv 4{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 5{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 6{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 7{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 8{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 9{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 10{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 11{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 12{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}73{\text{ teilbar}}\\n\equiv 13{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ und }}7{\text{ teilbar}}\\n\equiv 14{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 15{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 16{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 17{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 18{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 19{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 20{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 21{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ und }}73{\text{ teilbar}}\\n\equiv 22{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 23{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 24{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 25{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ und }}7{\text{ teilbar}}\\n\equiv 26{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 27{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 28{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 29{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 30{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}73{\text{ teilbar}}\\n\equiv 31{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 32{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 33{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}5{\text{ und }}19{\text{ teilbar}}\\n\equiv 34{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 35{\pmod {36}}&\Longrightarrow &78557\cdot 2^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\end{array}}}
Damit werden alle möglichen n {\displaystyle n} abgedeckt. Somit ist 78557 ⋅ 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 ⋅ 2 n + 1 > 73 {\displaystyle 78557\cdot 2^{n}+1>73} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} ist, ist 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} immer eine zusammengesetzte Zahl, was zu beweisen war. ◻ {\displaystyle \Box }
  • Die folgenden Zahlen sind bekannte Sierpiński-Zahlen k {\displaystyle k} :
78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … (Folge A076336 in OEIS)
Ist k {\displaystyle k} eine dieser Zahlen, so ist k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} für alle n {\displaystyle n} zusammengesetzt. Man erhält niemals eine Primzahl.

Gegenbeispiel

Die Zahl k = 19 {\displaystyle k=19} ist keine Sierpiński-Zahl, da in der Folge 19 ⋅ 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 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 k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} nennt man Prothsche Primzahl.

Sierpiński-Problem

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.[1] 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 k {\displaystyle k} kleiner als 78557 eine Zahl n {\displaystyle n} gefunden werden, so dass die resultierende Proth-Zahl N = k ⋅ 2 n + 1 {\displaystyle N=k\cdot 2^{n}+1} eine Primzahl ist. Dieser Beweis ist (Stand 8. Juli 2019) bereits für alle k {\displaystyle k} bis auf 5 Ausnahmen erfolgt, diese sind (Primzahlen werden fett geschrieben):

21181, 22699, 24737, 55459 und 67607[1][2][3]

Die möglicherweise kleinste Sierpiński-Zahl k = 78557 = 17 ⋅ 4621 {\displaystyle k=78557=17\cdot 4621} ist eine zusammengesetzte Zahl.

Das prime Sierpiński-Problem beschäftigt sich damit, ob k = 271129 {\displaystyle k=271129} die kleinste prime Sierpiński-Zahl ist.[4] 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: 21181 = 59 ⋅ 359 {\displaystyle 21181=59\cdot 359} , 24737 = 29 ⋅ 853 {\displaystyle 24737=29\cdot 853} und 55459 = 31 ⋅ 1789 {\displaystyle 55459=31\cdot 1789} ) (Stand: 31. Dezember 2019):

k = 22699, 67607, 79309, 79817, 152267, 156511, 222113, 225931, 237019

Das erweiterte Sierpiński-Problem beschäftigt sich damit, ob k = 271129 {\displaystyle k=271129} tatsächlich die zweitkleinste Sierpiński-Zahl ist.[4][5] 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):

k = 21181, 24737, 55459, 91549, 131179, 163187, 200749, 209611, 227723, 229673, 238411

Riesel-Zahl

Eine Riesel-Zahl (benannt nach dem schwedischen Mathematiker Hans Riesel) ist eine natürliche, ungerade Zahl k {\displaystyle k} , für die die unendliche Zahlenfolge k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} mit n ≥ 1 {\displaystyle n\geq 1} keine Primzahlen enthält.

Beispiele

  • 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 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} für alle natürlichen Zahlen n ∈ N ∖ { 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 ⋅ 2 n − 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 ⋅ 3 + 1 ≡ 1 ( mod 3 ) {\displaystyle 509203=169734\cdot 3+1\equiv 1{\pmod {3}}} . Somit gilt:
3 {\displaystyle 3} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 3 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {3}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 3 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {3}}} genau dann, wenn 1 ⋅ 2 n ≡ 1 ( mod 3 ) {\displaystyle 1\cdot 2^{n}\equiv 1{\pmod {3}}} ist.
Es ist also 3 {\displaystyle 3} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 1 ( mod 3 ) {\displaystyle 2^{n}\equiv 1{\pmod {3}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 3 ) 2 2 = 4 ≡ 1 _ ( mod 3 ) 2 3 = 8 ≡ 2 _ ( mod 3 ) 2 4 = 16 ≡ 1 _ ( mod 3 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {3}}\\2^{2}&=&4&\equiv &{\underline {1}}{\pmod {3}}\\2^{3}&=&8&\equiv &{\underline {2}}{\pmod {3}}\\2^{4}&=&16&\equiv &{\underline {1}}{\pmod {3}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 3 {\displaystyle 3} immer einen Zykel der Länge 2 {\displaystyle 2} der Form ( 2 , 1 ) {\displaystyle (2,1)} .
Es ist also 2 n ≡ 1 ( mod 3 ) {\displaystyle 2^{n}\equiv 1{\pmod {3}}} genau dann, wenn n {\displaystyle n} gerade ist, also wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} ist.
3 {\displaystyle 3} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} ist.
Teil 2: Teilbarkeit durch 5:
Es ist 509203 = 101840 ⋅ 5 + 3 ≡ 3 ( mod 5 ) {\displaystyle 509203=101840\cdot 5+3\equiv 3{\pmod {5}}} . Somit gilt:
5 {\displaystyle 5} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 5 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {5}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 5 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {5}}} genau dann, wenn 3 ⋅ 2 n ≡ 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} , nämlich mit 2 {\displaystyle 2} (es ist 3 ⋅ 2 = 6 ≡ 1 ( mod 5 ) {\displaystyle 3\cdot 2=6\equiv 1{\pmod {5}}} ), so erhält man 6 ⋅ 2 n ≡ 2 ( mod 5 ) {\displaystyle 6\cdot 2^{n}\equiv 2{\pmod {5}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 2 ( mod 5 ) {\displaystyle 1\cdot 2^{n}\equiv 2{\pmod {5}}} .
Es ist also 5 {\displaystyle 5} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 2 ( mod 5 ) {\displaystyle 2^{n}\equiv 2{\pmod {5}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 5 ) 2 2 = 4 ≡ 4 _ ( mod 5 ) 2 3 = 8 ≡ 3 _ ( mod 5 ) 2 4 = 16 ≡ 1 _ ( mod 5 ) 2 5 = 32 ≡ 2 _ ( mod 5 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {5}}\\2^{2}&=&4&\equiv &{\underline {4}}{\pmod {5}}\\2^{3}&=&8&\equiv &{\underline {3}}{\pmod {5}}\\2^{4}&=&16&\equiv &{\underline {1}}{\pmod {5}}\\2^{5}&=&32&\equiv &{\underline {2}}{\pmod {5}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 5 {\displaystyle 5} immer einen Zykel der Länge 4 {\displaystyle 4} der Form ( 2 , 4 , 3 , 1 ) {\displaystyle (2,4,3,1)} .
Es ist also 2 n ≡ 2 ( mod 5 ) {\displaystyle 2^{n}\equiv 2{\pmod {5}}} genau dann, wenn n ≡ 1 ( mod 4 ) {\displaystyle n\equiv 1{\pmod {4}}} ist.
5 {\displaystyle 5} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 1 ( mod 4 ) {\displaystyle n\equiv 1{\pmod {4}}} ist.
Teil 3: Teilbarkeit durch 7:
Es ist 509203 = 72743 ⋅ 7 + 2 ≡ 2 ( mod 7 ) {\displaystyle 509203=72743\cdot 7+2\equiv 2{\pmod {7}}} . Somit gilt:
7 {\displaystyle 7} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 7 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {7}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 7 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {7}}} genau dann, wenn 2 ⋅ 2 n ≡ 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} , nämlich mit 4 {\displaystyle 4} (es ist 2 ⋅ 4 = 8 ≡ 1 ( mod 7 ) {\displaystyle 2\cdot 4=8\equiv 1{\pmod {7}}} ), so erhält man 8 ⋅ 2 n ≡ 4 ( mod 7 ) {\displaystyle 8\cdot 2^{n}\equiv 4{\pmod {7}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 4 ( mod 7 ) {\displaystyle 1\cdot 2^{n}\equiv 4{\pmod {7}}} .
Es ist also 7 {\displaystyle 7} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 4 ( mod 7 ) {\displaystyle 2^{n}\equiv 4{\pmod {7}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 7 ) 2 2 = 4 ≡ 4 _ ( mod 7 ) 2 3 = 8 ≡ 1 _ ( mod 7 ) 2 4 = 16 ≡ 2 _ ( mod 7 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}{\pmod {7}}\\2^{2}&=&4&\equiv &{\underline {4}}{\pmod {7}}\\2^{3}&=&8&\equiv &{\underline {1}}{\pmod {7}}\\2^{4}&=&16&\equiv &{\underline {2}}{\pmod {7}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 7 {\displaystyle 7} immer einen Zykel der Länge 3 {\displaystyle 3} der Form ( 2 , 4 , 1 ) {\displaystyle (2,4,1)} .
Es ist also 2 n ≡ 4 ( mod 7 ) {\displaystyle 2^{n}\equiv 4{\pmod {7}}} genau dann, wenn n ≡ 2 ( mod 3 ) {\displaystyle n\equiv 2{\pmod {3}}} ist.
7 {\displaystyle 7} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 2 ( mod 3 ) {\displaystyle n\equiv 2{\pmod {3}}} ist.
Teil 4: Teilbarkeit durch 13:
Es ist 509203 = 39169 ⋅ 13 + 6 ≡ 6 ( mod 13 ) {\displaystyle 509203=39169\cdot 13+6\equiv 6{\pmod {13}}} . Somit gilt:
13 {\displaystyle 13} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 13 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {13}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 13 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {13}}} genau dann, wenn 6 ⋅ 2 n ≡ 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} , nämlich mit 11 {\displaystyle 11} (es ist 6 ⋅ 11 = 66 ≡ 1 ( mod 13 ) {\displaystyle 6\cdot 11=66\equiv 1{\pmod {13}}} ), so erhält man 66 ⋅ 2 n ≡ 11 ( mod 13 ) {\displaystyle 66\cdot 2^{n}\equiv 11{\pmod {13}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 11 ( mod 13 ) {\displaystyle 1\cdot 2^{n}\equiv 11{\pmod {13}}} .
Es ist also 13 {\displaystyle 13} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 11 ( mod 13 ) {\displaystyle 2^{n}\equiv 11{\pmod {13}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 13 ) 2 2 = 4 ≡ 4 _ ( mod 13 ) 2 3 = 8 ≡ 8 _ ( mod 13 ) 2 4 = 16 ≡ 3 _ ( mod 13 ) 2 5 = 32 ≡ 6 _ ( mod 13 ) 2 6 = 64 ≡ 12 _ ( mod 13 ) 2 7 = 128 ≡ 11 _ ( mod 13 ) 2 8 = 256 ≡ 9 _ ( mod 13 ) 2 9 = 512 ≡ 5 _ ( mod 13 ) 2 10 = 1024 ≡ 10 _ ( mod 13 ) 2 11 = 2048 ≡ 7 _ ( mod 13 ) 2 12 = 4096 ≡ 1 _ ( mod 13 ) 2 13 = 8192 ≡ 2 _ ( mod 13 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {13}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {13}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {13}}\\2^{4}&=&16&\equiv &{\underline {3}}&{\pmod {13}}\\2^{5}&=&32&\equiv &{\underline {6}}&{\pmod {13}}\\2^{6}&=&64&\equiv &{\underline {12}}&{\pmod {13}}\\2^{7}&=&128&\equiv &{\underline {11}}&{\pmod {13}}\\2^{8}&=&256&\equiv &{\underline {9}}&{\pmod {13}}\\2^{9}&=&512&\equiv &{\underline {5}}&{\pmod {13}}\\2^{10}&=&1024&\equiv &{\underline {10}}&{\pmod {13}}\\2^{11}&=&2048&\equiv &{\underline {7}}&{\pmod {13}}\\2^{12}&=&4096&\equiv &{\underline {1}}&{\pmod {13}}\\2^{13}&=&8192&\equiv &{\underline {2}}&{\pmod {13}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 13 {\displaystyle 13} immer einen Zykel der Länge 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 ≡ 11 ( mod 13 ) {\displaystyle 2^{n}\equiv 11{\pmod {13}}} genau dann, wenn n ≡ 7 ( mod 12 ) {\displaystyle n\equiv 7{\pmod {12}}} ist.
13 {\displaystyle 13} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 7 ( mod 12 ) {\displaystyle n\equiv 7{\pmod {12}}} ist.
Teil 5: Teilbarkeit durch 17:
Es ist 509203 = 29953 ⋅ 17 + 2 ≡ 2 ( mod 17 ) {\displaystyle 509203=29953\cdot 17+2\equiv 2{\pmod {17}}} . Somit gilt:
17 {\displaystyle 17} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 17 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {17}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 17 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {17}}} genau dann, wenn 2 ⋅ 2 n ≡ 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} , nämlich mit 9 {\displaystyle 9} (es ist 2 ⋅ 9 = 18 ≡ 1 ( mod 17 ) {\displaystyle 2\cdot 9=18\equiv 1{\pmod {17}}} ), so erhält man 18 ⋅ 2 n ≡ 9 ( mod 17 ) {\displaystyle 18\cdot 2^{n}\equiv 9{\pmod {17}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 9 ( mod 17 ) {\displaystyle 1\cdot 2^{n}\equiv 9{\pmod {17}}} .
Es ist also 17 {\displaystyle 17} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 9 ( mod 17 ) {\displaystyle 2^{n}\equiv 9{\pmod {17}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 17 ) 2 2 = 4 ≡ 4 _ ( mod 17 ) 2 3 = 8 ≡ 8 _ ( mod 17 ) 2 4 = 16 ≡ 16 _ ( mod 17 ) 2 5 = 32 ≡ 15 _ ( mod 17 ) 2 6 = 64 ≡ 13 _ ( mod 17 ) 2 7 = 128 ≡ 9 _ ( mod 17 ) 2 8 = 256 ≡ 1 _ ( mod 17 ) 2 9 = 512 ≡ 2 _ ( mod 17 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {17}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {17}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {17}}\\2^{4}&=&16&\equiv &{\underline {16}}&{\pmod {17}}\\2^{5}&=&32&\equiv &{\underline {15}}&{\pmod {17}}\\2^{6}&=&64&\equiv &{\underline {13}}&{\pmod {17}}\\2^{7}&=&128&\equiv &{\underline {9}}&{\pmod {17}}\\2^{8}&=&256&\equiv &{\underline {1}}&{\pmod {17}}\\2^{9}&=&512&\equiv &{\underline {2}}&{\pmod {17}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 17 {\displaystyle 17} immer einen Zykel der Länge 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 ≡ 9 ( mod 17 ) {\displaystyle 2^{n}\equiv 9{\pmod {17}}} genau dann, wenn n ≡ 7 ( mod 8 ) {\displaystyle n\equiv 7{\pmod {8}}} ist.
17 {\displaystyle 17} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 7 ( mod 8 ) {\displaystyle n\equiv 7{\pmod {8}}} ist.
Teil 6: Teilbarkeit durch 241:
Es ist 509203 = 2112 ⋅ 241 + 211 ≡ 211 ( mod 241 ) {\displaystyle 509203=2112\cdot 241+211\equiv 211{\pmod {241}}} . Somit gilt:
241 {\displaystyle 241} teilt 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 509203 ⋅ 2 n − 1 ≡ 0 ( mod 241 ) {\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {241}}} genau dann, wenn 509203 ⋅ 2 n ≡ 1 ( mod 241 ) {\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {241}}} genau dann, wenn 211 ⋅ 2 n ≡ 1 ( mod 241 ) {\displaystyle 211\cdot 2^{n}\equiv 1{\pmod {241}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 211 {\displaystyle 211} modulo 241 {\displaystyle 241} , nämlich mit 8 {\displaystyle 8} (es ist 211 ⋅ 8 = 1688 ≡ 1 ( mod 241 ) {\displaystyle 211\cdot 8=1688\equiv 1{\pmod {241}}} ), so erhält man 1688 ⋅ 2 n ≡ 8 ( mod 241 ) {\displaystyle 1688\cdot 2^{n}\equiv 8{\pmod {241}}} , was gleichwertig ist mit 1 ⋅ 2 n ≡ 8 ( mod 241 ) {\displaystyle 1\cdot 2^{n}\equiv 8{\pmod {241}}} .
Es ist also 241 {\displaystyle 241} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn 2 n ≡ 8 ( mod 241 ) {\displaystyle 2^{n}\equiv 8{\pmod {241}}} ist.
Es gilt:
2 1 = 2 ≡ 2 _ ( mod 241 ) 2 2 = 4 ≡ 4 _ ( mod 241 ) 2 3 = 8 ≡ 8 _ ( mod 241 ) 2 4 = 16 ≡ 16 _ ( mod 241 ) 2 5 = 32 ≡ 32 _ ( mod 241 ) 2 6 = 64 ≡ 64 _ ( mod 241 ) 2 7 = 128 ≡ 128 _ ( mod 241 ) 2 8 = 256 ≡ 15 _ ( mod 241 ) 2 9 = 512 ≡ 30 _ ( mod 241 ) 2 10 = 1024 ≡ 60 _ ( mod 241 ) 2 11 = 2048 ≡ 120 _ ( mod 241 ) 2 12 = 4096 ≡ 240 _ ( mod 241 ) 2 13 = 8192 ≡ 239 _ ( mod 241 ) 2 14 = 16384 ≡ 237 _ ( mod 241 ) 2 15 = 32768 ≡ 233 _ ( mod 241 ) 2 16 = 65536 ≡ 225 _ ( mod 241 ) 2 17 = 131072 ≡ 209 _ ( mod 241 ) 2 18 = 262144 ≡ 177 _ ( mod 241 ) 2 19 = 524288 ≡ 113 _ ( mod 241 ) 2 20 = 1048576 ≡ 226 _ ( mod 241 ) 2 21 = 2097152 ≡ 211 _ ( mod 241 ) 2 22 = 4194304 ≡ 181 _ ( mod 241 ) 2 23 = 8388608 ≡ 121 _ ( mod 241 ) 2 24 = 16777216 ≡ 1 _ ( mod 241 ) 2 25 = 33554432 ≡ 2 _ ( mod 241 ) {\displaystyle {\begin{aligned}2^{1}&=&2&\equiv &{\underline {2}}&{\pmod {241}}\\2^{2}&=&4&\equiv &{\underline {4}}&{\pmod {241}}\\2^{3}&=&8&\equiv &{\underline {8}}&{\pmod {241}}\\2^{4}&=&16&\equiv &{\underline {16}}&{\pmod {241}}\\2^{5}&=&32&\equiv &{\underline {32}}&{\pmod {241}}\\2^{6}&=&64&\equiv &{\underline {64}}&{\pmod {241}}\\2^{7}&=&128&\equiv &{\underline {128}}&{\pmod {241}}\\2^{8}&=&256&\equiv &{\underline {15}}&{\pmod {241}}\\2^{9}&=&512&\equiv &{\underline {30}}&{\pmod {241}}\\2^{10}&=&1024&\equiv &{\underline {60}}&{\pmod {241}}\\2^{11}&=&2048&\equiv &{\underline {120}}&{\pmod {241}}\\2^{12}&=&4096&\equiv &{\underline {240}}&{\pmod {241}}\\2^{13}&=&8192&\equiv &{\underline {239}}&{\pmod {241}}\\2^{14}&=&16384&\equiv &{\underline {237}}&{\pmod {241}}\\2^{15}&=&32768&\equiv &{\underline {233}}&{\pmod {241}}\\2^{16}&=&65536&\equiv &{\underline {225}}&{\pmod {241}}\\2^{17}&=&131072&\equiv &{\underline {209}}&{\pmod {241}}\\2^{18}&=&262144&\equiv &{\underline {177}}&{\pmod {241}}\\2^{19}&=&524288&\equiv &{\underline {113}}&{\pmod {241}}\\2^{20}&=&1048576&\equiv &{\underline {226}}&{\pmod {241}}\\2^{21}&=&2097152&\equiv &{\underline {211}}&{\pmod {241}}\\2^{22}&=&4194304&\equiv &{\underline {181}}&{\pmod {241}}\\2^{23}&=&8388608&\equiv &{\underline {121}}&{\pmod {241}}\\2^{24}&=&16777216&\equiv &{\underline {1}}&{\pmod {241}}\\2^{25}&=&33554432&\equiv &{\underline {2}}&{\pmod {241}}\end{aligned}}}
etc.
Somit durchlaufen die Zweierpotenzen modulo 241 {\displaystyle 241} immer einen Zykel der Länge 24 {\displaystyle 24} der Form ( 2 , 4 , 8 , 16 , 32 , 64 , 128 , 15 , 30 , 60 , 120 , 240 , 239 , 237 , 233 , 225 , 209 , 177 , 113 , 226 , 211 , 181 , 121 , 1 ) {\displaystyle (2,4,8,16,32,64,128,15,30,60,120,240,239,237,233,225,209,177,113,226,211,181,121,1)} .
Es ist also 2 n ≡ 8 ( mod 241 ) {\displaystyle 2^{n}\equiv 8{\pmod {241}}} genau dann, wenn n ≡ 3 ( mod 24 ) {\displaystyle n\equiv 3{\pmod {24}}} ist.
241 {\displaystyle 241} ist somit ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann, wenn n ≡ 3 ( mod 24 ) {\displaystyle n\equiv 3{\pmod {24}}} ist.
Teil 7: Zusammenfassung:
In den vergangenen sechs Teilen dieses Beweises wurden alle möglichen Kongruenzen modulo 24 {\displaystyle 24} abgedeckt. Es wurde zum Beispiel gezeigt, dass 3 {\displaystyle 3} ein Teiler von 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} genau dann ist, wenn n ≡ 0 ( mod 2 ) {\displaystyle n\equiv 0{\pmod {2}}} gilt, also wenn n ≡ k ( mod 24 ) {\displaystyle n\equiv k{\pmod {24}}} mit k ∈ { 0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 , 22 } {\displaystyle k\in \{0,2,4,6,8,10,12,14,16,18,20,22\}} ist.
Zusammenfassend gilt also:
509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} ist, abhängig von n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} , unter anderem durch folgende Primzahlen teilbar:
n ≡ 0 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 1 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  teilbar n ≡ 2 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  und  7  teilbar n ≡ 3 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  241  teilbar n ≡ 4 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 5 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  und  7  teilbar n ≡ 6 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 7 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  13  und  17  teilbar n ≡ 8 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  und  7  teilbar n ≡ 9 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  teilbar n ≡ 10 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 11 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  7  teilbar n ≡ 12 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 13 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  teilbar n ≡ 14 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  und  7  teilbar n ≡ 15 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  17  teilbar n ≡ 16 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 17 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  und  7  teilbar n ≡ 18 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 19 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  13  teilbar n ≡ 20 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  und  7  teilbar n ≡ 21 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  5  teilbar n ≡ 22 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  3  teilbar n ≡ 23 ( mod 24 ) ⟹ 509203 ⋅ 2 n − 1  ist durch  7  und  17  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 0{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 1{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 2{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 3{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}241{\text{ teilbar}}\\n\equiv 4{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 5{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ und }}7{\text{ teilbar}}\\n\equiv 6{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 7{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}13{\text{ und }}17{\text{ teilbar}}\\n\equiv 8{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 9{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 10{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 11{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 12{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 13{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 14{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 15{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 16{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 17{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ und }}7{\text{ teilbar}}\\n\equiv 18{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 19{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 20{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ und }}7{\text{ teilbar}}\\n\equiv 21{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 22{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}3{\text{ teilbar}}\\n\equiv 23{\pmod {24}}&\Longrightarrow &509203\cdot 2^{n}-1{\text{ ist durch }}7{\text{ und }}17{\text{ teilbar}}\end{array}}}
Damit werden alle möglichen n {\displaystyle n} abgedeckt. Somit ist 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} immer durch mindestens eine Primzahl teilbar, welche in der Menge { 3 , 5 , 7 , 13 , 17 , 241 } {\displaystyle \{3,5,7,13,17,241\}} liegt. Weil 509203 ⋅ 2 n − 1 > 241 {\displaystyle 509203\cdot 2^{n}-1>241} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} ist, ist 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} immer eine zusammengesetzte Zahl, was zu beweisen war. ◻ {\displaystyle \Box }
  • 1956 bewies Hans Riesel, dass es unendlich viele ganze Zahlen k {\displaystyle k} gibt, so dass k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} nicht prim, also zusammengesetzt ist für alle positiven ganzen Zahlen n {\displaystyle n} .[6]
  • Die folgenden Zahlen sind bekannte Riesel-Zahlen k {\displaystyle k} :
509203, 762701, 777149, 790841, 992077, … (Folge A101036 in OEIS)
Ist k {\displaystyle k} eine der oberen Zahlen, so ist k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} für alle n {\displaystyle n} zusammengesetzt. Man erhält niemals eine Primzahl.

Gegenbeispiel

Die Zahl k = 23 {\displaystyle k=23} ist keine Riesel-Zahl, da in der Folge 23 ⋅ 2 n − 1 {\displaystyle 23\cdot 2^{n}-1} wenigstens eine Primzahl auftritt: 45, 91, 183, 367.

Die kleinste Riesel-Zahl

Riesel selbst fand 1956 mit 509.203 eine Riesel-Zahl. Es ist jedoch noch nicht bekannt, ob 509.203 die kleinste Riesel-Zahl ist (dieses Problem nennt man Riesel-Problem). Um dies zu beweisen, muss man noch die folgenden 42 Zahlen kontrollieren, ob sie Riesel-Zahlen sind oder nicht[7]:

23669, 31859, 38473, 46663, 67117, 74699, 81041, 107347, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557 und 494743

Es würde ausreichen, wenn man zu jeder der obigen Zahlen k {\displaystyle k} wenigstens ein einziges n {\displaystyle n} finden würde, sodass k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} eine Primzahl ist. Dann würde diese Zahl k als Kandidat für die kleinste Riesel-Zahl ausscheiden.

Brier-Zahl

Durch Eric Brier wurde nach positiven ganzen Zahlen k gesucht, die gleichzeitig Sierpiński- und Riesel-Zahl sind, d. h.

k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} und k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1}

sind für alle n stets zusammengesetzt. Derartige Zahlen heißen Brier-Zahlen.

Die erste 1998 gefundene Brier-Zahl ist die 41-stellige

k = 29364695660123543278115025405114452910889

Yves Gallot ermittelte 2000 eine 27-stellige Brier-Zahl

k = 878503122374924101526292469

2007 fanden Michael Filaseta, Carrie Finch und Mark Kozek die damals kleinste bekannte 24-stellige Brier-Zahl

k = 143665583045350793098657

Mittlerweile kennt man noch kleinere, aber immer noch mindestens 22-stellige Brier-Zahlen:

3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, … (Folge A076335 in OEIS)

Duales Sierpiński-Problem

Bisher musste das n {\displaystyle n} bei k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} immer eine positive ganze Zahl sein, also n ≥ 1 , n ∈ N {\displaystyle n\geq 1,n\in \mathbb {N} } . Was passiert aber, wenn man die Hochzahl negativ werden lässt? Sei also m ∈ Z − {\displaystyle m\in \mathbb {Z} ^{-}} mit m := − n {\displaystyle m:=-n} . Dann erhält man k ⋅ 2 m + 1 = k ⋅ 2 − n + 1 = k ⋅ 1 2 n + 1 = k 2 n + 2 n 2 n = k + 2 n 2 n = 2 n + k 2 n {\displaystyle k\cdot 2^{m}+1=k\cdot 2^{-n}+1=k\cdot {\frac {1}{2^{n}}}+1={\frac {k}{2^{n}}}+{\frac {2^{n}}{2^{n}}}={\frac {k+2^{n}}{2^{n}}}={\frac {2^{n}+k}{2^{n}}}} . Nimmt man nur den Zähler dieser Bruchzahl, so erhält man die Zahl 2 n + k {\displaystyle 2^{n}+k} .

Eine duale Sierpiński-Zahl ist eine ungerade natürliche Zahl k {\displaystyle k} , für die 2 n + k {\displaystyle 2^{n}+k} für alle natürlichen Zahlen n {\displaystyle n} zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt bzw. gab zwei Vermutungen, diese dualen Sierpiński-Zahlen betreffend:

  • Vermutung 1: Die Menge dieser dualen Sierpiński-Zahlen k {\displaystyle k} ist ident zur Menge der Sierpiński-Zahlen. Dies zu beweisen ist das duale Sierpiński-Problem.
  • Vermutung 2: Die Zahl k = 78557 {\displaystyle k=78557} ist die kleinste duale Sierpiński-Zahl. Diese zweite Vermutung konnte schon bewiesen werden. Das bedeutet, dass 2 n + 78557 {\displaystyle 2^{n}+78557} für alle natürlichen Zahlen n {\displaystyle n} zusammengesetzt ist. Gleichzeitig dürfte k = 78557 {\displaystyle k=78557} aber auch die kleinste Sierpiński-Zahl sein (siehe Sierpiński-Problem).

Es gibt also kein k {\displaystyle k} , welches kleiner als 78557 {\displaystyle 78557} ist, für welches 2 n + k {\displaystyle 2^{n}+k} niemals eine Primzahl ergibt. Dieser Beweis gelang wie schon beim noch laufenden Internet-Projekt Seventeen or Bust durch die Brute-Force-Methode, indem man für jedes k {\displaystyle k} so lange ein geeignetes n {\displaystyle n} sucht, bis man eines gefunden hat, für welches 2 n + k {\displaystyle 2^{n}+k} eine Primzahl ergibt. Dieses Internet-Projekt mit dem Namen Five or Bust[8] hat somit seinen Zweck erfüllt und aus einer Vermutung eine Gewissheit gemacht (der Name kommt von fünf verschiedenen k {\displaystyle k} , die damals noch zu keiner bekannten Primzahl geführt haben). Jedenfalls brachte auch dieser Beweis einige sehr große Primzahlen zu Tage. Die fünf k {\displaystyle k} , von denen man vor dem Projekt keine Primzahlen gekannt hat, lauteten:

k=2131, 28433, 40291, 41693 und 75353

Es wurde mittlerweile zu jedem dieser k {\displaystyle k} eine passende Zahl n {\displaystyle n} gefunden, sodass 2 n + k {\displaystyle 2^{n}+k} höchstwahrscheinlich eine Primzahl ist. Genau genommen handelt es sich bei den so gefundenen Zahlen der Form 2 n + k {\displaystyle 2^{n}+k} nur um PRP-Zahlen (sogenannte probable primes), also Zahlen, die höchstwahrscheinlich, aber eben nicht hundertprozentig, Primzahlen sind. Dies hängt damit zusammen, dass man für Zahlen der Form 2 n + k {\displaystyle 2^{n}+k} noch keine geeigneten Algorithmen kennt, die explizit garantieren könnten, dass es sich um Primzahlen handelt. Trotzdem ist man sich sehr sicher, dass es sich um Primzahlen handelt. In der Folge wird also, um genau zu sein, nicht von Primzahlen, sondern von PRP-Zahlen die Rede sein.

Bei k = 2131 {\displaystyle k=2131} erhält man erst bei n = 4583176 {\displaystyle n=4583176} eine PRP-Zahl[9], das heißt, dass 2 4583176 + 2131 {\displaystyle 2^{4583176}+2131} die kleinste PRP-Zahl ist, die in der Folge 2 n + 2131 {\displaystyle 2^{n}+2131} vorkommt. Weitere hohe PRP-Zahlen erhält man für k = 40291 {\displaystyle k=40291} und k = 41693 {\displaystyle k=41693} , nämlich n = 9092392 {\displaystyle n=9092392} bzw. n = 5146295 {\displaystyle n=5146295} (somit sind 2 9092392 + 40291 {\displaystyle 2^{9092392}+40291} und 2 5146295 + 41693 {\displaystyle 2^{5146295}+41693} PRP-Zahlen[9]). Gleichzeitig erhält man aber für diese drei k {\displaystyle k} sehr schnell Primzahlen der Form k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} , nämlich 2131 ⋅ 2 44 + 1 {\displaystyle 2131\cdot 2^{44}+1} , 40291 ⋅ 2 8 + 1 {\displaystyle 40291\cdot 2^{8}+1} und 41693 ⋅ 2 33 + 1 {\displaystyle 41693\cdot 2^{33}+1} . Für das eigentliche Sierpiński-Problem machen diese drei k {\displaystyle k} also keinerlei Schwierigkeiten. Umgekehrt kennt man zum Beispiel für k = 21181 {\displaystyle k=21181} noch kein geeignetes n {\displaystyle n} , sodass 21181 ⋅ 2 n + 1 {\displaystyle 21181\cdot 2^{n}+1} eine Primzahl ergibt (es ist eines der fünf übrig gebliebenen Problemfälle beim Projekt Seventeen or Bust). Beim dualen Sierpiński-Problem macht dieses k {\displaystyle k} aber kein Problem, denn schon für n = 28 {\displaystyle n=28} erhält man die Primzahl 2 28 + 21181 {\displaystyle 2^{28}+21181} .

In einer Tabelle zusammengefasst erkennt man die jeweils sechs größten Primzahlen beim Sierpiński-Problem und beim dualen Sierpiński-Problem bis zu k = 78557 {\displaystyle k=78557} :

Sierpiński-Problem duales Sierpiński-Problem
k n Stellen von k·2n+1 n Stellen von 2n+k
2.131 44 17 4583176 1379674
8.543 5793 1748 1191375 358640
10.223 31172165 9383761 19 6
21.181 unbekannt, sehr groß 28 9
22.699 unbekannt, sehr groß 26 8
24.737 unbekannt, sehr groß 17 6
28.433 7830457 2357207 2249255 677094
40.291 8 8 9092392 2737083
41.693 33 15 5146295 1549190
55.459 unbekannt, sehr groß 14 5
67.607 unbekannt, sehr groß 46549 14013
75.353 1 6 1518191 457022

Die kleinsten n {\displaystyle n} , für die 2 n + k {\displaystyle 2^{n}+k} erstmals eine Primzahl ergibt (wobei k {\displaystyle k} ungerade ist) verrät die folgende Liste:

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 2, 1, 1, 4, 2, 1, 2, 1, 1, 2, 1, 5, 2, 1, 3, 2, 1, 1, 8, 2, 1, 2, 1, 1, 4, 2, 1, 2, 1, 7, 2, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 7, 4, 5, 3, 4, 2, 1, 2, 1, 3, 2, 1, 1, 10, 3, 3, 2, 1, 1, … (Folge A067760 in OEIS)

Wie man erkennen kann, sind die Hochzahlen n {\displaystyle n} , die zu einem gegebenen k {\displaystyle k} erstmals eine auf eine Primzahl führen, meistens sehr klein. In den meisten Fällen ist tatsächlich n < k {\displaystyle n<k} . Es existieren lediglich einige wenige Fälle, bei denen man zu einem gegebenen k {\displaystyle k} ein sehr hohes n {\displaystyle n} benötigt, um erstmals eine Primzahl zu finden. Die folgende Liste gibt alle 28 existierenden k {\displaystyle k} bis inklusive 78557 an, die ein dementsprechend hohes n {\displaystyle n} benötigen, damit 2 n + k {\displaystyle 2^{n}+k} eine Primzahl ergibt (oder, wie im Fall k = 78557 {\displaystyle k=78557} , keine Primzahl existiert) und für welches auch n > k {\displaystyle n>k} gilt. (eine umgekehrte Argumentation lautet: zu folgenden ungeraden k {\displaystyle k} ist die Zahl 2 n + k {\displaystyle 2^{n}+k} für alle n < k {\displaystyle n<k} immer zusammengesetzt):

773, 2131, 2491, 4471, 5101, 7013, 8543, 10711, 14717, 17659, 19081, 19249, 20273, 21661, 22193, 28433, 35461, 37967, 39079, 40291, 41693, 48527, 60443, 60451, 60947, 64133, 75353, 78557 (Folge A033919 in OEIS)

Gerades Sierpiński-Problem

Im Gegensatz zum ursprünglichen Sierpiński-Problem, bei dem k {\displaystyle k} eine natürliche, ungerade Zahl sein muss, ist beim geraden Sierpiński-Problem das k {\displaystyle k} eine natürliche gerade Zahl. Wieder stellt sich die Frage, ob es bis k = 78557 {\displaystyle k=78557} kein gerades k {\displaystyle k} gibt, welches eine Sierpiński-Zahl ist[10].

Im Gegensatz zum ursprünglichen Sierpiński-Problem kann man diesmal gleich von vornherein viele gerade k {\displaystyle k} ausschließen. Wenn man zum Beispiel wegen der Untersuchung der k {\displaystyle k} vom Sierpiński-Problem weiß, dass 5107 ⋅ 2 8 + 1 {\displaystyle 5107\cdot 2^{8}+1} eine Primzahl ist, kann man daraus sofort folgern, dass 5107 ⋅ 2 ⋅ 2 7 + 1 = 10214 ⋅ 2 7 + 1 {\displaystyle 5107\cdot 2\cdot 2^{7}+1=10214\cdot 2^{7}+1} auch eine Primzahl ist und man kann somit k = 10214 {\displaystyle k=10214} sofort aus der Liste der potentiellen geraden Sierpiński-Zahlen streichen. Ebenso ist 5107 ⋅ 2 2 ⋅ 2 6 + 1 = 20428 ⋅ 2 6 + 1 {\displaystyle 5107\cdot 2^{2}\cdot 2^{6}+1=20428\cdot 2^{6}+1} und 5107 ⋅ 2 3 ⋅ 2 5 + 1 = 40856 ⋅ 2 5 + 1 {\displaystyle 5107\cdot 2^{3}\cdot 2^{5}+1=40856\cdot 2^{5}+1} eine Primzahl und somit scheidet auch k = 20428 {\displaystyle k=20428} und k = 40856 {\displaystyle k=40856} sofort als gerader Sierpiński-Kandidat aus, ohne dass man eine besondere Rechnung angestellt haben muss.

Es gibt aber auch gerade k {\displaystyle k} , bei denen man mit der sonst üblichen Brute-Force-Methode arbeiten muss. Zum Beispiel stößt man bei der Lösung des ursprünglichen Sierpiński-Problems auf die Primzahl 5111 ⋅ 2 1 + 1 {\displaystyle 5111\cdot 2^{1}+1} . In diesem Fall kann man aber leider keine 2 herausheben, sodass man über k = 10222 {\displaystyle k=10222} eine Aussage treffen könnte. Somit muss man für dieses k {\displaystyle k} mit roher Rechengewalt eine Primzahl finden. Hat man aber eine gefunden, in diesem Fall 10222 ⋅ 2 6 + 1 {\displaystyle 10222\cdot 2^{6}+1} , so kann man wieder weitere k {\displaystyle k} ausschließen. In diesem Fall k = 20444 {\displaystyle k=20444} und k = 40888 {\displaystyle k=40888} .

Momentan gibt es für das gerade Sierpiński-Problem 4 Zahlen, für die man noch nicht ausschließen kann, dass sie Sierpiński-Zahlen sind:

42362, 45398, 49474, 65536

Drei dieser vier Zahlen sind eng verwandt mit den 5 Problemfällen vom ursprünglichen Sierpiński-Problem (21181, 22699, 24737, 55459 und 67607). Wenn man zum Beispiel für k = 21181 {\displaystyle k=21181} irgendwann einmal eine Primzahl der Form 21181 ⋅ 2 n + 1 {\displaystyle 21181\cdot 2^{n}+1} finden wird (mit einem sehr hohen n {\displaystyle n} ), kann man sofort daraus schließen, dass 21181 ⋅ 2 ⋅ 2 n − 1 + 1 = 42362 ⋅ 2 n − 1 + 1 {\displaystyle 21181\cdot 2\cdot 2^{n-1}+1=42362\cdot 2^{n-1}+1} ebenfalls eine Primzahl ist und schon hätte das gerade Sierpiński-Problem nur noch 3 Problemfälle. Analog kann man aus einer noch zu findenden Primzahl der Form 22699 ⋅ 2 n + 1 {\displaystyle 22699\cdot 2^{n}+1} sofort folgern, dass auch 45398 ⋅ 2 n − 1 + 1 {\displaystyle 45398\cdot 2^{n-1}+1} eine Primzahl ist (nämlich die gleiche). Weiters wäre die noch unentdeckte Primzahl der Form 24737 ⋅ 2 n + 1 = 49474 ⋅ 2 n − 1 + 1 {\displaystyle 24737\cdot 2^{n}+1=49474\cdot 2^{n-1}+1} eine Lösung, die aus der Liste der obigen 4 Zahlen nur noch einen einzigen Problemfall übrig lassen würden: k = 65536 {\displaystyle k=65536} .

Es stellt sich die Frage, ob 65536 ⋅ 2 n + 1 {\displaystyle 65536\cdot 2^{n}+1} jemals eine Primzahl werden kann. Es ist 65536 = 2 16 {\displaystyle 65536=2^{16}} und somit hätte diese gesuchte Primzahl die Form 2 16 ⋅ 2 n + 1 = 2 n + 16 + 1 =: 2 m + 1 {\displaystyle 2^{16}\cdot 2^{n}+1=2^{n+16}+1=:2^{m}+1} mit m := n + 16 {\displaystyle m:=n+16} . Primzahlen der Form 2 m + 1 {\displaystyle 2^{m}+1} sind aber Fermatsche Primzahlen, also nur prim, wenn m = 2 n {\displaystyle m=2^{n}} eine Zweierpotenz ist und somit die Form 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} haben. Von diesen sind momentan nur fünf bekannt, nämlich 2 2 0 + 1 = 3 {\displaystyle 2^{2^{0}}+1=3} , 2 2 1 + 1 = 5 {\displaystyle 2^{2^{1}}+1=5} , 2 2 2 + 1 = 17 {\displaystyle 2^{2^{2}}+1=17} , 2 2 3 + 1 = 257 {\displaystyle 2^{2^{3}}+1=257} und 2 2 4 + 1 = 65537 {\displaystyle 2^{2^{4}}+1=65537} . Pierre de Fermat vermutete zwar, dass es unendlich viele solche Fermatschen Primzahlen gibt, mittlerweile wird aber vermutet, dass es nur diese fünf Primzahlen von dieser Form gibt. Wenn es wirklich noch weitere Fermatsche Primzahlen gibt, so muss diese Zahl mindestens F 33 = 2 2 33 + 1 = 2 8589934592 + 1 {\displaystyle F_{33}=2^{2^{33}}+1=2^{8589934592}+1} sein und somit mindestens 2.585.827.973 Stellen haben (diese Fermat-Zahl F 33 {\displaystyle F_{33}} ist tatsächlich die kleinste Zahl der Form 2 n + 1 {\displaystyle 2^{n}+1} , die eine Primzahl sein könnte, von der man es aber noch nicht weiß). Die größte bekannte Primzahl hat im Moment aber lediglich 24.862.048 Stellen (eine Mersenne-Primzahl, Stand: 26. Juli 2020), welches gerade einmal 0,96 % der Stellen sind, die F 33 {\displaystyle F_{33}} besitzt. Man ist also noch meilenweit von der Primzahlbestimmung von so riesigen Zahlen entfernt. Für das gerade Sierpiński-Problem bedeutet das aber, dass man für die Zahl k = 65536 {\displaystyle k=65536} in absehbarer Zeit keine Primzahl finden wird. Möglicherweise gibt es auch tatsächlich keine Primzahl für dieses k {\displaystyle k} . Dies würde aber bedeuten, dass k = 65536 {\displaystyle k=65536} die erste gerade (und insgesamt auch kleinste) Sierpiński-Zahl wäre.

Duales Riesel-Problem

Bisher musste das n {\displaystyle n} bei k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} immer eine positive ganze Zahl sein, also n ≥ 1 , n ∈ N {\displaystyle n\geq 1,n\in \mathbb {N} } . Was passiert aber, wenn man wie schon bei den Sierpiński-Zahlen die Hochzahl negativ werden lässt? Sei also m ∈ Z − {\displaystyle m\in \mathbb {Z} ^{-}} mit m := − n {\displaystyle m:=-n} . Dann erhält man k ⋅ 2 m − 1 = k ⋅ 2 − n − 1 = k ⋅ 1 2 n − 1 = k 2 n − 2 n 2 n = k − 2 n 2 n = − ( 2 n − k ) 2 n {\displaystyle k\cdot 2^{m}-1=k\cdot 2^{-n}-1=k\cdot {\frac {1}{2^{n}}}-1={\frac {k}{2^{n}}}-{\frac {2^{n}}{2^{n}}}={\frac {k-2^{n}}{2^{n}}}={\frac {-(2^{n}-k)}{2^{n}}}} . Nimmt man nur den Betrag des Zählers dieser Bruchzahl, so erhält man die Zahl | 2 n − k | {\displaystyle |2^{n}-k|} .

Eine duale Riesel-Zahl ist eine ungerade natürliche Zahl k {\displaystyle k} , für die | 2 n − k | {\displaystyle |2^{n}-k|} für alle natürlichen Zahlen n {\displaystyle n} zusammengesetzt sind (man erhält also niemals eine Primzahl). Es gibt zwei Vermutungen, diese dualen Riesel-Zahlen betreffend:

  • Vermutung 1: Die Menge dieser dualen Riesel-Zahlen k {\displaystyle k} ist ident zur Menge der Riesel-Zahlen. Dies zu beweisen ist das duale Riesel-Problem.
  • Vermutung 2: Die Zahl k = 509203 {\displaystyle k=509203} ist die kleinste duale Riesel-Zahl. Diese zweite Vermutung resultiert allerdings aus der obigen Vermutung 1. Das bedeutet, dass | 2 n − 509203 | {\displaystyle |2^{n}-509203|} für alle natürlichen Zahlen n {\displaystyle n} zusammengesetzt ist. Gleichzeitig dürfte k = 509203 {\displaystyle k=509203} aber auch die kleinste Riesel-Zahl sein (siehe Riesel-Problem).

Die Bedingung | 2 n − k | {\displaystyle |2^{n}-k|} verrät, dass man das Problem auf zweierlei Arten angehen kann. Man stößt bei der Suche nach Primzahlen der Form 2 n − k {\displaystyle 2^{n}-k} auch auf negative Zahlen, wenn 2 n < k {\displaystyle 2^{n}<k} ist. Dieser Sachverhalt kann erlaubt sein, muss aber nicht erlaubt sein. Deswegen spaltet sich das duale Riesel-Problem in zwei Fälle auf.

Fall 1: 2n – k < 0 ist erlaubt

Dann stößt man bei der Suche nach Primzahlen der Form 2 n − k {\displaystyle 2^{n}-k} auch auf negative Zahlen, deren Beträge Primzahlen sind. In diesem Fall ist dann 2 n < k {\displaystyle 2^{n}<k} .

Unter diesen Voraussetzungen gibt es noch viele k {\displaystyle k} , für welche man noch kein geeignetes n {\displaystyle n} kennt, sodass | 2 n − k | {\displaystyle |2^{n}-k|} eine Primzahl ergibt. Die kleinste davon ist k = 2293 {\displaystyle k=2293} .

Ungerade natürliche Zahlen k {\displaystyle k} mit k > 2 n {\displaystyle k>2^{n}} , für welche k − 2 n > 0 {\displaystyle k-2^{n}>0} immer zusammengesetzte Zahlen ergeben (also niemals Primzahlen sind), nennt man de Polignac-Zahlen (eine dazu äquivalente Definition lautet: eine de Polignac-Zahl k {\displaystyle k} ist eine ungerade Zahl, die nicht die Form k = 2 n + p {\displaystyle k=2^{n}+p} mit p ∈ P {\displaystyle p\in \mathbb {P} } hat[11]). Die ersten paar solcher Zahlen verrät die folgende Liste:

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, … (Folge A006285 in OEIS)

Fall 2: 2n – k < 0 ist nicht erlaubt

Dann darf man bei der Suche nach Primzahlen der Form 2 n − k {\displaystyle 2^{n}-k} nicht auf negative Zahlen stoßen. In diesem Fall ist dann 2 n > k {\displaystyle 2^{n}>k} .

Die kleinsten n {\displaystyle n} , für die 2 n − k = p > 0 {\displaystyle 2^{n}-k=p>0} erstmals eine Primzahl ergibt, verrät die folgende Liste (aufsteigend für ungerade k=1, 3, 5, 7, 9,…):

2, 3, 3, 39, 4, 4, 4, 5, 6, 5, 5, 6, 5, 5, 5, 7, 6, 6, 11, 7, 6, 29, 6, 6, 7, 6, 6, 7, 6, 6, 6, 8, 8, 7, 7, 10, 9, 7, 8, 9, 7, 8, 7, 7, 8, 7, 8, 10, 7, 7, 26, 9, 7, 8, 7, 7, 10, 7, 7, 8, 7, 7, 7, 47, 8, 14, 9, 11, 10, 9, 10, 8, 9, 8, 8, … (Folge A096502 in OEIS)

Die ersten k {\displaystyle k} , für welche man noch kein geeignetes n {\displaystyle n} kennt, sodass 2 n − k {\displaystyle 2^{n}-k} eine Primzahl ergibt, lauten:

1871, 2293, 25229, 31511, 36971, 47107, 48959, 50171, 56351, 63431, 69427, 75989, 81253, 83381, 84491, 107857, 109649, 118567, 128263, 132217, 134557, 134579, 138847, 144337, 148091, 149797, 150179, 150641, 158369, 170531, 175709, 183313, 191759, …

Gerades Riesel-Problem

Beim geraden Riesel-Problem muss k {\displaystyle k} eine gerade natürliche Zahl sein. Es stellt sich die Frage, ob es ein gerades k < 509203 {\displaystyle k<509203} gibt, welches eine Riesel-Zahl ist (für das also alle Zahlen der Form k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} immer zusammengesetzte Zahlen, also niemals Primzahlen, sind)[12].

Wie schon beim geraden Sierpiński-Problem kann man gleich von vornherein viele gerade k {\displaystyle k} ausschließen. Zum Beispiel weiß man wegen der Untersuchung der k {\displaystyle k} vom Riesel-Problem, dass 119 ⋅ 2 12 − 1 = 487423 {\displaystyle 119\cdot 2^{12}-1=487423} eine Primzahl ist und somit k = 119 {\displaystyle k=119} als Riesel-Zahl nicht in Frage kommt. Aus dieser Tatsache kann man aber sofort folgern, dass auch 119 ⋅ 2 ⋅ 2 11 − 1 = 238 ⋅ 2 11 − 1 = 487423 {\displaystyle 119\cdot 2\cdot 2^{11}-1=238\cdot 2^{11}-1=487423} und 119 ⋅ 2 2 ⋅ 2 10 − 1 = 476 ⋅ 2 10 − 1 = 487423 {\displaystyle 119\cdot 2^{2}\cdot 2^{10}-1=476\cdot 2^{10}-1=487423} und 119 ⋅ 2 3 ⋅ 2 9 − 1 = 952 ⋅ 2 9 − 1 = 487423 {\displaystyle 119\cdot 2^{3}\cdot 2^{9}-1=952\cdot 2^{9}-1=487423} und so fort, Primzahlen sind, die somit für das gerade Riesel-Problem als potentielle gerade Riesel-Zahlen ausfallen. Wegen dieses einen erfolgreich ausgeschlossenen k = 119 {\displaystyle k=119} kann man also sofort, ohne längere Rechnung, elf Werte für k {\displaystyle k} , nämlich k=238, 476, 952, 1904, 3808, 7616, 15232, 30464, 60928, 121856 und 243712 ausschließen. Erst bei 119 ⋅ 2 11 ⋅ 2 1 − 1 = 243712 ⋅ 2 1 − 1 = 487423 {\displaystyle 119\cdot 2^{11}\cdot 2^{1}-1=243712\cdot 2^{1}-1=487423} kann man keine 2 mehr herausheben, da man sonst 119 ⋅ 2 12 ⋅ 2 0 − 1 = 487424 ⋅ 2 0 − 1 = 487423 {\displaystyle 119\cdot 2^{12}\cdot 2^{0}-1=487424\cdot 2^{0}-1=487423} erhalten würde, wobei aber 0 als Hochzahl weder beim Sierpiński- noch beim Riesel-Problem erlaubt ist. Der Wert k = 487424 {\displaystyle k=487424} kann erst durch die Primzahl 487424 ⋅ 2 4 − 1 = 7798783 {\displaystyle 487424\cdot 2^{4}-1=7798783} als gerade Riesel-Zahl ausgeschlossen werden. Diesmal wieder durch die Brute-Force-Methode, also durch Ausnützung der rohen Rechengewalt eines Computers, der alle möglichen Werte so lange durchprobiert, bis er eine Primzahl gefunden hat. Auch aus ungeraden k {\displaystyle k} , die zu sehr niedrigen Primzahlen geführt haben, wie zum Beispiel 69 ⋅ 2 1 − 1 = 137 {\displaystyle 69\cdot 2^{1}-1=137} kann man keine weiteren geraden k {\displaystyle k} herausrechnen. Somit muss man auch für Vielfache von 69, also zuallererst für k = 2 ⋅ 69 = 138 {\displaystyle k=2\cdot 69=138} eine geeignete Primzahl finden. Ist diese gefunden, in diesem Fall 138 ⋅ 2 3 − 1 = 1103 {\displaystyle 138\cdot 2^{3}-1=1103} , so kann man wieder höhere k {\displaystyle k} ausschließen. In diesem Fall k = 276 {\displaystyle k=276} und k = 552 {\displaystyle k=552} . Dann ist man wieder bei 552 ⋅ 2 1 − 1 = 1103 {\displaystyle 552\cdot 2^{1}-1=1103} angelangt und muss für k = 1104 {\displaystyle k=1104} wieder eine neue Berechnung mit der Brute-Force-Methode beginnen.

In der Praxis sind aber die Computer heutzutage so schnell, dass man sich obige Überlegungen ersparen kann. Binnen weniger Stunden ist es möglich, mit einem geeigneten Mathematik-Programm alle k {\displaystyle k} als potentielle gerade Riesel-Kandidaten auszuschließen, die eine Hochzahl n {\displaystyle n} zwischen 2 0 = 1 {\displaystyle 2^{0}=1} und 2 13 = 16384 {\displaystyle 2^{13}=16384} haben. Der untersten Tabelle kann man entnehmen, dass damit schon 254233 k {\displaystyle k} wegfallen, also keine geraden Riesel-Zahlen sein können. Erst ab Hochzahlen n > 2 13 {\displaystyle n>2^{13}} benötigt man, je nach Rechenleistung, ein paar Tage bis Jahre.

Der unteren Tabelle kann man entnehmen, dass mit höheren Hochzahlen 2 13 < n < 2 21 {\displaystyle 2^{13}<n<2^{21}} schon die meisten k {\displaystyle k} ausgeschlossen werden konnten. Insgesamt bleiben 38 verschiedene k {\displaystyle k} übrig, für die noch kein n {\displaystyle n} gefunden werden konnte, sodass k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} eine Primzahl ist. 36 dieser 38 Zahlen sind die folgenden (Stand: 2. Mai 2021):

47338, 63718, 76946, 93326, 94676, 127436, 134234, 149398, 153892, 162082, 186652, 187678, 189352, 194278, 214694, 243778, 254872, 258014, 268468, 286094, 298796, 307784, 323338, 324164, 373304, 375356, 378704, 388556, 412462, 429388, 430886, 452306, 468686, 487556, 491122, 500054

Für diese k {\displaystyle k} wird man erst dann geeignete n {\displaystyle n} finden, wenn man für das ursprüngliche Riesel-Problem für gewisse im Moment noch problematische k {\displaystyle k} geeignete n {\displaystyle n} gefunden hat. Zum Beispiel kennt man für k = 23669 {\displaystyle k=23669} noch kein n {\displaystyle n} , sodass k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} eine Primzahl ergibt. Deswegen ist k = 23669 {\displaystyle k=23669} auch in der Liste der noch zu erledigenden k {\displaystyle k} im Abschnitt Riesel-Zahl enthalten. Hat man aber irgendwann einmal ein geeignetes n {\displaystyle n} gefunden, für welches 23669 ⋅ 2 n − 1 {\displaystyle 23669\cdot 2^{n}-1} prim ist, dann wird dieses n {\displaystyle n} sehr groß sein. Dann ist aber auch 23669 ⋅ 2 ⋅ 2 n − 1 − 1 = 47338 ⋅ 2 n − 1 − 1 {\displaystyle 23669\cdot 2\cdot 2^{n-1}-1=47338\cdot 2^{n-1}-1} eine Primzahl (nämlich dieselbe) und man kann aus der obigen Liste sofort, ohne eine besondere Rechnung angestellt zu haben, k = 47338 {\displaystyle k=47338} eliminieren. Ebenso kann man mit derselben Argumentation auch sofort die Werte k=94676, 189352 und 378704 eliminieren. Insgesamt wären sofort 4 Werte aus obiger Liste zu entfernen, wenn man irgendwann für k = 23669 {\displaystyle k=23669} eine geeignete Primzahl findet. Ebenso kann man für alle oben genannten 36 Werte Primzahlen finden. Man muss nur beim ursprünglichen Riesel-Problem die problematischen k {\displaystyle k} eliminieren, also geeignete Primzahlen der Form k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} finden.

Übrig bleiben nur noch 2 Werte für k {\displaystyle k} , die man separat untersuchen muss. Diese lauten (Stand: 15. April 2021):[13]

351134, 478214

Für diese k {\displaystyle k} sind noch keine Primzahlen der Form k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} bekannt. Wenn man zum Beispiel k = 351134 {\displaystyle k=351134} betrachtet, kann man feststellen, dass man eine Primzahl der Form 351134 ⋅ 2 n − 1 = 175567 ⋅ 2 ⋅ 2 n − 1 = 175567 ⋅ 2 n + 1 − 1 {\displaystyle 351134\cdot 2^{n}-1=175567\cdot 2\cdot 2^{n}-1=175567\cdot 2^{n+1}-1} benötigt. Beim ursprünglichen Riesel-Problem macht k = 175567 {\displaystyle k=175567} auch tatsächlich kein Problem, zumal 175567 ⋅ 2 1 − 1 = 351133 {\displaystyle 175567\cdot 2^{1}-1=351133} eine Primzahl ergibt. Nur leider kann man bei dieser Primzahl nicht 2 1 {\displaystyle 2^{1}} herausheben, denn dann würde man 175567 ⋅ 2 1 ⋅ 2 0 − 1 = 351134 ⋅ 2 0 − 1 {\displaystyle 175567\cdot 2^{1}\cdot 2^{0}-1=351134\cdot 2^{0}-1} erhalten. Für das Riesel-Problem ist eine Hochzahl 0 aber nicht erlaubt. Somit muss man eine größere Primzahl für k = 175567 {\displaystyle k=175567} suchen, damit man auch für k = 351134 {\displaystyle k=351134} eine geeignete findet. Und so eine größere Primzahl ist eben im Moment noch nicht bekannt, obwohl man schon bis n = 6650000 {\displaystyle n=6650000} gesucht hat.[14] Analog verhält es sich mit dem anderen Wert k = 478214 {\displaystyle k=478214} . In diesem Fall ist k = 239107 ⋅ 2 1 − 1 = 478214 ⋅ 2 0 − 1 = 478213 {\displaystyle k=239107\cdot 2^{1}-1=478214\cdot 2^{0}-1=478213} die momentan einzige bekannte Primzahl, wobei aber 2 0 {\displaystyle 2^{0}} nicht erlaubt ist. In diesem Fall hat man ebenfalls schon bis n = 6650000 {\displaystyle n=6650000} ergebnislos gesucht.[14]

Das gerade Riesel-Problem ist also noch längst nicht gelöst. Es könnte durchaus sein, dass man ein gerades k {\displaystyle k} finden wird, für welches k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} niemals eine Primzahl ist. Dann hätte man eine gerade Riesel-Zahl gefunden, die kleiner als 509203 ist. Es wird aber davon ausgegangen, dass es keine solche Zahl gibt.

Wie schnell findet man eine Primzahl für ein gegebenes k

Für die meisten k {\displaystyle k} findet man sehr schnell geeignete n {\displaystyle n} , sodass k ⋅ 2 n ± 1 {\displaystyle k\cdot 2^{n}\pm 1} bzw. 2 n ± k {\displaystyle 2^{n}\pm k} eine Primzahl ergibt. Um zu erkennen, wie schnell man eine Zahl n {\displaystyle n} zu einem gegebenen k {\displaystyle k} findet, sodass man erstmals eine Primzahl der jeweiligen Form erhält, definiert man f m {\displaystyle f_{m}} als die Anzahl der k {\displaystyle k} , für welche der Exponent n {\displaystyle n} im Intervall 2 m ≤ n < 2 m + 1 {\displaystyle 2^{m}\leq n<2^{m+1}} liegt. Die folgende Tabelle zeigt, wie schnell man die k {\displaystyle k} ausschließen kann. In der Tabelle werden folgende Variablen verwendet:

n {\displaystyle n} … kleinste Hochzahl, bei der man erstmals eine Primzahl der gegebenen Form erhält

x {\displaystyle x} … maximale Anzahl der Stellen von 2 n {\displaystyle 2^{n}}

f m {\displaystyle f_{m}} … Anzahl der k {\displaystyle k} , für welche man im Intervall 2 m ≤ n < 2 m + 1 {\displaystyle 2^{m}\leq n<2^{m+1}} erstmals eine Primzahl findet

k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} 2 n + k {\displaystyle 2^{n}+k} k ⋅ 2 n − 1 {\displaystyle k\cdot 2^{n}-1} 2 n − k {\displaystyle 2^{n}-k}
Sierpiński-
Problem[4] 		primes
Sierpiński-
Problem[4] 		erweitertes
Sierpiński-
Problem[4] 		gerades
Sierpiński-
Problem[15] 		duales
Sierpiński-
Problem 		Riesel-
Problem[7] 		gerades
Riesel-
Problem 		duales
Riesel-
Problem
2n<k 		duales
Riesel-
Problem
2n>k
m n x fm fm’ fm’’ fm fm fm fm fm fm
0 1 1 7238 1667 13491 7205 7707 39867 39980 42226 0
1 2 ≤ n ≤ 3 1 10194 2804 19709 10166 11622 59460 59474 66788 3
2 4 ≤ n ≤ 7 3 9582 3635 19803 9703 11091 62311 62112 71954 42
3 8 ≤ n ≤ 15 5 6272 3242 13909 6204 6161 45177 44869 48639 6220
4 16 ≤ n ≤ 31 10 3045 2140 7193 3052 1764 24478 24477 17286 199858
5 32 ≤ n ≤ 63 19 1445 1145 3197 1437 463 11668 11997 4031 33537
6 64 ≤ n ≤ 127 39 685 605 1451 629 202 5360 5459 1558 8166
7 128 ≤ n ≤ 255 77 331 322 656 351 92 2728 2671 785 3205
8 256 ≤ n ≤ 511 154 195 159 364 227 57 1337 1277 447 1449
9 512 ≤ n ≤ 1023 308 114 106 162 122 26 785 830 247 735
10 1024 ≤ n ≤ 2047 617 47 59 99 55 28 467 488 181 465
11 2048 ≤ n ≤ 4095 1233 34 45 67 38 18 289 275 131 278
12 4096 ≤ n ≤ 8191 2466 26 23 42 30 11 191 184 72 169
13 8192 ≤ n ≤ 16383 4932 11 17 30 7 4 125 140 45 108
14 16384 ≤ n ≤ 32767 9864 18 12 23 10 8 87 91 43 83
15 32768 ≤ n ≤ 65535 19729 12 5 14 18 6 62 59 31 56
16 65536 ≤ n ≤ 131071 39457 5 12 9 4 5 38 36 31 55
17 131072 ≤ n ≤ 262143 78913 5 5 3 1 3 35 45 ≤106 ≤172
18 262144 ≤ n ≤ 524287 157827 2 5 8 1 2 25 27 ≤106 ≤172
19 524288 ≤ n ≤ 1048575 315653 3 6 6 0 2 22 29 ≤106 ≤172
20 1048576 ≤ n ≤ 2097151 631306 2 3 3 0 2 18 9 ≤106 ≤172
21 2097152 ≤ n ≤ 4194303 1262612 1 1 5 4 1 13 14 ≤106 ≤172
22 4194304 ≤ n ≤ 8388607 2525223 3 2 1 5 2 8 5 ≤106 ≤172
23 8388608 ≤ n ≤ 16777215 5050445 2 1 2≤fm’’≤11 3 1 6≤fm≤50 15≤fm≤53 ≤106 ≤172
24 16777216 ≤ n ≤ 33554431 10100891 1≤fm≤6 1≤fm’≤8 ≤9 2≤fm≤6 0 ≤44 ≤38 ≤106 ≤172
>24 33554432 ≤ n >10100891 ≤5 ≤7 ≤9 ≤4 0 ≤44 ≤38 ≤106 ≤172
Summe: 39278 16029 80256 39278 39278 254601 254601 254601 254601

Sierpiński-Zahlen zur Basis b

Eine Sierpiński-Zahl zur Basis b ist eine natürliche Zahl k {\displaystyle k} , sodass k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n > 0 {\displaystyle n>0} eine zusammengesetzte Zahl ergibt. Es darf also niemals eine Primzahl herauskommen.

Für b = 2 {\displaystyle b=2} erhält man die klassischen Sierpiński-Zahlen, die weiter oben vorgestellt wurden.

Allerdings ist die Situation nicht mehr ganz so einfach wie bei den klassischen Sierpiński-Zahlen. Denn wenn man zum Beispiel b = 3 {\displaystyle b=3} wählt, kann man recht schnell erkennen, dass jedes ungerade k {\displaystyle k} eine Sierpiński-Zahl zur Basis 3 wäre, weil jede Zahl der Form k ⋅ 3 n + 1 {\displaystyle k\cdot 3^{n}+1} gerade und somit immer durch 2 teilbar ist und folglich niemals eine Primzahl ergibt (jede Potenz von 3 ist wieder ungerade, multipliziert mit einer ungeraden Zahl bleibt sie ungerade, und wegen +1 wird sie gerade). Um diese trivialen Fälle für potentiell interessante Sierpiński-Zahlen zur Basis b auszuschließen, muss man somit noch gewisse Vorkehrungen treffen, damit nur wirklich interessante, nichttriviale k {\displaystyle k} als Sierpiński-Zahlen zur Basis b in Frage kommen.

Bedingung

Die zusätzliche Bedingung für nichttriviale Sierpiński-Zahlen k {\displaystyle k} zur Basis b, sodass nicht eine einzelne Primzahl p {\displaystyle p} alle Zahlen der Form k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} teilt, ist die folgende:

ggT ⁡ ( k + 1 , b − 1 ) = 1 {\displaystyle \operatorname {ggT} (k+1,b-1)=1}

Es muss also der größte gemeinsamer Teiler von k + 1 {\displaystyle k+1} und b − 1 {\displaystyle b-1} gleich 1 {\displaystyle 1} sein.

Beweis der folgenden Behauptung: p {\displaystyle \qquad p} teilt k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n ≥ 0 {\displaystyle n\geq 0} ⟺ p {\displaystyle \Longleftrightarrow p} ist ein Teiler von ggT ⁡ ( k + 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k+1,b-1)\not =1}

Der Beweis[16] funktioniert direkt.

⟹: {\displaystyle \Longrightarrow :}

Zuerst wird gezeigt, dass wenn eine Primzahl p ≠ 1 {\displaystyle p\not =1} jedes k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n ≥ 0 {\displaystyle n\geq 0} teilt, gelten muss:
p {\displaystyle p} teilt ggT ⁡ ( k + 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k+1,b-1)} und somit ist ggT ⁡ ( k + 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k+1,b-1)\not =1} .
Angenommen, eine Primzahl p ∈ P {\displaystyle p\in \mathbb {P} } teilt k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n ≥ 0 {\displaystyle n\geq 0} . Dann teilt p {\displaystyle p} auch k ⋅ b 0 + 1 = k ⋅ 1 + 1 = k + 1 {\displaystyle k\cdot b^{0}+1=k\cdot 1+1=k+1} und k ⋅ b 1 + 1 = k ⋅ b + 1 {\displaystyle k\cdot b^{1}+1=k\cdot b+1} . Wenn p {\displaystyle p} aber sowohl k + 1 {\displaystyle k+1} als auch k ⋅ b + 1 {\displaystyle k\cdot b+1} teilt, dann teilt p {\displaystyle p} auch die Differenz dieser beider Terme, nämlich ( k ⋅ b + 1 ) − ( k + 1 ) = k ⋅ b + 1 − k − 1 = k ⋅ b − k = k ⋅ ( b − 1 ) {\displaystyle (k\cdot b+1)-(k+1)=k\cdot b+1-k-1=k\cdot b-k=k\cdot (b-1)} . Somit muss p {\displaystyle p} auch k {\displaystyle k} oder b − 1 {\displaystyle b-1} teilen. Da p {\displaystyle p} schon k + 1 {\displaystyle k+1} teilt, kann p {\displaystyle p} nicht gleichzeitig k {\displaystyle k} teilen, also ist p {\displaystyle p} ein Teiler von b − 1 {\displaystyle b-1} . Weil somit also p {\displaystyle p} ein Teiler von k + 1 {\displaystyle k+1} und b − 1 {\displaystyle b-1} sein muss, teilt p {\displaystyle p} auch den ggT ⁡ ( k + 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k+1,b-1)} . Also ist ggT ⁡ ( k + 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k+1,b-1)\not =1} .

⟸: {\displaystyle \Longleftarrow :}

Umgekehrt wird nun gezeigt, dass wenn p {\displaystyle p} ein Teiler von ggT ⁡ ( k + 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k+1,b-1)} ist, daraus gefolgert werden kann, dass p {\displaystyle p} auch ein Teiler von k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n ≥ 0 {\displaystyle n\geq 0} sein muss.
Sei also p {\displaystyle p} ein Teiler von ggT ⁡ ( k + 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k+1,b-1)} . Dann kann man mit den Rechenregeln der Kongruenz zeigen, dass gilt: k ≡ − 1 mod p {\displaystyle k\equiv -1\mod p} und b ≡ 1 mod p {\displaystyle b\equiv 1\mod p} und somit gilt:
k ⋅ b n + 1 ≡ − 1 ⋅ 1 n + 1 ≡ 0 mod p {\displaystyle k\cdot b^{n}+1\equiv -1\cdot 1^{n}+1\equiv 0\mod p}
Somit ist p {\displaystyle p} ein Teiler von k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} .

Insgesamt wurde also gezeigt, dass p {\displaystyle p} die Zahlen k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n ≥ 0 {\displaystyle n\geq 0} genau dann teilt, wenn p {\displaystyle p} ein Teiler von ggT ⁡ ( k + 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k+1,b-1)} ist. Der Beweis ist vollendet. ◻ {\displaystyle \Box }

Tabelle der Sierpiński-Zahlen zur Basis b

Um den trivialen Fall auszuschließen, bei dem lediglich eine einzige (Prim-)Zahl p {\displaystyle p} alle Zahlen der Form k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} mit n > 0 {\displaystyle n>0} teilt und somit k {\displaystyle k} schon eine gesuchte Sierpiński-Zahl zur Basis b ist, muss zusätzlich die Bedingung ggT ⁡ ( k + 1 , b − 1 ) = 1 {\displaystyle \operatorname {ggT} (k+1,b-1)=1} gefordert werden.

Nun kann man natürlich die Basis b {\displaystyle b} beliebig hoch werden lassen. Untersucht werden momentan aber „nur“ Basen bis b ≤ 1030 {\displaystyle b\leq 1030} . Es folgt eine Tabelle mit dem momentanen Wissensstand (Stand: 22. April 2024) für Basen bis b = 30 {\displaystyle b=30} :[17][18]

b vermutete kleinste
Sierpiński-Zahl k 		Problemfälle k, für die man noch keine Primzahlen kennt,
die kleiner als die vermutete kleinste Sierpiński-Zahl k
und keine Vielfachen von ebenfalls unbekannten Problemfällen sind;
in Klammern sind ausgewählte Problemfälle, die Vielfache von anderen Problemfällen sind 		größte so gefundene Primzahl
2 78557 21181, 22699, 24737, 55459, 65536, 67607
(insgesamt 6 Problemfälle) 		10223·231172165+1
3 125.050.976.086 6363484, 8911036, 12663902, 14138648, 14922034, 18302632, 21497746, 23896396, 24019448, 24677704, 33224138, 33381178, 35821276, 37063498, 39431872, 46891088, 47628292, 54503602, 56882284, 60581468,…
(diese 20 und noch 393512 weitere, also insgesamt 393532 Problemfälle) 		125030472038·3945719+1
4 66741 18534, 21181, 22699, 49474, 55459, 64494, 65536
(insgesamt 7 Problemfälle) 		20446·415586082+1
5 159986 6436, 7528, 10918, 26798, 29914, 31712, 36412, 41738, 44348, 44738, 45748, 51208, 58642, 60394, 62698, 64258, 67612, 67748, 71492, 74632, 76724, 83936, 84284, 90056, 92906, 93484, 105464, 126134, 139196, 152588
(insgesamt 30 Problemfälle) 		118568·53112069+1
6 174308 1296, 13215, 14505, 50252, 76441, 87800, 97131, 112783, 127688, 166753, 168610
(insgesamt 11 Problemfälle) 		124125·62018254+1
7 1.112.646.039.348 987144, 1613796, 1911142, 2052426, 2471044, 3778846, 4023946, 4300896, 4369704, 4455408, 4723986, 4783794, 4810884, 5673636, 6551056, 7115518, 7248984, 8186656, 8643682, 9230674,…
(diese 20 und noch 19889 weitere bis k ≤ 1.000.000.000, also bis dahin insgesamt 19909 Problemfälle) 		1952376·7293352+1
8 1 keine Problemfälle mehr keine
9 2344 keine Problemfälle mehr 2036·95004596+1
10 9175 100, 7666 5028·1083982+1
11 1490 keine Problemfälle mehr 958·11300544+1
12 521 12 404·12714558+1
13 132 keine Problemfälle mehr 48·136267+1
14 4 keine Problemfälle mehr 1·142+1
15 91.218.919.470.156 215432, 424074, 685812, 1936420, 2831648, 3100818, 3789018, 5074424, 5095268, 5311880, 5349258, 5382720, 5391260, 5437658, 5624046, 5624350, 5923260, 6022606, 6038592, 6079288, 6113172, 6201428, 6341914, 6438174, 6492284, 6729940, 6741008, 7370892, 7567724, 7759144, 7858272, 7976572, 8029172, 8340272, 8347462, 8371008, 8410850, 8446312, 8495324, 8592272, 8718584, 9051940, 9174358, 9189710, 9307436, 9352744, 9562550, 9564418, 9720238, 10033124,…
(diese 50 und noch 10312 weitere bis k ≤ 1.000.000.000, also bis dahin 10362 Problemfälle) 		3859132·15195563+1
16 2500 keine Problemfälle mehr 2158·1610905+1
17 278 244 262·17186768+1
18 398 18 122·18292318+1
19 765174 1446, 2526, 2716, 3714, 4506, 4614, 6796, 10776, 14556, 15394, 15396, 16246, 17596, 19014, 19906, 20326, 20364, 21696, 24754, 25474, 29746, 29896, 29956, 30196, 36534, 38356, 39126, 39276, 42934, 43986, 44106, 45216, 45846, 46174, 50124, 53014, 55516, 57544, 59214, 61536,…
(diese 40 und noch 485 weitere, also insgesamt 525 Problemfälle) 		256134·19199223+1
20 8 keine Problemfälle mehr 6·2015+1
21 1002 keine Problemfälle mehr 118·2119849+1
22 6694 22, 5128 1611·22738988+1
23 182 keine Problemfälle mehr 68·23365239+1
24 30651 656, 1099, 1851, 1864, 2164, 2351, 2586, 3404, 3526, 3609, 4606, 4894, 5129, 5316, 5324, 5386, 5889, 5974, 7276, 7746, 7844, 8054, 8091, 8161, 9279, 9304, 9701, 9721, 10026, 10156, 10531, 11346, 12969, 12991, 13716, 15921, 17334, 17819, 17876, 18006, 18204, 18911, 19031, 19094, 20219, 20731, 21459, 22289, 22356, 22479, 23844, 23874, 24784, 25964, 26279, 27344, 29091, 29349, 29464, 29566, 29601
(insgesamt 61 Problemfälle) 		13984·24397259+1
25 262638 222, 6436, 7528, 10918, 12864, 13548, 15588, 18576, 29914, 36412, 45330, 45748, 51208, 57240, 58434, 58642, 60394, 62698, 64258, 65610, 66678, 67612, 74632, 75666, 76896, 81186, 82962, 86334, 90240, 91038, 93378, 93484, 94212, 101958, 107472, 108720, 110304, 114516, 114726, 124164, 133990, 134172, 157548, 158560, 162756, 165270, 165504, 166620, 169324, 176916, 177022, 178972, 183028, 184414, 184456, 195016, 195144, 196236, 198840, 199174, 201382, 205906, 206982, 207544, 208690, 211860, 216282, 217140, 221304, 221740, 223690, 226992, 228982, 230998, 231328, 231390, 231906, 243108, 244438, 245010, 258942
(insgesamt 81 Problemfälle) 		138514·251385961+1
26 221 65, 155 32·26318071+1
27 8 keine Problemfälle mehr 2·272+1
28 4554 871, 4552 3394·28427262+1
29 4 keine Problemfälle mehr 2·291+1
30 867 278, 588 699·3011837+1

Wie man erkennen kann, sind für gewisse Basen b {\displaystyle b} alle Problemfälle gelöst. Das bedeutet, dass die oben genannte Sierpiński-Zahl k {\displaystyle k} tatsächlich die kleinste Sierpiński-Zahl zu dieser Basis b ist und dass folglich alle Zahlen der Form k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1} für alle n > 0 {\displaystyle n>0} zusammengesetzte Zahlen sind. Im Folgenden werden die kleinsten Teiler für die schon bewiesenen und die noch vermuteten kleinsten Sierpiński-Zahlen angegeben:[17][18]

b bewiesene kleinste
Sierpiński-Zahl k 		vermutete kleinste
Sierpiński-Zahl k 		(kleinste) Teiler von k ⋅ b n + 1 {\displaystyle k\cdot b^{n}+1}
2 78557 78557 ⋅ 2 n + 1 {\displaystyle 78557\cdot 2^{n}+1} hat immer mindestens einen der Teiler 3, 5, 7, 13, 19, 37 oder 73
3 125.050.976.086 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} hat immer mindestens einen der Teiler 5, 7, 13, 17, 19, 37, 41, 193 oder 757
4 66741 66741 ⋅ 4 n + 1 {\displaystyle 66741\cdot 4^{n}+1} hat immer mindestens einen der Teiler 5, 7, 13, 17 oder 241
5 159986 159986 ⋅ 5 n + 1 {\displaystyle 159986\cdot 5^{n}+1} hat immer mindestens einen der Teiler 3, 7, 13, 31 oder 601
6 174308 174308 ⋅ 6 n + 1 {\displaystyle 174308\cdot 6^{n}+1} hat immer mindestens einen der Teiler 7, 13, 31, 37 oder 97
7 1.112.646.039.348 1112646039348 ⋅ 7 n + 1 {\displaystyle 1112646039348\cdot 7^{n}+1} hat immer mindestens einen der Teiler 5, 13, 19, 43, 73, 181, 193 oder 1201
8 1 1 ⋅ 8 n + 1 = ( 1 ⋅ 2 n + 1 ) ⋅ ( 1 ⋅ 4 n − 1 ⋅ 2 n + 1 ) {\displaystyle 1\cdot 8^{n}+1=(1\cdot 2^{n}+1)\cdot (1\cdot 4^{n}-1\cdot 2^{n}+1)}
9 2344 2344 ⋅ 9 n + 1 {\displaystyle 2344\cdot 9^{n}+1} hat immer mindestens einen der Teiler 5, 7, 13 oder 73
10 9175 9175 ⋅ 10 n + 1 {\displaystyle 9175\cdot 10^{n}+1} hat immer mindestens einen der Teiler 7, 11, 13 oder 37
11 1490 1490 ⋅ 11 n + 1 {\displaystyle 1490\cdot 11^{n}+1} hat immer mindestens einen der Teiler 3, 7, 19 oder 37
12 521 521 ⋅ 12 n + 1 {\displaystyle 521\cdot 12^{n}+1} hat immer mindestens einen der Teiler 5, 13 oder 29
13 132 132 ⋅ 13 n + 1 {\displaystyle 132\cdot 13^{n}+1} hat immer mindestens einen der Teiler 5, 7 oder 17
14 4 4 ⋅ 14 n + 1 {\displaystyle 4\cdot 14^{n}+1} hat immer mindestens einen der Teiler 3 oder 5
15 91.218.919.470.156 91218919470156 ⋅ 15 n + 1 {\displaystyle 91218919470156\cdot 15^{n}+1} hat immer mindestens einen der Teiler 13, 17, 113, 211, 241, 1489 oder 3877
16 2500 2500 ⋅ 16 n + 1 = ( 50 ⋅ 4 n − 10 ⋅ 2 n + 1 ) ⋅ ( 50 ⋅ 4 n + 10 ⋅ 2 n + 1 ) {\displaystyle 2500\cdot 16^{n}+1=(50\cdot 4^{n}-10\cdot 2^{n}+1)\cdot (50\cdot 4^{n}+10\cdot 2^{n}+1)}
17 278 278 ⋅ 17 n + 1 {\displaystyle 278\cdot 17^{n}+1} hat immer mindestens einen der Teiler 3, 5 oder 29
18 398 398 ⋅ 18 n + 1 {\displaystyle 398\cdot 18^{n}+1} hat immer mindestens einen der Teiler 5, 13 oder 19
19 765174 765174 ⋅ 19 n + 1 {\displaystyle 765174\cdot 19^{n}+1} hat immer mindestens einen der Teiler 5, 7, 13, 127 oder 769
20 8 8 ⋅ 20 n + 1 {\displaystyle 8\cdot 20^{n}+1} hat immer mindestens einen der Teiler 3 oder 7
21 1002 1002 ⋅ 21 n + 1 {\displaystyle 1002\cdot 21^{n}+1} hat immer mindestens einen der Teiler 11, 13 oder 17
22 6694 6694 ⋅ 22 n + 1 {\displaystyle 6694\cdot 22^{n}+1} hat immer mindestens einen der Teiler 5, 23 oder 97
23 182 182 ⋅ 23 n + 1 {\displaystyle 182\cdot 23^{n}+1} hat immer mindestens einen der Teiler 3, 5 oder 53
24 30651 30651 ⋅ 24 n + 1 {\displaystyle 30651\cdot 24^{n}+1} hat immer mindestens einen der Teiler 5, 7, 13, 73 oder 79
25 262638 262638 ⋅ 25 n + 1 {\displaystyle 262638\cdot 25^{n}+1} hat immer mindestens einen der Teiler 7, 13, 31 oder 601
26 221 221 ⋅ 26 n + 1 {\displaystyle 221\cdot 26^{n}+1} hat immer mindestens einen der Teiler 3, 7, 19 oder 37
27 8 8 ⋅ 27 n + 1 = ( 2 ⋅ 3 n + 1 ) ⋅ ( 4 ⋅ 9 n − 2 ⋅ 3 n + 1 ) {\displaystyle 8\cdot 27^{n}+1=(2\cdot 3^{n}+1)\cdot (4\cdot 9^{n}-2\cdot 3^{n}+1)}
28 4554 4554 ⋅ 28 n + 1 {\displaystyle 4554\cdot 28^{n}+1} hat immer mindestens einen der Teiler 5, 29 oder 157
29 4 4 ⋅ 29 n + 1 {\displaystyle 4\cdot 29^{n}+1} hat immer mindestens einen der Teiler 3 oder 5
30 867 867 ⋅ 30 n + 1 {\displaystyle 867\cdot 30^{n}+1} hat immer mindestens einen der Teiler 7, 13, 19 oder 31

Stellvertretend für alle Sierpiński-Zahlen zur Basis b {\displaystyle b} sei hier noch der umfangreiche und ausführliche Beweis angeführt, dass k = 125.050.976.086 {\displaystyle k=125.050.976.086} eine Sierpiński-Zahl zur Basis b = 3 {\displaystyle b=3} ist:

Beweis der Behauptung, dass k = 125.050.976.086 {\displaystyle k=125.050.976.086} eine Sierpiński-Zahl zur Basis b = 3 {\displaystyle b=3} ist:

Der Beweis funktioniert direkt mittels Modulo-Rechnung.

Zu zeigen ist, dass 125.050.976.086 ⋅ 3 n + 1 {\displaystyle 125.050.976.086\cdot 3^{n}+1} für alle natürlichen Zahlen n ∈ N ∖ { 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 { 5 , 7 , 13 , 17 , 19 , 37 , 41 , 193 , 757 } {\displaystyle \{5,7,13,17,19,37,41,193,757\}} gibt, welche 125.050.976.086 ⋅ 3 n + 1 {\displaystyle 125.050.976.086\cdot 3^{n}+1} teilt (diese Menge nennt man im englischen covering set of 125.050.976.086).

Beweis:

Teil 1: Teilbarkeit durch 5:
Es ist 125050976086 = 25010195217 ⋅ 5 + 1 ≡ 1 ( mod 5 ) {\displaystyle 125050976086=25010195217\cdot 5+1\equiv 1{\pmod {5}}} . Somit gilt:
5 {\displaystyle 5} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 5 ( mod 5 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 5{\pmod {5}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 4 ( mod 5 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 4{\pmod {5}}} genau dann, wenn 1 ⋅ 3 n ≡ 4 ( mod 5 ) {\displaystyle 1\cdot 3^{n}\equiv 4{\pmod {5}}} genau dann, wenn 3 n ≡ 4 ( mod 5 ) {\displaystyle 3^{n}\equiv 4{\pmod {5}}} ist.
Es ist also 5 {\displaystyle 5} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 4 ( mod 5 ) {\displaystyle 3^{n}\equiv 4{\pmod {5}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 5 ) 3 2 = 9 ≡ 4 _ ( mod 5 ) 3 3 = 27 ≡ 2 _ ( mod 5 ) 3 4 = 81 ≡ 1 _ ( mod 5 ) 3 5 = 243 ≡ 3 _ ( mod 5 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}{\pmod {5}}\\3^{2}&=&9&\equiv &{\underline {4}}{\pmod {5}}\\3^{3}&=&27&\equiv &{\underline {2}}{\pmod {5}}\\3^{4}&=&81&\equiv &{\underline {1}}{\pmod {5}}\\3^{5}&=&243&\equiv &{\underline {3}}{\pmod {5}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 5 {\displaystyle 5} immer einen Zykel der Länge 4 {\displaystyle 4} der Form ( 3 , 4 , 2 , 1 ) {\displaystyle (3,4,2,1)} .
Es ist also 3 n ≡ 4 ( mod 5 ) {\displaystyle 3^{n}\equiv 4{\pmod {5}}} genau dann, wenn n ≡ 2 ( mod 4 ) {\displaystyle n\equiv 2{\pmod {4}}} ist.
5 {\displaystyle 5} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 2 ( mod 4 ) {\displaystyle n\equiv 2{\pmod {4}}} ist.
Teil 2: Teilbarkeit durch 7:
Es ist 125050976086 = 17864425155 ⋅ 7 + 1 ≡ 1 ( mod 7 ) {\displaystyle 125050976086=17864425155\cdot 7+1\equiv 1{\pmod {7}}} . Somit gilt:
7 {\displaystyle 7} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 7 ( mod 7 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 7{\pmod {7}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 6 ( mod 7 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 6{\pmod {7}}} genau dann, wenn 1 ⋅ 3 n ≡ 6 ( mod 7 ) {\displaystyle 1\cdot 3^{n}\equiv 6{\pmod {7}}} genau dann, wenn 3 n ≡ 6 ( mod 7 ) {\displaystyle 3^{n}\equiv 6{\pmod {7}}} ist.
Es ist also 7 {\displaystyle 7} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 6 ( mod 7 ) {\displaystyle 3^{n}\equiv 6{\pmod {7}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 7 ) 3 2 = 9 ≡ 2 _ ( mod 7 ) 3 3 = 27 ≡ 6 _ ( mod 7 ) 3 4 = 81 ≡ 4 _ ( mod 7 ) 3 5 = 243 ≡ 5 _ ( mod 7 ) 3 6 = 729 ≡ 1 _ ( mod 7 ) 3 7 = 2187 ≡ 3 _ ( mod 7 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}{\pmod {7}}\\3^{2}&=&9&\equiv &{\underline {2}}{\pmod {7}}\\3^{3}&=&27&\equiv &{\underline {6}}{\pmod {7}}\\3^{4}&=&81&\equiv &{\underline {4}}{\pmod {7}}\\3^{5}&=&243&\equiv &{\underline {5}}{\pmod {7}}\\3^{6}&=&729&\equiv &{\underline {1}}{\pmod {7}}\\3^{7}&=&2187&\equiv &{\underline {3}}{\pmod {7}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 7 {\displaystyle 7} immer einen Zykel der Länge 6 {\displaystyle 6} der Form ( 3 , 2 , 6 , 4 , 5 , 1 ) {\displaystyle (3,2,6,4,5,1)} .
Es ist also 3 n ≡ 6 ( mod 7 ) {\displaystyle 3^{n}\equiv 6{\pmod {7}}} genau dann, wenn n ≡ 3 ( mod 6 ) {\displaystyle n\equiv 3{\pmod {6}}} ist.
7 {\displaystyle 7} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 3 ( mod 6 ) {\displaystyle n\equiv 3{\pmod {6}}} ist.
Teil 3: Teilbarkeit durch 13:
Es ist 125050976086 = 9619305852 ⋅ 13 + 10 ≡ 10 ( mod 13 ) {\displaystyle 125050976086=9619305852\cdot 13+10\equiv 10{\pmod {13}}} . Somit gilt:
13 {\displaystyle 13} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 13 ( mod 13 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 13{\pmod {13}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 12 ( mod 13 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 12{\pmod {13}}} genau dann, wenn 10 ⋅ 3 n ≡ 12 ( mod 13 ) {\displaystyle 10\cdot 3^{n}\equiv 12{\pmod {13}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 10 {\displaystyle 10} modulo 13 {\displaystyle 13} , nämlich mit 4 {\displaystyle 4} (es ist 10 ⋅ 4 = 40 ≡ 1 ( mod 13 ) {\displaystyle 10\cdot 4=40\equiv 1{\pmod {13}}} ), so erhält man 40 ⋅ 3 n ≡ 48 ( mod 13 ) {\displaystyle 40\cdot 3^{n}\equiv 48{\pmod {13}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 9 ( mod 13 ) {\displaystyle 1\cdot 3^{n}\equiv 9{\pmod {13}}} .
Es ist also 13 {\displaystyle 13} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 9 ( mod 13 ) {\displaystyle 3^{n}\equiv 9{\pmod {13}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 13 ) 3 2 = 9 ≡ 9 _ ( mod 13 ) 3 3 = 27 ≡ 1 _ ( mod 13 ) 3 4 = 81 ≡ 3 _ ( mod 13 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {13}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {13}}\\3^{3}&=&27&\equiv &{\underline {1}}&{\pmod {13}}\\3^{4}&=&81&\equiv &{\underline {3}}&{\pmod {13}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 13 {\displaystyle 13} immer einen Zykel der Länge 3 {\displaystyle 3} der Form ( 3 , 9 , 1 ) {\displaystyle (3,9,1)} .
Es ist also 3 n ≡ 9 ( mod 13 ) {\displaystyle 3^{n}\equiv 9{\pmod {13}}} genau dann, wenn n ≡ 2 ( mod 3 ) {\displaystyle n\equiv 2{\pmod {3}}} ist.
13 {\displaystyle 13} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 2 ( mod 3 ) {\displaystyle n\equiv 2{\pmod {3}}} ist.
Teil 4: Teilbarkeit durch 17:
Es ist 125050976086 = 7355939769 ⋅ 17 + 13 ≡ 13 ( mod 17 ) {\displaystyle 125050976086=7355939769\cdot 17+13\equiv 13{\pmod {17}}} . Somit gilt:
17 {\displaystyle 17} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 17 ( mod 17 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 17{\pmod {17}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 16 ( mod 17 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 16{\pmod {17}}} genau dann, wenn 13 ⋅ 3 n ≡ 16 ( mod 17 ) {\displaystyle 13\cdot 3^{n}\equiv 16{\pmod {17}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 13 {\displaystyle 13} modulo 17 {\displaystyle 17} , nämlich mit 4 {\displaystyle 4} (es ist 13 ⋅ 4 = 52 ≡ 1 ( mod 17 ) {\displaystyle 13\cdot 4=52\equiv 1{\pmod {17}}} ), so erhält man 52 ⋅ 3 n ≡ 64 ( mod 17 ) {\displaystyle 52\cdot 3^{n}\equiv 64{\pmod {17}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 13 ( mod 17 ) {\displaystyle 1\cdot 3^{n}\equiv 13{\pmod {17}}} .
Es ist also 17 {\displaystyle 17} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 13 ( mod 17 ) {\displaystyle 3^{n}\equiv 13{\pmod {17}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 17 ) 3 2 = 9 ≡ 9 _ ( mod 17 ) 3 3 = 27 ≡ 10 _ ( mod 17 ) 3 4 = 81 ≡ 13 _ ( mod 17 ) 3 5 = 243 ≡ 5 _ ( mod 17 ) 3 6 = 729 ≡ 15 _ ( mod 17 ) 3 7 = 2187 ≡ 11 _ ( mod 17 ) 3 8 = 6561 ≡ 16 _ ( mod 17 ) 3 9 = 19683 ≡ 14 _ ( mod 17 ) 3 10 = 59049 ≡ 8 _ ( mod 17 ) 3 11 = 177147 ≡ 7 _ ( mod 17 ) 3 12 = 531441 ≡ 4 _ ( mod 17 ) 3 13 = 1594323 ≡ 12 _ ( mod 17 ) 3 14 = 4782969 ≡ 2 _ ( mod 17 ) 3 15 = 14348907 ≡ 6 _ ( mod 17 ) 3 16 = 43046721 ≡ 1 _ ( mod 17 ) 3 17 = 129140163 ≡ 3 _ ( mod 17 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {17}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {17}}\\3^{3}&=&27&\equiv &{\underline {10}}&{\pmod {17}}\\3^{4}&=&81&\equiv &{\underline {13}}&{\pmod {17}}\\3^{5}&=&243&\equiv &{\underline {5}}&{\pmod {17}}\\3^{6}&=&729&\equiv &{\underline {15}}&{\pmod {17}}\\3^{7}&=&2187&\equiv &{\underline {11}}&{\pmod {17}}\\3^{8}&=&6561&\equiv &{\underline {16}}&{\pmod {17}}\\3^{9}&=&19683&\equiv &{\underline {14}}&{\pmod {17}}\\3^{10}&=&59049&\equiv &{\underline {8}}&{\pmod {17}}\\3^{11}&=&177147&\equiv &{\underline {7}}&{\pmod {17}}\\3^{12}&=&531441&\equiv &{\underline {4}}&{\pmod {17}}\\3^{13}&=&1594323&\equiv &{\underline {12}}&{\pmod {17}}\\3^{14}&=&4782969&\equiv &{\underline {2}}&{\pmod {17}}\\3^{15}&=&14348907&\equiv &{\underline {6}}&{\pmod {17}}\\3^{16}&=&43046721&\equiv &{\underline {1}}&{\pmod {17}}\\3^{17}&=&129140163&\equiv &{\underline {3}}&{\pmod {17}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 17 {\displaystyle 17} immer einen Zykel der Länge 16 {\displaystyle 16} der Form ( 3 , 9 , 10 , 13 , 5 , 15 , 11 , 16 , 14 , 8 , 7 , 4 , 12 , 2 , 6 , 1 ) {\displaystyle (3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1)} .
Es ist also 3 n ≡ 13 ( mod 17 ) {\displaystyle 3^{n}\equiv 13{\pmod {17}}} genau dann, wenn n ≡ 4 ( mod 16 ) {\displaystyle n\equiv 4{\pmod {16}}} ist.
17 {\displaystyle 17} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 4 ( mod 16 ) {\displaystyle n\equiv 4{\pmod {16}}} ist.
Teil 5: Teilbarkeit durch 19:
Es ist 125050976086 = 6581630320 ⋅ 19 + 6 ≡ 6 ( mod 19 ) {\displaystyle 125050976086=6581630320\cdot 19+6\equiv 6{\pmod {19}}} . Somit gilt:
19 {\displaystyle 19} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 19 ( mod 19 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 19{\pmod {19}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 18 ( mod 19 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 18{\pmod {19}}} genau dann, wenn 6 ⋅ 3 n ≡ 18 ( mod 19 ) {\displaystyle 6\cdot 3^{n}\equiv 18{\pmod {19}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 6 {\displaystyle 6} modulo 19 {\displaystyle 19} , nämlich mit 16 {\displaystyle 16} (es ist 6 ⋅ 16 = 96 ≡ 1 ( mod 19 ) {\displaystyle 6\cdot 16=96\equiv 1{\pmod {19}}} ), so erhält man 96 ⋅ 3 n ≡ 288 ( mod 19 ) {\displaystyle 96\cdot 3^{n}\equiv 288{\pmod {19}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 3 ( mod 19 ) {\displaystyle 1\cdot 3^{n}\equiv 3{\pmod {19}}} .
Es ist also 19 {\displaystyle 19} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 3 ( mod 19 ) {\displaystyle 3^{n}\equiv 3{\pmod {19}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 19 ) 3 2 = 9 ≡ 9 _ ( mod 19 ) 3 3 = 27 ≡ 8 _ ( mod 19 ) 3 4 = 81 ≡ 5 _ ( mod 19 ) 3 5 = 243 ≡ 15 _ ( mod 19 ) 3 6 = 729 ≡ 7 _ ( mod 19 ) 3 7 = 2187 ≡ 2 _ ( mod 19 ) 3 8 = 6561 ≡ 6 _ ( mod 19 ) 3 9 = 19683 ≡ 18 _ ( mod 19 ) 3 10 = 59049 ≡ 16 _ ( mod 19 ) 3 11 = 177147 ≡ 10 _ ( mod 19 ) 3 12 = 531441 ≡ 11 _ ( mod 19 ) 3 13 = 1594323 ≡ 14 _ ( mod 19 ) 3 14 = 4782969 ≡ 4 _ ( mod 19 ) 3 15 = 14348907 ≡ 12 _ ( mod 19 ) 3 16 = 43046721 ≡ 17 _ ( mod 19 ) 3 17 = 129140163 ≡ 13 _ ( mod 19 ) 3 18 = 387420489 ≡ 1 _ ( mod 19 ) 3 19 = 1162261467 ≡ 3 _ ( mod 19 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {19}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {19}}\\3^{3}&=&27&\equiv &{\underline {8}}&{\pmod {19}}\\3^{4}&=&81&\equiv &{\underline {5}}&{\pmod {19}}\\3^{5}&=&243&\equiv &{\underline {15}}&{\pmod {19}}\\3^{6}&=&729&\equiv &{\underline {7}}&{\pmod {19}}\\3^{7}&=&2187&\equiv &{\underline {2}}&{\pmod {19}}\\3^{8}&=&6561&\equiv &{\underline {6}}&{\pmod {19}}\\3^{9}&=&19683&\equiv &{\underline {18}}&{\pmod {19}}\\3^{10}&=&59049&\equiv &{\underline {16}}&{\pmod {19}}\\3^{11}&=&177147&\equiv &{\underline {10}}&{\pmod {19}}\\3^{12}&=&531441&\equiv &{\underline {11}}&{\pmod {19}}\\3^{13}&=&1594323&\equiv &{\underline {14}}&{\pmod {19}}\\3^{14}&=&4782969&\equiv &{\underline {4}}&{\pmod {19}}\\3^{15}&=&14348907&\equiv &{\underline {12}}&{\pmod {19}}\\3^{16}&=&43046721&\equiv &{\underline {17}}&{\pmod {19}}\\3^{17}&=&129140163&\equiv &{\underline {13}}&{\pmod {19}}\\3^{18}&=&387420489&\equiv &{\underline {1}}&{\pmod {19}}\\3^{19}&=&1162261467&\equiv &{\underline {3}}&{\pmod {19}}\\\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 19 {\displaystyle 19} immer einen Zykel der Länge 18 {\displaystyle 18} der Form ( 3 , 9 , 8 , 5 , 15 , 7 , 2 , 6 , 18 , 16 , 10 , 11 , 14 , 4 , 12 , 17 , 13 , 1 ) {\displaystyle (3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,1)} .
Es ist also 3 n ≡ 3 ( mod 19 ) {\displaystyle 3^{n}\equiv 3{\pmod {19}}} genau dann, wenn n ≡ 1 ( mod 18 ) {\displaystyle n\equiv 1{\pmod {18}}} ist.
19 {\displaystyle 19} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 1 ( mod 18 ) {\displaystyle n\equiv 1{\pmod {18}}} ist.
Teil 6: Teilbarkeit durch 37:
Es ist 125050976086 = 3379756110 ⋅ 37 + 16 ≡ 16 ( mod 37 ) {\displaystyle 125050976086=3379756110\cdot 37+16\equiv 16{\pmod {37}}} . Somit gilt:
37 {\displaystyle 37} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 37 ( mod 37 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 37{\pmod {37}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 36 ( mod 37 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 36{\pmod {37}}} genau dann, wenn 16 ⋅ 3 n ≡ 36 ( mod 37 ) {\displaystyle 16\cdot 3^{n}\equiv 36{\pmod {37}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 16 {\displaystyle 16} modulo 37 {\displaystyle 37} , nämlich mit 7 {\displaystyle 7} (es ist 16 ⋅ 7 = 112 ≡ 1 ( mod 37 ) {\displaystyle 16\cdot 7=112\equiv 1{\pmod {37}}} ), so erhält man 112 ⋅ 3 n ≡ 252 ( mod 37 ) {\displaystyle 112\cdot 3^{n}\equiv 252{\pmod {37}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 30 ( mod 37 ) {\displaystyle 1\cdot 3^{n}\equiv 30{\pmod {37}}} .
Es ist also 37 {\displaystyle 37} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 30 ( mod 37 ) {\displaystyle 3^{n}\equiv 30{\pmod {37}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 37 ) 3 2 = 9 ≡ 9 _ ( mod 37 ) 3 3 = 27 ≡ 27 _ ( mod 37 ) 3 4 = 81 ≡ 7 _ ( mod 37 ) 3 5 = 243 ≡ 21 _ ( mod 37 ) 3 6 = 729 ≡ 26 _ ( mod 37 ) 3 7 = 2187 ≡ 4 _ ( mod 37 ) 3 8 = 6561 ≡ 12 _ ( mod 37 ) 3 9 = 19683 ≡ 36 _ ( mod 37 ) 3 10 = 59049 ≡ 34 _ ( mod 37 ) 3 11 = 177147 ≡ 28 _ ( mod 37 ) 3 12 = 531441 ≡ 10 _ ( mod 37 ) 3 13 = 1594323 ≡ 30 _ ( mod 37 ) 3 14 = 4782969 ≡ 16 _ ( mod 37 ) 3 15 = 14348907 ≡ 11 _ ( mod 37 ) 3 16 = 43046721 ≡ 33 _ ( mod 37 ) 3 17 = 129140163 ≡ 25 _ ( mod 37 ) 3 18 = 387420489 ≡ 1 _ ( mod 37 ) 3 19 = 1162261467 ≡ 3 _ ( mod 37 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {37}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {37}}\\3^{3}&=&27&\equiv &{\underline {27}}&{\pmod {37}}\\3^{4}&=&81&\equiv &{\underline {7}}&{\pmod {37}}\\3^{5}&=&243&\equiv &{\underline {21}}&{\pmod {37}}\\3^{6}&=&729&\equiv &{\underline {26}}&{\pmod {37}}\\3^{7}&=&2187&\equiv &{\underline {4}}&{\pmod {37}}\\3^{8}&=&6561&\equiv &{\underline {12}}&{\pmod {37}}\\3^{9}&=&19683&\equiv &{\underline {36}}&{\pmod {37}}\\3^{10}&=&59049&\equiv &{\underline {34}}&{\pmod {37}}\\3^{11}&=&177147&\equiv &{\underline {28}}&{\pmod {37}}\\3^{12}&=&531441&\equiv &{\underline {10}}&{\pmod {37}}\\3^{13}&=&1594323&\equiv &{\underline {30}}&{\pmod {37}}\\3^{14}&=&4782969&\equiv &{\underline {16}}&{\pmod {37}}\\3^{15}&=&14348907&\equiv &{\underline {11}}&{\pmod {37}}\\3^{16}&=&43046721&\equiv &{\underline {33}}&{\pmod {37}}\\3^{17}&=&129140163&\equiv &{\underline {25}}&{\pmod {37}}\\3^{18}&=&387420489&\equiv &{\underline {1}}&{\pmod {37}}\\3^{19}&=&1162261467&\equiv &{\underline {3}}&{\pmod {37}}\\\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 37 {\displaystyle 37} immer einen Zykel der Länge 18 {\displaystyle 18} der Form ( 3 , 9 , 27 , 7 , 21 , 26 , 4 , 12 , 36 , 34 , 28 , 10 , 30 , 16 , 11 , 33 , 25 , 1 ) {\displaystyle (3,9,27,7,21,26,4,12,36,34,28,10,30,16,11,33,25,1)} .
Es ist also 3 n ≡ 30 ( mod 37 ) {\displaystyle 3^{n}\equiv 30{\pmod {37}}} genau dann, wenn n ≡ 13 ( mod 18 ) {\displaystyle n\equiv 13{\pmod {18}}} ist.
37 {\displaystyle 37} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 13 ( mod 18 ) {\displaystyle n\equiv 13{\pmod {18}}} ist.
Teil 7: Teilbarkeit durch 41:
Es ist 125050976086 = 3050023806 ⋅ 41 + 40 ≡ 40 ( mod 41 ) {\displaystyle 125050976086=3050023806\cdot 41+40\equiv 40{\pmod {41}}} . Somit gilt:
41 {\displaystyle 41} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 41 ( mod 41 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 41{\pmod {41}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 40 ( mod 41 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 40{\pmod {41}}} genau dann, wenn 40 ⋅ 3 n ≡ 40 ( mod 41 ) {\displaystyle 40\cdot 3^{n}\equiv 40{\pmod {41}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 40 {\displaystyle 40} modulo 41 {\displaystyle 41} , nämlich mit 40 {\displaystyle 40} (es ist 40 ⋅ 40 = 1600 ≡ 1 ( mod 41 ) {\displaystyle 40\cdot 40=1600\equiv 1{\pmod {41}}} ), so erhält man 1600 ⋅ 3 n ≡ 1600 ( mod 41 ) {\displaystyle 1600\cdot 3^{n}\equiv 1600{\pmod {41}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 1 ( mod 41 ) {\displaystyle 1\cdot 3^{n}\equiv 1{\pmod {41}}} .
Es ist also 41 {\displaystyle 41} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 1 ( mod 41 ) {\displaystyle 3^{n}\equiv 1{\pmod {41}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 41 ) 3 2 = 9 ≡ 9 _ ( mod 41 ) 3 3 = 27 ≡ 27 _ ( mod 41 ) 3 4 = 81 ≡ 40 _ ( mod 41 ) 3 5 = 243 ≡ 38 _ ( mod 41 ) 3 6 = 729 ≡ 32 _ ( mod 41 ) 3 7 = 2187 ≡ 14 _ ( mod 41 ) 3 8 = 6561 ≡ 1 _ ( mod 41 ) 3 9 = 19683 ≡ 3 _ ( mod 41 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {41}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {41}}\\3^{3}&=&27&\equiv &{\underline {27}}&{\pmod {41}}\\3^{4}&=&81&\equiv &{\underline {40}}&{\pmod {41}}\\3^{5}&=&243&\equiv &{\underline {38}}&{\pmod {41}}\\3^{6}&=&729&\equiv &{\underline {32}}&{\pmod {41}}\\3^{7}&=&2187&\equiv &{\underline {14}}&{\pmod {41}}\\3^{8}&=&6561&\equiv &{\underline {1}}&{\pmod {41}}\\3^{9}&=&19683&\equiv &{\underline {3}}&{\pmod {41}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 41 {\displaystyle 41} immer einen Zykel der Länge 8 {\displaystyle 8} der Form ( 3 , 9 , 27 , 40 , 38 , 32 , 14 , 1 ) {\displaystyle (3,9,27,40,38,32,14,1)} .
Es ist also 3 n ≡ 1 ( mod 41 ) {\displaystyle 3^{n}\equiv 1{\pmod {41}}} genau dann, wenn n ≡ 8 ≡ 0 ( mod 8 ) {\displaystyle n\equiv 8\equiv 0{\pmod {8}}} ist.
41 {\displaystyle 41} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 0 ( mod 8 ) {\displaystyle n\equiv 0{\pmod {8}}} ist.
Teil 8: Teilbarkeit durch 193:
Es ist 125050976086 = 647932518 ⋅ 193 + 112 ≡ 112 ( mod 193 ) {\displaystyle 125050976086=647932518\cdot 193+112\equiv 112{\pmod {193}}} . Somit gilt:
193 {\displaystyle 193} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 193 ( mod 193 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 193{\pmod {193}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 192 ( mod 193 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 192{\pmod {193}}} genau dann, wenn 112 ⋅ 3 n ≡ 192 ( mod 193 ) {\displaystyle 112\cdot 3^{n}\equiv 192{\pmod {193}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 112 {\displaystyle 112} modulo 193 {\displaystyle 193} , nämlich mit 81 {\displaystyle 81} (es ist 112 ⋅ 81 = 9072 ≡ 1 ( mod 193 ) {\displaystyle 112\cdot 81=9072\equiv 1{\pmod {193}}} ), so erhält man 9072 ⋅ 3 n ≡ 192 ⋅ 81 = 15552 ≡ 112 ( mod 193 ) {\displaystyle 9072\cdot 3^{n}\equiv 192\cdot 81=15552\equiv 112{\pmod {193}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 112 ( mod 193 ) {\displaystyle 1\cdot 3^{n}\equiv 112{\pmod {193}}} .
Es ist also 193 {\displaystyle 193} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 112 ( mod 193 ) {\displaystyle 3^{n}\equiv 112{\pmod {193}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 193 ) 3 2 = 9 ≡ 9 _ ( mod 193 ) 3 3 = 27 ≡ 27 _ ( mod 193 ) 3 4 = 81 ≡ 81 _ ( mod 193 ) 3 5 = 243 ≡ 50 _ ( mod 193 ) 3 6 = 729 ≡ 150 _ ( mod 193 ) 3 7 = 2187 ≡ 64 _ ( mod 193 ) 3 8 = 6561 ≡ 192 _ ( mod 193 ) 3 9 = 19683 ≡ 190 _ ( mod 193 ) 3 10 = 59049 ≡ 184 _ ( mod 193 ) 3 11 = 177147 ≡ 166 _ ( mod 193 ) 3 12 = 531441 ≡ 112 _ ( mod 193 ) 3 13 = 1594323 ≡ 143 _ ( mod 193 ) 3 14 = 4782969 ≡ 43 _ ( mod 193 ) 3 15 = 14348907 ≡ 129 _ ( mod 193 ) 3 16 = 43046721 ≡ 1 _ ( mod 193 ) 3 17 = 129140163 ≡ 3 _ ( mod 193 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {193}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {193}}\\3^{3}&=&27&\equiv &{\underline {27}}&{\pmod {193}}\\3^{4}&=&81&\equiv &{\underline {81}}&{\pmod {193}}\\3^{5}&=&243&\equiv &{\underline {50}}&{\pmod {193}}\\3^{6}&=&729&\equiv &{\underline {150}}&{\pmod {193}}\\3^{7}&=&2187&\equiv &{\underline {64}}&{\pmod {193}}\\3^{8}&=&6561&\equiv &{\underline {192}}&{\pmod {193}}\\3^{9}&=&19683&\equiv &{\underline {190}}&{\pmod {193}}\\3^{10}&=&59049&\equiv &{\underline {184}}&{\pmod {193}}\\3^{11}&=&177147&\equiv &{\underline {166}}&{\pmod {193}}\\3^{12}&=&531441&\equiv &{\underline {112}}&{\pmod {193}}\\3^{13}&=&1594323&\equiv &{\underline {143}}&{\pmod {193}}\\3^{14}&=&4782969&\equiv &{\underline {43}}&{\pmod {193}}\\3^{15}&=&14348907&\equiv &{\underline {129}}&{\pmod {193}}\\3^{16}&=&43046721&\equiv &{\underline {1}}&{\pmod {193}}\\3^{17}&=&129140163&\equiv &{\underline {3}}&{\pmod {193}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 193 {\displaystyle 193} immer einen Zykel der Länge 16 {\displaystyle 16} der Form ( 3 , 9 , 27 , 81 , 50 , 150 , 64 , 192 , 190 , 184 , 166 , 112 , 143 , 43 , 129 , 1 ) {\displaystyle (3,9,27,81,50,150,64,192,190,184,166,112,143,43,129,1)} .
Es ist also 3 n ≡ 112 ( mod 193 ) {\displaystyle 3^{n}\equiv 112{\pmod {193}}} genau dann, wenn n ≡ 12 ( mod 16 ) {\displaystyle n\equiv 12{\pmod {16}}} ist.
193 {\displaystyle 193} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 12 ( mod 16 ) {\displaystyle n\equiv 12{\pmod {16}}} ist.
Teil 9: Teilbarkeit durch 757:
Es ist 125050976086 = 165192834 ⋅ 757 + 748 ≡ 748 ( mod 757 ) {\displaystyle 125050976086=165192834\cdot 757+748\equiv 748{\pmod {757}}} . Somit gilt:
757 {\displaystyle 757} teilt 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 125050976086 ⋅ 3 n + 1 ≡ 0 ≡ 757 ( mod 757 ) {\displaystyle 125050976086\cdot 3^{n}+1\equiv 0\equiv 757{\pmod {757}}} genau dann, wenn 125050976086 ⋅ 3 n ≡ 756 ( mod 757 ) {\displaystyle 125050976086\cdot 3^{n}\equiv 756{\pmod {757}}} genau dann, wenn 748 ⋅ 3 n ≡ 756 ( mod 757 ) {\displaystyle 748\cdot 3^{n}\equiv 756{\pmod {757}}} . Multipliziert man diese Modulo-Rechnung mit der Inversen von 748 {\displaystyle 748} modulo 757 {\displaystyle 757} , nämlich mit 84 {\displaystyle 84} (es ist 748 ⋅ 84 = 62832 ≡ 1 ( mod 757 ) {\displaystyle 748\cdot 84=62832\equiv 1{\pmod {757}}} ), so erhält man 62832 ⋅ 3 n ≡ 756 ⋅ 84 = 63504 ≡ 673 ( mod 757 ) {\displaystyle 62832\cdot 3^{n}\equiv 756\cdot 84=63504\equiv 673{\pmod {757}}} , was gleichwertig ist mit 1 ⋅ 3 n ≡ 673 ( mod 757 ) {\displaystyle 1\cdot 3^{n}\equiv 673{\pmod {757}}} .
Es ist also 757 {\displaystyle 757} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn 3 n ≡ 673 ( mod 757 ) {\displaystyle 3^{n}\equiv 673{\pmod {757}}} ist.
Es gilt:
3 1 = 3 ≡ 3 _ ( mod 757 ) 3 2 = 9 ≡ 9 _ ( mod 757 ) 3 3 = 27 ≡ 27 _ ( mod 757 ) 3 4 = 81 ≡ 81 _ ( mod 757 ) 3 5 = 243 ≡ 243 _ ( mod 757 ) 3 6 = 729 ≡ 729 _ ( mod 757 ) 3 7 = 2187 ≡ 673 _ ( mod 757 ) 3 8 = 6561 ≡ 505 _ ( mod 757 ) 3 9 = 19683 ≡ 1 _ ( mod 757 ) 3 10 = 59049 ≡ 3 _ ( mod 757 ) {\displaystyle {\begin{aligned}3^{1}&=&3&\equiv &{\underline {3}}&{\pmod {757}}\\3^{2}&=&9&\equiv &{\underline {9}}&{\pmod {757}}\\3^{3}&=&27&\equiv &{\underline {27}}&{\pmod {757}}\\3^{4}&=&81&\equiv &{\underline {81}}&{\pmod {757}}\\3^{5}&=&243&\equiv &{\underline {243}}&{\pmod {757}}\\3^{6}&=&729&\equiv &{\underline {729}}&{\pmod {757}}\\3^{7}&=&2187&\equiv &{\underline {673}}&{\pmod {757}}\\3^{8}&=&6561&\equiv &{\underline {505}}&{\pmod {757}}\\3^{9}&=&19683&\equiv &{\underline {1}}&{\pmod {757}}\\3^{10}&=&59049&\equiv &{\underline {3}}&{\pmod {757}}\end{aligned}}}
etc.
Somit durchlaufen die Dreierpotenzen modulo 757 {\displaystyle 757} immer einen Zykel der Länge 9 {\displaystyle 9} der Form ( 3 , 9 , 27 , 81 , 243 , 729 , 673 , 505 , 1 ) {\displaystyle (3,9,27,81,243,729,673,505,1)} .
Es ist also 3 n ≡ 673 ( mod 757 ) {\displaystyle 3^{n}\equiv 673{\pmod {757}}} genau dann, wenn n ≡ 7 ( mod 9 ) {\displaystyle n\equiv 7{\pmod {9}}} ist.
757 {\displaystyle 757} ist somit ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann, wenn n ≡ 7 ( mod 9 ) {\displaystyle n\equiv 7{\pmod {9}}} ist.
Teil 10: Zusammenfassung:
In den vergangenen neun Teilen dieses Beweises wurden alle möglichen Kongruenzen modulo kgV ⁡ ( 4 , 6 , 3 , 16 , 18 , 8 , 16 , 9 ) = 144 {\displaystyle \operatorname {kgV} (4,6,3,16,18,8,16,9)=144} abgedeckt. Es wurde zum Beispiel gezeigt, dass 5 {\displaystyle 5} ein Teiler von 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} genau dann ist, wenn n ≡ 2 ( mod 4 ) {\displaystyle n\equiv 2{\pmod {4}}} gilt, also wenn n ≡ k ( mod 144 ) {\displaystyle n\equiv k{\pmod {144}}} mit k ∈ { 2 , 6 , 10 , 14 , 18 , 22 , … , , 138 , 142 } {\displaystyle k\in \{2,6,10,14,18,22,\ldots ,,138,142\}} ist.
Zusammenfassend gilt also:
125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} ist, abhängig von n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} , unter anderem durch folgende Primzahlen teilbar:
n ≡ 0 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 1 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 2 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 3 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 4 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  teilbar n ≡ 5 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 6 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 7 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 8 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 9 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 10 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 11 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 12 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  teilbar n ≡ 13 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 14 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 15 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 16 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  und  757  teilbar n ≡ 17 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 18 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 19 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 20 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  17  teilbar n ≡ 21 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 22 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 23 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 24 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 25 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 26 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 27 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 28 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  teilbar n ≡ 29 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 30 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 31 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 32 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 33 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 0{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 1{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 2{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 3{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 4{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 5{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 6{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 7{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 8{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 9{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 10{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 11{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 12{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ teilbar}}\\n\equiv 13{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 14{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 15{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 16{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ und }}757{\text{ teilbar}}\\n\equiv 17{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 18{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 19{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 20{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}17{\text{ teilbar}}\\n\equiv 21{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 22{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 23{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 24{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 25{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 26{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 27{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 28{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ teilbar}}\\n\equiv 29{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 30{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 31{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 32{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 33{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\\end{array}}}
n ≡ 34 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  757  teilbar n ≡ 35 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 36 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  teilbar n ≡ 37 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 38 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 39 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 40 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 41 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 42 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 43 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 44 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  193  teilbar n ≡ 45 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 46 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 47 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 48 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 49 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 50 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 51 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 52 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  und  757  teilbar n ≡ 53 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 54 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 55 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 56 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 57 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 58 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 59 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 60 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  teilbar n ≡ 61 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 62 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 63 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 64 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 65 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 66 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 34{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}757{\text{ teilbar}}\\n\equiv 35{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 36{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 37{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 38{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 39{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 40{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 41{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 42{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 43{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 44{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}193{\text{ teilbar}}\\n\equiv 45{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 46{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 47{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 48{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 49{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 50{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 51{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 52{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ und }}757{\text{ teilbar}}\\n\equiv 53{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 54{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 55{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 56{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 57{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 58{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 59{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 60{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ teilbar}}\\n\equiv 61{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 62{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 63{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 64{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 65{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 66{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\\end{array}}}
n ≡ 67 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 68 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  17  teilbar n ≡ 69 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 70 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  757  teilbar n ≡ 71 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 72 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 73 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 74 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 75 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 76 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  teilbar n ≡ 77 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 78 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 79 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 80 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 81 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 82 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 83 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 84 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  teilbar n ≡ 85 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 86 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 87 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 88 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  und  757  teilbar n ≡ 89 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 90 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 91 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 92 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  193  teilbar n ≡ 93 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 94 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 95 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 96 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 97 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 98 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 99 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 67{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 68{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}17{\text{ teilbar}}\\n\equiv 69{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 70{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}757{\text{ teilbar}}\\n\equiv 71{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 72{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 73{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 74{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 75{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 76{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ teilbar}}\\n\equiv 77{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 78{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 79{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 80{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 81{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 82{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 83{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 84{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 85{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 86{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 87{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 88{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ und }}757{\text{ teilbar}}\\n\equiv 89{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 90{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 91{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 92{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}193{\text{ teilbar}}\\n\equiv 93{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 94{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 95{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 96{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 97{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 98{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 99{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\\end{array}}}
n ≡ 100 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  teilbar n ≡ 101 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 102 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 103 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 104 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 105 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 106 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  757  teilbar n ≡ 107 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 108 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  teilbar n ≡ 109 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 110 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 111 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 112 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 113 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 114 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 115 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 116 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  17  teilbar n ≡ 117 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 118 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 119 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 120 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 121 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 122 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 123 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 124 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  193  und  757  teilbar n ≡ 125 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 126 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 127 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  19  teilbar n ≡ 128 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  41  teilbar n ≡ 129 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 130 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 131 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 132 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  17  teilbar n ≡ 133 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  757  teilbar n ≡ 134 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  13  teilbar n ≡ 135 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 136 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  41  teilbar n ≡ 137 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar n ≡ 138 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  teilbar n ≡ 139 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  37  teilbar n ≡ 140 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  und  193  teilbar n ≡ 141 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  7  teilbar n ≡ 142 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  5  und  757  teilbar n ≡ 143 ( mod 144 ) ⟹ 125050976086 ⋅ 3 n + 1  ist durch  13  teilbar {\displaystyle {\begin{array}{rcl}n\equiv 100{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 101{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 102{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 103{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 104{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 105{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 106{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}757{\text{ teilbar}}\\n\equiv 107{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 108{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ teilbar}}\\n\equiv 109{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 110{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 111{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 112{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 113{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 114{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 115{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 116{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}17{\text{ teilbar}}\\n\equiv 117{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 118{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 119{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 120{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 121{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 122{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 123{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 124{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}193{\text{ und }}757{\text{ teilbar}}\\n\equiv 125{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 126{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 127{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}19{\text{ teilbar}}\\n\equiv 128{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}41{\text{ teilbar}}\\n\equiv 129{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 130{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 131{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 132{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}17{\text{ teilbar}}\\n\equiv 133{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}757{\text{ teilbar}}\\n\equiv 134{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}13{\text{ teilbar}}\\n\equiv 135{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 136{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}41{\text{ teilbar}}\\n\equiv 137{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\\n\equiv 138{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ teilbar}}\\n\equiv 139{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}37{\text{ teilbar}}\\n\equiv 140{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ und }}193{\text{ teilbar}}\\n\equiv 141{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}7{\text{ teilbar}}\\n\equiv 142{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}5{\text{ und }}757{\text{ teilbar}}\\n\equiv 143{\pmod {144}}&\Longrightarrow &125050976086\cdot 3^{n}+1{\text{ ist durch }}13{\text{ teilbar}}\end{array}}}
Damit werden alle möglichen n {\displaystyle n} abgedeckt. Somit ist 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} immer durch mindestens eine Primzahl teilbar, welche in der Menge { 5 , 7 , 13 , 17 , 19 , 37 , 41 , 193 , 757 } {\displaystyle \{5,7,13,17,19,37,41,193,757\}} liegt. Weil 125050976086 ⋅ 3 n + 1 > 757 {\displaystyle 125050976086\cdot 3^{n}+1>757} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} ist, ist 125050976086 ⋅ 3 n + 1 {\displaystyle 125050976086\cdot 3^{n}+1} für alle n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \backslash \{0\}} immer eine zusammengesetzte Zahl, was zu beweisen war. ◻ {\displaystyle \Box }

Es folgt noch eine Liste der vermuteten kleinsten Sierpiński-Zahlen zur Basis 2 ≤ b ≤ 50 {\displaystyle 2\leq b\leq 50} :

78557, 125050976086, 66741, 159986, 174308, 1112646039348, 1, 2344, 9175, 1490, 521, 132, 4, 91218919470156, 2500, 278, 398, 765174, 8, 1002, 6694, 182, 30651, 262638, 221, 8, 4554, 4, 867, 6360528, 1, 1854, 6, 214018, 1886, 2604, 14, 166134, 826477, 8, 13372, 2256, 4, 53474, 14992, 8, 1219, 2944, 16,… (Folge A123159 in OEIS)

Riesel-Zahlen zur Basis b

Eine Riesel-Zahl zur Basis b ist eine natürliche Zahl k {\displaystyle k} , sodass k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n > 0 {\displaystyle n>0} eine zusammengesetzte Zahl ergibt. Es darf also niemals eine Primzahl herauskommen.

Für b = 2 {\displaystyle b=2} erhält man die klassischen Riesel-Zahlen, die weiter oben vorgestellt wurden.

Wie schon bei den Sierpiński-Zahlen zur Basis b ist auch die Situation bei Riesel-Zahlen zur Basis b nicht mehr ganz so einfach wie bei den klassischen Riesel-Zahlen. Denn wenn man wie vorher zum Beispiel b = 3 {\displaystyle b=3} wählt, kann man erkennen, dass jedes ungerade k {\displaystyle k} eine Riesel-Zahl zur Basis 3 wäre, weil jede Zahl der Form k ⋅ 3 n − 1 {\displaystyle k\cdot 3^{n}-1} gerade und somit immer durch 2 teilbar ist und folglich niemals eine Primzahl ergibt (jede Potenz von 3 ist wieder ungerade, multipliziert mit einer ungeraden Zahl bleibt sie ungerade, und wegen −1 wird sie gerade). Um diese trivialen Fälle für potentiell interessantere Riesel-Zahlen zur Basis b auszuschließen, muss man somit wieder eine Vorkehrung treffen, damit nur wirklich interessante, nichttriviale k {\displaystyle k} als Riesel-Zahlen zur Basis b in Frage kommen.

Bedingung

Die zusätzliche Bedingung für nichttriviale Riesel-Zahlen k {\displaystyle k} zur Basis b, sodass nicht eine einzelne Primzahl p {\displaystyle p} alle Zahlen der Form k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} teilt, ist die folgende:

ggT ⁡ ( k − 1 , b − 1 ) = 1 {\displaystyle \operatorname {ggT} (k-1,b-1)=1}

Es muss also der größte gemeinsamer Teiler von k − 1 {\displaystyle k-1} und b − 1 {\displaystyle b-1} gleich 1 {\displaystyle 1} sein.

Beweis der folgenden Behauptung: p {\displaystyle \qquad p} teilt k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n ≥ 0 {\displaystyle n\geq 0} ⟺ p {\displaystyle \Longleftrightarrow p} ist ein Teiler von ggT ⁡ ( k − 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k-1,b-1)\not =1}

Der Beweis funktioniert analog zum Beweis der Bedingung für Sierpiński-Zahlen zur Basis b direkt.

⟹: {\displaystyle \Longrightarrow :}

Zuerst wird gezeigt, dass wenn eine Primzahl p ≠ 1 {\displaystyle p\not =1} jedes k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n ≥ 0 {\displaystyle n\geq 0} teilt, gelten muss:
p {\displaystyle p} teilt ggT ⁡ ( k − 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k-1,b-1)} und somit ist ggT ⁡ ( k − 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k-1,b-1)\not =1} .
Angenommen, eine Primzahl p ∈ P {\displaystyle p\in \mathbb {P} } teilt k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n ≥ 0 {\displaystyle n\geq 0} . Dann teilt p {\displaystyle p} auch k ⋅ b 0 − 1 = k ⋅ 1 − 1 = k − 1 {\displaystyle k\cdot b^{0}-1=k\cdot 1-1=k-1} und k ⋅ b 1 − 1 = k ⋅ b − 1 {\displaystyle k\cdot b^{1}-1=k\cdot b-1} . Wenn p {\displaystyle p} aber sowohl k − 1 {\displaystyle k-1} als auch k ⋅ b − 1 {\displaystyle k\cdot b-1} teilt, dann teilt p {\displaystyle p} auch die Differenz dieser beider Terme, nämlich ( k ⋅ b − 1 ) − ( k − 1 ) = k ⋅ b − 1 − k + 1 = k ⋅ b − k = k ⋅ ( b − 1 ) {\displaystyle (k\cdot b-1)-(k-1)=k\cdot b-1-k+1=k\cdot b-k=k\cdot (b-1)} . Somit muss p {\displaystyle p} auch k {\displaystyle k} oder b − 1 {\displaystyle b-1} teilen. Da p {\displaystyle p} schon k − 1 {\displaystyle k-1} teilt, kann p {\displaystyle p} nicht gleichzeitig k {\displaystyle k} teilen, also ist p {\displaystyle p} ein Teiler von b − 1 {\displaystyle b-1} . Weil somit also p {\displaystyle p} ein Teiler von k − 1 {\displaystyle k-1} und b − 1 {\displaystyle b-1} sein muss, teilt p {\displaystyle p} auch den ggT ⁡ ( k − 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k-1,b-1)} . Also ist ggT ⁡ ( k − 1 , b − 1 ) ≠ 1 {\displaystyle \operatorname {ggT} (k-1,b-1)\not =1} .

⟸: {\displaystyle \Longleftarrow :}

Umgekehrt wird nun gezeigt, dass wenn p {\displaystyle p} ein Teiler von ggT ⁡ ( k − 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k-1,b-1)} ist, daraus gefolgert werden kann, dass p {\displaystyle p} auch ein Teiler von k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n ≥ 0 {\displaystyle n\geq 0} sein muss.
Sei also p {\displaystyle p} ein Teiler von ggT ⁡ ( k − 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k-1,b-1)} . Dann kann man mit den Rechenregeln der Kongruenz zeigen, dass gilt: k ≡ 1 mod p {\displaystyle k\equiv 1\mod p} und b ≡ 1 mod p {\displaystyle b\equiv 1\mod p} und somit gilt:
k ⋅ b n − 1 ≡ 1 ⋅ 1 n − 1 ≡ 0 mod p {\displaystyle k\cdot b^{n}-1\equiv 1\cdot 1^{n}-1\equiv 0\mod p}
Somit ist p {\displaystyle p} ein Teiler von k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} .

Insgesamt wurde also gezeigt, dass p {\displaystyle p} die Zahlen k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n ≥ 0 {\displaystyle n\geq 0} genau dann teilt, wenn p {\displaystyle p} ein Teiler von ggT ⁡ ( k − 1 , b − 1 ) {\displaystyle \operatorname {ggT} (k-1,b-1)} ist. Der Beweis ist vollendet. ◻ {\displaystyle \Box }

Tabelle der Riesel-Zahlen zur Basis b

Um den trivialen Fall auszuschließen, bei dem lediglich eine einzige (Prim-)Zahl p {\displaystyle p} alle Zahlen der Form k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} mit n > 0 {\displaystyle n>0} teilt und somit k {\displaystyle k} schon eine gesuchte Riesel-Zahl zur Basis b ist, muss zusätzlich die Bedingung ggT ⁡ ( k − 1 , b − 1 ) = 1 {\displaystyle \operatorname {ggT} (k-1,b-1)=1} gefordert werden.

Nun kann man wieder die Basis b {\displaystyle b} beliebig hoch werden lassen. Untersucht werden momentan aber wie schon bei Sierpiński-Zahlen „nur“ Basen bis b ≤ 1030 {\displaystyle b\leq 1030} . Es folgt eine Tabelle mit dem momentanen Wissensstand (Stand: 22. April 2024) für Basen bis b = 30 {\displaystyle b=30} :[19][20]

b vermutete kleinste
Riesel-Zahl k 		Problemfälle k, für die man noch keine Primzahlen kennt,
die kleiner als die vermutete kleinste Riesel-Zahl k
und keine Vielfachen von ebenfalls unbekannten Problemfällen sind 		größte so gefundene Primzahl
2 509203 23669, 31859, 38473, 46663, 67117, 74699, 81041, 107347, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 351134, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 478214, 485557, 494743
(insgesamt 44 Problemfälle) 		97139·218397548−1
3 63.064.644.938 3677878, 6878756, 10789522, 16874152, 18137648, 21368582, 29140796, 31064666, 38394682, 40175404, 40396658, 51672206, 52072432, 56244334, 59254534, 62126002, 62402206, 65337866, 71248336, 94210372,…
(diese 20 und noch 98835 weitere, also insgesamt 98855 Problemfälle) 		690544546·31147906−1
4 9 keine Problemfälle mehr 8·41−1
5 346802 4906, 23906, 26222, 35248, 68132, 71146, 76354, 81134, 92936, 102952, 109238, 109862, 127174, 131848, 134266, 143632, 145462, 145484, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 231674, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 285598, 285728, 298442, 304004, 313126, 318278, 325922, 335414, 338866
(insgesamt 53 Problemfälle) 		3622·57558139−1
6 84687 1597 36772·61723287−1
7 408.034.255.082 315768, 1356018, 2494112, 2631672, 3423408, 4322834, 4326672, 4363418, 4382984, 4870566, 4990788, 5529368, 6279074, 6463028, 6544614, 7446728, 7553594, 8057622, 8640204, 8733908,…
(diese 20 und noch 37748 weitere bis k ≤ 2.000.000.000, also bis dahin insgesamt 37768 Problemfälle) 		1620198·7684923−1
8 14 keine Problemfälle mehr 11·818−1
9 4 keine Problemfälle mehr 2·91−1
10 10176 4421 7019·10881309−1
11 862 keine Problemfälle mehr 62·1126202−1
12 25 keine Problemfälle mehr 24·124−1
13 302 keine Problemfälle mehr 288·13109217−1
14 4 keine Problemfälle mehr 2·144−1
15 36.370.321.851.498 381714, 4502952, 5237186, 7256276, 8524154, 11118550, 11176190, 12232180, 15691976, 16338798, 16695396, 18267324, 18709072, 19615792,…
(diese 14 und noch viele weitere ab k > 20.000.000) 		4242104·15728840−1
16 9 keine Problemfälle mehr 8·161−1
17 86 keine Problemfälle mehr 44·176488−1
18 246 keine Problemfälle mehr 151·18418−1
19 144 keine Problemfälle mehr 134·19202−1
20 8 keine Problemfälle mehr 2·2010−1
21 560 keine Problemfälle mehr 64·212867−1
22 4461 3656 3104·22161188−1
23 476 404 194·23211140−1
24 4 keine Problemfälle mehr 3·241−1
25 36 keine Problemfälle mehr 32·254−1
26 149 keine Problemfälle mehr 115·26520277−1
27 8 keine Problemfälle mehr 6·272−1
28 144 keine Problemfälle mehr 107·2874−1
29 4 keine Problemfälle mehr 2·29136−1
30 1369 659, 1024 239·30337990−1

Auch in dieser Tabelle kann man erkennen, dass für gewisse Basen b {\displaystyle b} alle Problemfälle gelöst sind. Das bedeutet, dass die oben genannte Riesel-Zahl k {\displaystyle k} tatsächlich die kleinste Riesel-Zahl zu dieser Basis b ist und dass folglich alle Zahlen der Form k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1} für alle n > 0 {\displaystyle n>0} zusammengesetzte Zahlen sind. Im Folgenden werden die kleinsten Teiler für die schon bewiesenen und die noch vermuteten kleinsten Riesel-Zahlen angegeben:[19][20]

b bewiesene kleinste
Riesel-Zahl k 		vermutete kleinste
Riesel-Zahl k 		(kleinste) Teiler von k ⋅ b n − 1 {\displaystyle k\cdot b^{n}-1}
2 509203 509203 ⋅ 2 n − 1 {\displaystyle 509203\cdot 2^{n}-1} hat immer mindestens einen der Teiler 3, 5, 7, 13, 17 oder 241
3 63.064.644.938 63064644938 ⋅ 3 n − 1 {\displaystyle 63064644938\cdot 3^{n}-1} hat immer mindestens einen der Teiler 5, 7, 13, 17, 19, 37, 41, 193 oder 757
4 9 9 ⋅ 4 n − 1 = ( 3 ⋅ 2 n − 1 ) ⋅ ( 3 ⋅ 2 n + 1 ) {\displaystyle 9\cdot 4^{n}-1=(3\cdot 2^{n}-1)\cdot (3\cdot 2^{n}+1)}
5 346802 346802 ⋅ 5 n − 1 {\displaystyle 346802\cdot 5^{n}-1} hat immer mindestens einen der Teiler 3, 7, 13, 31 oder 601
6 84687 84687 ⋅ 6 n − 1 {\displaystyle 84687\cdot 6^{n}-1} hat immer mindestens einen der Teiler 7, 13, 31, 37 oder 97
7 408.034.255.082 408034255082 ⋅ 7 n − 1 {\displaystyle 408034255082\cdot 7^{n}-1} hat immer mindestens einen der Teiler 5, 13, 19, 43, 73, 181, 193 oder 1201
8 14 14 ⋅ 8 n − 1 {\displaystyle 14\cdot 8^{n}-1} hat immer mindestens einen der Teiler 3, 5 oder 13
9 4 4 ⋅ 9 n − 1 = ( 2 ⋅ 3 n − 1 ) ⋅ ( 2 ⋅ 3 n + 1 ) {\displaystyle 4\cdot 9^{n}-1=(2\cdot 3^{n}-1)\cdot (2\cdot 3^{n}+1)}
10 10176 10176 ⋅ 10 n − 1 {\displaystyle 10176\cdot 10^{n}-1} hat immer mindestens einen der Teiler 7, 11, 13 oder 37
11 862 862 ⋅ 11 n − 1 {\displaystyle 862\cdot 11^{n}-1} hat immer mindestens einen der Teiler 3, 7, 19 oder 37
12 25 25 ⋅ 12 n − 1 {\displaystyle 25\cdot 12^{n}-1} hat für ungerade n immer den Teiler 13
25 ⋅ 12 n − 1 = ( 5 ⋅ 12 n 2 − 1 ) ⋅ ( 5 ⋅ 12 n 2 + 1 ) {\displaystyle 25\cdot 12^{n}-1=(5\cdot 12^{\frac {n}{2}}-1)\cdot (5\cdot 12^{\frac {n}{2}}+1)} für gerade n
13 302 302 ⋅ 13 n − 1 {\displaystyle 302\cdot 13^{n}-1} hat immer mindestens einen der Teiler 5, 7 oder 17
14 4 4 ⋅ 14 n − 1 {\displaystyle 4\cdot 14^{n}-1} hat immer mindestens einen der Teiler 3 oder 5
15 36.370.321.851.498 36370321851498 ⋅ 15 n − 1 {\displaystyle 36370321851498\cdot 15^{n}-1} hat immer mindestens einen der Teiler 13, 17, 113, 211, 241, 1489 oder 3877
16 9 9 ⋅ 16 n − 1 = ( 3 ⋅ 4 n − 1 ) ⋅ ( 3 ⋅ 4 n + 1 ) {\displaystyle 9\cdot 16^{n}-1=(3\cdot 4^{n}-1)\cdot (3\cdot 4^{n}+1)}
17 86 86 ⋅ 17 n − 1 {\displaystyle 86\cdot 17^{n}-1} hat immer mindestens einen der Teiler 3, 5 oder 29
18 246 246 ⋅ 18 n − 1 {\displaystyle 246\cdot 18^{n}-1} hat immer mindestens einen der Teiler 5, 13 oder 19
19 144 144 ⋅ 19 n − 1 {\displaystyle 144\cdot 19^{n}-1} hat für ungerade n immer den Teiler 5
144 ⋅ 19 n − 1 = ( 12 ⋅ 19 n 2 − 1 ) ⋅ ( 12 ⋅ 19 n 2 + 1 ) {\displaystyle 144\cdot 19^{n}-1=(12\cdot 19^{\frac {n}{2}}-1)\cdot (12\cdot 19^{\frac {n}{2}}+1)} für gerade n
20 8 8 ⋅ 20 n − 1 {\displaystyle 8\cdot 20^{n}-1} hat immer mindestens einen der Teiler 3 oder 7
21 560 560 ⋅ 21 n − 1 {\displaystyle 560\cdot 21^{n}-1} hat immer mindestens einen der Teiler 11, 13 oder 17
22 4461 4461 ⋅ 22 n − 1 {\displaystyle 4461\cdot 22^{n}-1} hat immer mindestens einen der Teiler 5, 23 oder 97
23 476 476 ⋅ 23 n − 1 {\displaystyle 476\cdot 23^{n}-1} hat immer mindestens einen der Teiler 3, 5 oder 53
24 4 4 ⋅ 24 n − 1 {\displaystyle 4\cdot 24^{n}-1} hat für ungerade n immer den Teiler 5
4 ⋅ 24 n − 1 = ( 2 ⋅ 24 n 2 − 1 ) ⋅ ( 2 ⋅ 24 n 2 + 1 ) {\displaystyle 4\cdot 24^{n}-1=(2\cdot 24^{\frac {n}{2}}-1)\cdot (2\cdot 24^{\frac {n}{2}}+1)} für gerade n
25 36 36 ⋅ 25 n − 1 = ( 6 ⋅ 5 n − 1 ) ⋅ ( 6 ⋅ 5 n + 1 ) {\displaystyle 36\cdot 25^{n}-1=(6\cdot 5^{n}-1)\cdot (6\cdot 5^{n}+1)}
26 149 149 ⋅ 26 n − 1 {\displaystyle 149\cdot 26^{n}-1} hat immer mindestens einen der Teiler 3, 7, 31 oder 37
27 8 8 ⋅ 27 n − 1 = ( 2 ⋅ 3 n − 1 ) ⋅ ( 4 ⋅ 9 n + 2 ⋅ 3 n + 1 ) {\displaystyle 8\cdot 27^{n}-1=(2\cdot 3^{n}-1)\cdot (4\cdot 9^{n}+2\cdot 3^{n}+1)}
28 144 144 ⋅ 28 n − 1 {\displaystyle 144\cdot 28^{n}-1} hat für ungerade n immer den Teiler 29
144 ⋅ 28 n − 1 = ( 12 ⋅ 28 n 2 − 1 ) ⋅ ( 12 ⋅ 28 n 2 + 1 ) {\displaystyle 144\cdot 28^{n}-1=(12\cdot 28^{\frac {n}{2}}-1)\cdot (12\cdot 28^{\frac {n}{2}}+1)} für gerade n
29 4 4 ⋅ 29 n − 1 {\displaystyle 4\cdot 29^{n}-1} hat immer mindestens einen der Teiler 3 oder 5
30 1369 1369 ⋅ 30 n − 1 {\displaystyle 1369\cdot 30^{n}-1} hat für ungerade n immer mindestens einen der Teiler 7, 13 oder 19
1369 ⋅ 30 n − 1 = ( 37 ⋅ 30 n 2 − 1 ) ⋅ ( 37 ⋅ 30 n 2 + 1 ) {\displaystyle 1369\cdot 30^{n}-1=(37\cdot 30^{\frac {n}{2}}-1)\cdot (37\cdot 30^{\frac {n}{2}}+1)} für gerade n

Es folgt noch eine Liste der vermuteten kleinsten Riesel-Zahlen zur Basis 2 ≤ b ≤ 50 {\displaystyle 2\leq b\leq 50} :

509203, 63064644938, 9, 346802, 84687, 408034255082, 14, 4, 10176, 862, 25, 302, 4, 36370321851498, 9, 86, 246, 144, 8, 560, 4461, 476, 4, 36, 149, 8, 144, 4, 1369, 134718, 10, 16, 6, 287860, 4, 7772, 13, 4, 81, 8, 15137, 672, 4, 22564, 8177, 14, 3226, 36, 16,… (Folge A273987 in OEIS)

Weblinks

  • Seventeen Or Bust (Distributed-Computing-Projekt, englisch)
  • PrimeGrid (Distributed Computing-Projekt, englisch)
  • The Prime Glossary
  • Wilfrid Keller: The Sierpiński Problem: Definition and Status.
  • Wilfrid Keller: The Riesel Problem: Definition and Status.
  • A search for some small Brier numbers. Yves Gallot, 2000
  • Joe McLean: Brier Numbers.
  • Michael Filaseta, Carrie Finch, Mark Kozek: On Powers Associated with Sierpiński Numbers, Riesel Numbers and Polignac’s Conjecture. (PDF; 255 kB)
  • Startseite des Internet-Projektes “Seventeen or Bust”
  • Tabelle aller Vermutungen bis zur Basis 1030

Einzelnachweise

  1. ↑ a b c Beweis, dass k=78557 eine Sierpiński-Zahl ist (englisch). Abgerufen am 14. Juli 2019. 
  2. ↑ Chris K. Caldwell: Sierpinski number. The Prime Glossary, abgerufen am 27. Dezember 2019 (englisch). 
  3. ↑ Rytis Slatkevičius: Seventeen or Bust. Prime Grid, abgerufen am 29. Dezember 2019 (englisch). 
  4. ↑ a b c d e Wilfrid Keller: The Sierpiński Problem: Definition and Status. Prothsearch, abgerufen am 31. Dezember 2019 (englisch, erweitertes Sierpiński-Problem). 
  5. ↑ Rytis Slatkevičius: Welcome to the Extended Sierpinski Problem. PrimeGrid, abgerufen am 31. Dezember 2019 (englisch, erweitertes Sierpiński-Problem). 
  6. ↑ Chris K. Caldwell: Riesel number. The Prime Glossary, abgerufen am 1. September 2016 (englisch). 
  7. ↑ a b Wilfrid Keller: The Riesel Problem: Definition and Status. Prothsearch, abgerufen am 26. April 2023 (englisch). 
  8. ↑ Five or Bust. rechenkraft.net, abgerufen am 2. Januar 2016. 
  9. ↑ a b Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, abgerufen am 6. Juni 2021. 
  10. ↑ Jean Pennè: Even k’s and the Sierpinski conjecture. Mersenneforum, abgerufen am 30. Januar 2016 (englisch). 
  11. ↑ Giovanni Resta: de Polignac numbers. Abgerufen am 31. Januar 2016. 
  12. ↑ Jason „jasong“ Goatcher: Even k’s and the Riesel conjecture. Mersenneforum, abgerufen am 17. Februar 2016 (englisch). 
  13. ↑ „kar_bon“: Even k’s and the Riesel conjecture. Mersenneforum, abgerufen am 1. April 2008 (englisch). 
  14. ↑ a b Gary Barnes: Riesel conjecture base 2 remain. Mersenneforum, abgerufen am 18. Dezember 2017 (englisch). 
  15. ↑ Jean Pennè: Index of Sierpeven. Abgerufen am 30. Januar 2016. 
  16. ↑ Amy Brunner, Chris K.Caldwell, Daniel Krywaruczenko, Chris Lownsdale: Generalized Sierpiński numbers base b. (PDF) University of Tennessee at Martin, S. 2, abgerufen am 25. März 2016. 
  17. ↑ a b Gary Barnes: Sierpinski conjectures and proofs. Abgerufen am 22. April 2024. 
  18. ↑ a b Gary Barnes: Sierpinski conjectures and proofs, Powers of 2. Abgerufen am 15. April 2024. 
  19. ↑ a b Gary Barnes: Riesel conjectures and proofs. Abgerufen am 22. April 2024. 
  20. ↑ a b Gary Barnes: Riesel conjectures and proofs, Powers of 2. Abgerufen am 31. März 2024.