Sierpiński-Zahl

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

Zu zeigen ist, dass ${\displaystyle 78557\cdot 2^{n}+1}$ für alle natürlichen Zahlen ${\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 ${\displaystyle \{3,5,7,13,19,37,73\}}$ gibt, welche ${\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 ${\displaystyle 78557=26185\cdot 3+2\equiv 2{\pmod {3}}}$. Somit gilt:

${\displaystyle 3}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 3{\pmod {3}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 2{\pmod {3}}}$ genau dann, wenn ${\displaystyle 2\cdot 2^{n}\equiv 2{\pmod {3}}}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 1{\pmod {3}}}$ ist.

Es ist also ${\displaystyle 3}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 1{\pmod {3}}}$ ist.

Es gilt:

${\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 ${\displaystyle 3}$ immer einen Zykel der Länge ${\displaystyle 2}$ der Form ${\displaystyle (2,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 1{\pmod {3}}}$ genau dann, wenn ${\displaystyle n}$ gerade ist, also wenn ${\displaystyle n\equiv 0{\pmod {2}}}$ ist.

${\displaystyle 3}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 0{\pmod {2}}}$ ist.

Teil 2: Teilbarkeit durch 5:

Es ist ${\displaystyle 78557=15711\cdot 5+2\equiv 2{\pmod {5}}}$. Somit gilt:

${\displaystyle 5}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 5{\pmod {5}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 4{\pmod {5}}}$ genau dann, wenn ${\displaystyle 2\cdot 2^{n}\equiv 4{\pmod {5}}}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 2{\pmod {5}}}$ ist.

Es ist also ${\displaystyle 5}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 2{\pmod {5}}}$ ist.

Es gilt:

${\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 ${\displaystyle 5}$ immer einen Zykel der Länge ${\displaystyle 4}$ der Form ${\displaystyle (2,4,3,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 2{\pmod {5}}}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {4}}}$ ist.

${\displaystyle 5}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {4}}}$ ist.

Teil 3: Teilbarkeit durch 7:

Es ist ${\displaystyle 78557=11222\cdot 7+3\equiv 3{\pmod {7}}}$. Somit gilt:

${\displaystyle 7}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 7{\pmod {7}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 6{\pmod {7}}}$ genau dann, wenn ${\displaystyle 3\cdot 2^{n}\equiv 6{\pmod {7}}}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 2{\pmod {7}}}$ ist.

Es ist also ${\displaystyle 7}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 2{\pmod {7}}}$ ist.

Es gilt:

${\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 ${\displaystyle 7}$ immer einen Zykel der Länge ${\displaystyle 3}$ der Form ${\displaystyle (2,4,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 2{\pmod {7}}}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {3}}}$ ist.

${\displaystyle 7}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {3}}}$ ist.

Teil 4: Teilbarkeit durch 13:

Es ist ${\displaystyle 78557=6042\cdot 13+11\equiv 11{\pmod {13}}}$. Somit gilt:

${\displaystyle 13}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 13{\pmod {13}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 12{\pmod {13}}}$ genau dann, wenn ${\displaystyle 11\cdot 2^{n}\equiv 12{\pmod {13}}}$. Multipliziert man diese Modulo-Rechnung mit der Inversen von ${\displaystyle 11}$ modulo ${\displaystyle 13}$, nämlich mit ${\displaystyle 6}$ (es ist ${\displaystyle 11\cdot 6=66\equiv 1{\pmod {13}}}$), so erhält man ${\displaystyle 66\cdot 2^{n}\equiv 72{\pmod {13}}}$, was gleichwertig ist mit ${\displaystyle 1\cdot 2^{n}\equiv 7{\pmod {13}}}$.

Es ist also ${\displaystyle 13}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 7{\pmod {13}}}$ ist.

Es gilt:

