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
, für die die unendliche Zahlenfolge
mit
keine Primzahlen enthält.
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
für alle natürlichen Zahlen
immer eine zusammengesetzte Zahl, also niemals eine Primzahl, ist.
Es wird gezeigt, dass es immer eine Zahl aus der Menge
gibt, welche
teilt (diese Menge nennt man im englischen covering set of 78557).
Beweis:
- Teil 1: Teilbarkeit durch 3:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
genau dann, wenn
ist. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84bb22548f35e9168140d99bd9be8644f8ca0fa3)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
gerade ist, also wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 2: Teilbarkeit durch 5:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
genau dann, wenn
ist. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbf64ce7891f599d50ad81261c8889451a24fd9b)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 3: Teilbarkeit durch 7:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
genau dann, wenn
ist. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d27850a8e6af45073ade3dfe45e273bcb049cf55)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 4: Teilbarkeit durch 13:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e31d865309b750850c75e0a5aa6a94ba166a564d)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 5: Teilbarkeit durch 19:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b351f7009dfcec31c84a16f691269c8c4e1378a)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 6: Teilbarkeit durch 37:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6da704028c679e27170936b6ceaded92d77ebca7)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 7: Teilbarkeit durch 73:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66baaf7d01acb0065d07794f435225e2cce70abb)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 8: Zusammenfassung:
- In den vergangenen sieben Teilen dieses Beweises wurden alle möglichen Kongruenzen modulo
abgedeckt. Es wurde zum Beispiel gezeigt, dass
ein Teiler von
genau dann ist, wenn
gilt, also wenn
mit
ist. - Zusammenfassend gilt also:
ist, abhängig von
, 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3db3ddc688a72a738db8504b67756f2d9ec43d60)
- Damit werden alle möglichen
abgedeckt. Somit ist
immer durch mindestens eine Primzahl teilbar, welche in der Menge
liegt. Weil
für alle
ist, ist
für alle
immer eine zusammengesetzte Zahl, was zu beweisen war. ![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
- Die folgenden Zahlen sind bekannte Sierpiński-Zahlen
:
- 78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … (Folge A076336 in OEIS)
- Ist
eine dieser Zahlen, so ist
für alle
zusammengesetzt. Man erhält niemals eine Primzahl.
Die Zahl
ist keine Sierpiński-Zahl, da in der Folge
wenigstens eine Primzahl auftritt: 39, 77, 153, 305, 609, 1217, 2433, … Das sechste Glied der Folge, 1217, ist eine Primzahl. Das genügt zum Nachweis, dass 19 keine Sierpiński-Zahl ist. Ob noch weitere Primzahlen in dieser Folge auftreten oder nicht (das zehnte Glied 19457 ist prim), ist unerheblich.
Primzahlen der Form
nennt man Prothsche Primzahl.
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
kleiner als 78557 eine Zahl
gefunden werden, so dass die resultierende Proth-Zahl
eine Primzahl ist. Dieser Beweis ist (Stand 8. Juli 2019) bereits für alle
bis auf 5 Ausnahmen erfolgt, diese sind (Primzahlen werden fett geschrieben):
- 21181, 22699, 24737, 55459 und 67607[1][2][3]
Die möglicherweise kleinste Sierpiński-Zahl
ist eine zusammengesetzte Zahl.
Das prime Sierpiński-Problem beschäftigt sich damit, ob
die kleinste prime Sierpiński-Zahl ist.[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:
,
und
) (Stand: 31. Dezember 2019):
- k = 22699, 67607, 79309, 79817, 152267, 156511, 222113, 225931, 237019
Das erweiterte Sierpiński-Problem beschäftigt sich damit, ob
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
Eine Riesel-Zahl (benannt nach dem schwedischen Mathematiker Hans Riesel) ist eine natürliche, ungerade Zahl
, für die die unendliche Zahlenfolge
mit
keine Primzahlen enthält.
ist eine Riesel-Zahl.
Beweis der Behauptung, dass 509203 eine Riesel-Zahl ist:
Der Beweis funktioniert direkt mittels Modulo-Rechnung.
Zu zeigen ist, dass
für alle natürlichen Zahlen
immer eine zusammengesetzte Zahl, also niemals eine Primzahl, ist.
Es wird gezeigt, dass es immer eine Zahl aus der Menge
gibt, welche
teilt (diese Menge nennt man im englischen covering set of 509203).
Beweis:
- Teil 1: Teilbarkeit durch 3:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
ist. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84bb22548f35e9168140d99bd9be8644f8ca0fa3)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
gerade ist, also wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 2: Teilbarkeit durch 5:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbf64ce7891f599d50ad81261c8889451a24fd9b)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 3: Teilbarkeit durch 7:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d27850a8e6af45073ade3dfe45e273bcb049cf55)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 4: Teilbarkeit durch 13:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e31d865309b750850c75e0a5aa6a94ba166a564d)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 5: Teilbarkeit durch 17:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
ein Teiler von
genau dann, wenn
ist. - Es gilt:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3383383c7e87b2c239f1f86d39aca5fce17f6d3)
- etc.
- Somit durchlaufen die Zweierpotenzen modulo
immer einen Zykel der Länge
der Form
. - Es ist also
genau dann, wenn
ist.
ist somit ein Teiler von
genau dann, wenn
ist.
- Teil 6: Teilbarkeit durch 241:
- Es ist
. Somit gilt:
teilt
genau dann, wenn
genau dann, wenn
genau dann, wenn
. Multipliziert man diese Modulo-Rechnung mit der Inversen von
modulo
, nämlich mit
(es ist
), so erhält man
, was gleichwertig ist mit
. - Es ist also
![]()