78557：シェルピンスキー数 - インテジャーズ

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

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

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

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

まずは $n$ が偶数の場合：

補題１ $n \equiv 0 \pmod{2}$ ならば $s_n$ は $3$ で割り切れる。

証明. Fermatの小定理（FLT）より $2^2 \equiv 1 \pmod{3}$ であり*1、 $78557 \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}$ で分けます。

補題２ $n \equiv 1 \pmod{4}$ ならば $s_n$ は $5$ で割り切れる。

証明. 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}$ で分けます。

補題３ $n \equiv 7 \pmod{12}$ ならば $s_n$ は $7$ で割り切れる。

証明. 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.

補題４ $n \equiv 11 \pmod{12}$ ならば $s_n$ は $13$ で割り切れる。

証明. 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}$ に分ける。

補題５ $n \equiv 3 \pmod{36}$ ならば $s_n$ は $73$ で割り切れる。

証明. 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}$

補題６ $n \equiv 15 \pmod{36}$ ならば $s_n$ は $19$ で割り切れる。

証明. 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.

補題７ $n \equiv 27 \pmod{36}$ ならば $s_n$ は $37$ で割り切れる。

証明. 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}$ を用いると計算しやすい。