${\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 ${\displaystyle 13}$ immer einen Zykel der Länge ${\displaystyle 12}$ der Form ${\displaystyle (2,4,8,3,6,12,11,9,5,10,7,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 7{\pmod {13}}}$ genau dann, wenn ${\displaystyle n\equiv 11{\pmod {12}}}$ ist.

${\displaystyle 13}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 11{\pmod {12}}}$ ist.

Teil 5: Teilbarkeit durch 19:

Es ist ${\displaystyle 78557=4134\cdot 19+11\equiv 11{\pmod {19}}}$. Somit gilt:

${\displaystyle 19}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 19{\pmod {19}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 18{\pmod {19}}}$ genau dann, wenn ${\displaystyle 11\cdot 2^{n}\equiv 18{\pmod {19}}}$. Multipliziert man diese Modulo-Rechnung mit der Inversen von ${\displaystyle 11}$ modulo ${\displaystyle 19}$, nämlich mit ${\displaystyle 7}$ (es ist ${\displaystyle 11\cdot 7=77\equiv 1{\pmod {19}}}$), so erhält man ${\displaystyle 77\cdot 2^{n}\equiv 126{\pmod {19}}}$, was gleichwertig ist mit ${\displaystyle 1\cdot 2^{n}\equiv 12{\pmod {19}}}$.

Es ist also ${\displaystyle 19}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 12{\pmod {19}}}$ ist.

Es gilt:

${\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 ${\displaystyle 19}$ immer einen Zykel der Länge ${\displaystyle 18}$ der Form ${\displaystyle (2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 12{\pmod {19}}}$ genau dann, wenn ${\displaystyle n\equiv 15{\pmod {18}}}$ ist.

${\displaystyle 19}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 15{\pmod {18}}}$ ist.

Teil 6: Teilbarkeit durch 37:

Es ist ${\displaystyle 78557=2123\cdot 37+6\equiv 6{\pmod {37}}}$. Somit gilt:

${\displaystyle 37}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 37{\pmod {37}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 36{\pmod {37}}}$ genau dann, wenn ${\displaystyle 6\cdot 2^{n}\equiv 36{\pmod {37}}}$. Multipliziert man diese Modulo-Rechnung mit der Inversen von ${\displaystyle 6}$ modulo ${\displaystyle 37}$, nämlich mit ${\displaystyle 31}$ (es ist ${\displaystyle 6\cdot 31=186\equiv 1{\pmod {37}}}$), so erhält man ${\displaystyle 186\cdot 2^{n}\equiv 1116{\pmod {37}}}$, was gleichwertig ist mit ${\displaystyle 1\cdot 2^{n}\equiv 6{\pmod {37}}}$.

Es ist also ${\displaystyle 37}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 6{\pmod {37}}}$ ist.

Es gilt:

${\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 ${\displaystyle 37}$ immer einen Zykel der Länge ${\displaystyle 36}$ der Form ${\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 ${\displaystyle 2^{n}\equiv 6{\pmod {37}}}$ genau dann, wenn ${\displaystyle n\equiv 27{\pmod {36}}}$ ist.

${\displaystyle 37}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 27{\pmod {36}}}$ ist.

Teil 7: Teilbarkeit durch 73:

Es ist ${\displaystyle 78557=1076\cdot 73+9\equiv 9{\pmod {73}}}$. Somit gilt:

${\displaystyle 73}$ teilt ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}+1\equiv 0\equiv 73{\pmod {73}}}$ genau dann, wenn ${\displaystyle 78557\cdot 2^{n}\equiv 72{\pmod {73}}}$ genau dann, wenn ${\displaystyle 9\cdot 2^{n}\equiv 72{\pmod {73}}}$. Multipliziert man diese Modulo-Rechnung mit der Inversen von ${\displaystyle 9}$ modulo ${\displaystyle 73}$, nämlich mit ${\displaystyle 65}$ (es ist ${\displaystyle 9\cdot 65=585\equiv 1{\pmod {73}}}$), so erhält man ${\displaystyle 585\cdot 2^{n}\equiv 4680{\pmod {73}}}$, was gleichwertig ist mit ${\displaystyle 1\cdot 2^{n}\equiv 8{\pmod {73}}}$.

Es ist also ${\displaystyle 73}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 8{\pmod {73}}}$ ist.

Es gilt:

