インテジャーズ

INTEGERS

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

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}

Q.E.D.

補題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数

\begin{align}&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\end{align}

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

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

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

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