インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

78557:シェルピンスキー数

正の奇数kSierpinski数であるとは、k2^n+1が任意の自然数nに対して合成数になるときに言います。

78557は知られている最小のSierpinski数ですが、本当に最小であるかは未解決問題です。この記事ではSelfridgeの定理の証明を紹介します(未出版)。

定理 (Selfridge 1962) 78557はSierpinski数である。

証明は補題7個に分けて行います。計算技術の習得という観点でtsujimotter氏の記事
tsujimotter.hatenablog.com
を参照してください。s_n:=78557\cdot 2^n+1とおきます。

まずはnが偶数の場合:

補題1 n \equiv 0 \pmod{2}ならばs_n3で割り切れる。

証明. Fermatの小定理(FLT)より2^2 \equiv 1 \pmod{3}であり*178557 \equiv 2 \pmod{3}なので

\begin{equation}\begin{split}s_{2k} &= 78557\cdot 2^{2k}+1 \\ &\equiv 2\cdot 1+1 \\ &\equiv 0 \pmod{3}.\end{split}\end{equation}

Q.E.D.

奇数の場合はn\equiv 1 \pmod{4}n \equiv 3 \pmod{4}で分けます。

補題2 n \equiv 1 \pmod{4}ならばs_n5で割り切れる。

証明. FLTより2^{4} \equiv 1 \pmod{5}なので、

\begin{equation}\begin{split}s_{4k+1} &= 78557\cdot 2^{4k+1}+1 \\ &\equiv 78557\cdot 2 +1 \\ &= 157115 \\ &\equiv 0\pmod{5}.\end{split}\end{equation}

Q.E.D.

n \equiv 3 \pmod{4}の場合はn \equiv 3\pmod{12}, n \equiv 7 \pmod{12}, n \equiv 11 \pmod{12}で分けます。

補題3 n \equiv 7 \pmod{12}ならばs_n7で割り切れる。

証明. FLTより2^6 \equiv 1 \pmod{7}なので、

\begin{equation}\begin{split}s_{12k+7} &= 78557 \cdot 2^{12k+7} +1 \\ &\equiv 78557\cdot 2+1 \\ &= 157115 \\ &\equiv 0 \pmod{7}.\end{split}\end{equation}

Q.E.D.

補題4 n \equiv 11 \pmod{12}ならばs_n13で割り切れる。

証明. FLTより2^{12} \equiv 1 \pmod{13}であり78557 \equiv 11, 2^{11} \equiv 7なので*2

\begin{equation}\begin{split}s_{12k+11} &= 78557\cdot 2^{12k+11}+1 \\ &\equiv 78557\cdot 2^{11}+1 \\ &\equiv 11\cdot 7 + 1 \\ &\equiv 0 \pmod{13}. \end{split}\end{equation}

Q.E.D.

n\equiv 3 \pmod{12}の場合はn \equiv 3 \pmod{36}, n \equiv 15 \pmod{36}, n \equiv 27 \pmod{36}に分ける。

補題5 n \equiv 3 \pmod{36}ならばs_n73で割り切れる。

証明. FLTからは分からないが、直接計算によって2^9 \equiv 1 \pmod{73}が確かめられ、78557 \equiv 9 \pmod{73}なので

\begin{equation}\begin{split}s_{36k+3} &= 78557\cdot 2^{36k+3}+1 \\ &\equiv 78557\cdot 8+1 \\ &\equiv 9\cdot 8+1 \\ &\equiv 0 \pmod{73}. \end{split}\end{equation}

補題6 n \equiv 15 \pmod{36}ならばs_n19で割り切れる。

証明. FLTより2^{18} \equiv 1であり、78557 \equiv 11, 2^{15} \equiv 12 \pmod{19}なので*3

\begin{equation}\begin{split}s_{36k+15} &= 78557\cdot 2^{36k+15}+1\\ &\equiv 78557\cdot 2^{15}+1 \\ &\equiv 11\cdot 12 +1 \\ &= 133 \\ &\equiv 0 \pmod{19}. \end{split}\end{equation}

Q.E.D.

補題7 n \equiv 27 \pmod{36}ならばs_n37で割り切れる。

証明. FLTより2^{36} \equiv 1 \pmod{37}であり、78557 \equiv 6, 2^{27} \equiv 6 \pmod{37}なので*4

\begin{equation}\begin{split}s_{36k+27} &= 78557\cdot 2^{36k+27} + 1 \\ &\equiv 78557\cdot 2^{27}+1 \\ &\equiv 6\cdot 6+1 \\ &\equiv 0 \pmod{37}. \end{split}\end{equation}

Q.E.D.

以上で、全てのnに対してs_nが合成数であることが証明できた。

知られている1000万以下のSierpinski数

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909,
965431, 1259779, 1290677, 1518781, 1624097, 1639459, 1777613, 2131043, 2131099,
2191531, 2510177, 2541601, 2576089, 2931767, 2931991, 3083723, 3098059, 3555593,
3608251, 4067003, 4095859, 4573999, 5455789, 5841947, 6134663, 6135559, 6557843,
6676921, 6678713, 6742487, 6799831, 6828631, 7134623, 7158107, 7400371, 7523267,
7523281, 7696009, 7761437, 7765021, 7892569, 8007257, 8184977, 8629967, 8840599,
8871323, 8879993, 8959163, 9043831, 9044629, 9208337, 9252323, 9454129, 9454157,
9854491, 9854603, 9930469, 9933857, 9937637

*1:このケースは直接分かりますが、指数が大きい場合はFLTを使った方がよいので。

*2:2^6 \equiv -1を用いれば計算しやすい。勿論直接計算で確かめられるが、Eulerの規準を用いて計算することもできる。

*3:2^9 \equiv -1\pmod{19}を用いると計算しやすい。

*4:2^{18} \equiv -1 \pmod{37}を用いると計算しやすい。