${\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 ${\displaystyle 73}$ immer einen Zykel der Länge ${\displaystyle 9}$ der Form ${\displaystyle (2,4,8,16,32,64,55,37,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 8{\pmod {73}}}$ genau dann, wenn ${\displaystyle n\equiv 3{\pmod {9}}}$ ist.

${\displaystyle 73}$ ist somit ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann, wenn ${\displaystyle n\equiv 3{\pmod {9}}}$ ist.

Teil 8: Zusammenfassung:

In den vergangenen sieben Teilen dieses Beweises wurden alle möglichen Kongruenzen modulo ${\displaystyle 36}$ abgedeckt. Es wurde zum Beispiel gezeigt, dass ${\displaystyle 3}$ ein Teiler von ${\displaystyle 78557\cdot 2^{n}+1}$ genau dann ist, wenn ${\displaystyle n\equiv 0{\pmod {2}}}$ gilt, also wenn ${\displaystyle n\equiv k{\pmod {36}}}$ mit ${\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:

${\displaystyle 78557\cdot 2^{n}+1}$ ist, abhängig von ${\displaystyle n\in \mathbb {N} \backslash \{0\}}$, unter anderem durch folgende Primzahlen 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 ${\displaystyle n}$ abgedeckt. Somit ist ${\displaystyle 78557\cdot 2^{n}+1}$ immer durch mindestens eine Primzahl teilbar, welche in der Menge ${\displaystyle \{3,5,7,13,19,37,73\}}$ liegt. Weil ${\displaystyle 78557\cdot 2^{n}+1>73}$ für alle ${\displaystyle n\in \mathbb {N} \backslash \{0\}}$ ist, ist ${\displaystyle 78557\cdot 2^{n}+1}$ für alle ${\displaystyle n\in \mathbb {N} \backslash \{0\}}$ immer eine zusammengesetzte Zahl, was zu beweisen war. ${\displaystyle \Box }$

Der Beweis funktioniert direkt mittels Modulo-Rechnung.

Zu zeigen ist, dass ${\displaystyle 509203\cdot 2^{n}-1}$ für alle natürlichen Zahlen ${\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 ${\displaystyle \{3,5,7,13,17,241\}}$ gibt, welche ${\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 ${\displaystyle 509203=169734\cdot 3+1\equiv 1{\pmod {3}}}$. Somit gilt:

${\displaystyle 3}$ teilt ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {3}}}$ genau dann, wenn ${\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {3}}}$ genau dann, wenn ${\displaystyle 1\cdot 2^{n}\equiv 1{\pmod {3}}}$ ist.

Es ist also ${\displaystyle 3}$ ein Teiler von ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 1{\pmod {3}}}$ ist.

Es gilt:

${\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 ${\displaystyle 3}$ immer einen Zykel der Länge ${\displaystyle 2}$ der Form ${\displaystyle (2,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 1{\pmod {3}}}$ genau dann, wenn ${\displaystyle n}$ gerade ist, also wenn ${\displaystyle n\equiv 0{\pmod {2}}}$ ist.

${\displaystyle 3}$ ist somit ein Teiler von ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle n\equiv 0{\pmod {2}}}$ ist.

Teil 2: Teilbarkeit durch 5:

Es ist ${\displaystyle 509203=101840\cdot 5+3\equiv 3{\pmod {5}}}$. Somit gilt:

${\displaystyle 5}$ teilt ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle 509203\cdot 2^{n}-1\equiv 0{\pmod {5}}}$ genau dann, wenn ${\displaystyle 509203\cdot 2^{n}\equiv 1{\pmod {5}}}$ genau dann, wenn ${\displaystyle 3\cdot 2^{n}\equiv 1{\pmod {5}}}$. Multipliziert man diese Modulo-Rechnung mit der Inversen von ${\displaystyle 3}$ modulo ${\displaystyle 5}$, nämlich mit ${\displaystyle 2}$ (es ist ${\displaystyle 3\cdot 2=6\equiv 1{\pmod {5}}}$), so erhält man ${\displaystyle 6\cdot 2^{n}\equiv 2{\pmod {5}}}$, was gleichwertig ist mit ${\displaystyle 1\cdot 2^{n}\equiv 2{\pmod {5}}}$.

Es ist also ${\displaystyle 5}$ ein Teiler von ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle 2^{n}\equiv 2{\pmod {5}}}$ ist.

Es gilt:

${\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 ${\displaystyle 5}$ immer einen Zykel der Länge ${\displaystyle 4}$ der Form ${\displaystyle (2,4,3,1)}$.

Es ist also ${\displaystyle 2^{n}\equiv 2{\pmod {5}}}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {4}}}$ ist.

${\displaystyle 5}$ ist somit ein Teiler von ${\displaystyle 509203\cdot 2^{n}-1}$ genau dann, wenn ${\displaystyle n\equiv 1{\pmod {4}}}$ ist.