6700417：第五フェルマー数の余素因数

第五Fermat数 $F_5$ の素因子 $641$ はご存知だと思いますが、 $6700417$ がその余因子であることを暗記している人は少ないかもしれません。この機会に是非覚えましょう。
integers.hatenablog.com

Sierpinski数を以前紹介しました：
integers.hatenablog.com

この記事では次の定理の証明を解説します：

定理 (Sierpinski (1960)) Sierpinski数は無数に存在する。

自分の名前が付いている数だから頑張って無限に存在することを証明したというよりは、この定理を証明したからSierpinski数という名前が付いたものと思われます。この記事で紹介する証明はIzotovによる証明です。

証明. 自然数 $t$ を

$\begin{align} t &\equiv 1 \pmod{2} \\ t &\equiv 1 \ \text{or}\ 2 \pmod{3} \\ t &\equiv 0 \pmod{5} \\ t &\equiv 1, 4, 13, \ \text{or} \ 16 \pmod{17} \\ t &\equiv 1, 16, 241, \ \text{or} \ 256 \pmod{257} \\ t &\equiv 256, 318, 323, \ \text{or} \ 385 \pmod{641} \\ t &\equiv 1, 256, 65281, \ \text{or} \ 65536 \pmod{65537} \\ t &\equiv 1, 65536, 6634881, \ \text{or} \ 6700416 \pmod{6700417}\end{align}$

を満たすようなものとする（中国剰余定理によって、このような自然数は無数に存在する）。このとき、 $k:=t^4$ がSierpinski数であることを示す（そうすれば、このような $k$ は無数にあるのだからSierpinski数が無数に存在することも確定する）。

$t$ の取り方から

$\begin{align} k & \equiv 1 \pmod{2} \\ k & \equiv 1 \pmod{3} \\ k & \equiv 1 \pmod{17} \\ k & \equiv 1 \pmod{257} \\ k & \equiv 1 \pmod{65537} \\ k & \equiv 1 \pmod{6700417} \\ k & \equiv -1 \pmod{641}\end{align}$

が成り立つので、 $m \geq 9$ に対して

$\begin{align} &k\cdot 2^{2m+1} +1\equiv 0 \pmod{3} \\ &k\cdot 2^{8m+4} +1\equiv 0 \pmod{17} \\ &k\cdot 2^{16m+8} +1\equiv 0 \pmod{257} \\ &k\cdot 2^{32m+16} +1\equiv 0 \pmod{65537} \\ &k\cdot 2^{64m+32} +1\equiv 0 \pmod{6700417} \\ &k\cdot 2^{64m} +1\equiv 0 \pmod{641}\end{align}$

が成り立つ。こうして、 $n=4m+2$ と書けるとき以外は全て合成数であることが示された。

$n=4m+2$ としよう。このとき、

$\begin{equation}\begin{split} k\cdot 2^n+1 &= t^4\cdot 2^{4m+2}+1 \\ &=4(t\cdot 2^m)^4+1 \\ &= (t^2\cdot 2^{2m+1}+t\cdot 2^{m+1}+1)(t^2\cdot 2^{2m+1}-t\cdot 2^{m+1}+1)\end{split}\end{equation}$

と因数分解できる。 $t > 1$ より $t^2\cdot 2^{2m+1}-t\cdot 2^{m+1}+1 > 1$ となって、 $k\cdot 2^{4m+2}+1$ も合成数であることが示された。 Q.E.D.

コメント シェルピンスキー数 $k$ に対して、素数の有限集合 $P$ が $k$ の被覆集合であるとは、任意の $n$ に対して $k\cdot 2^n+1$ が $P$ のある元で割り切れるときにいいます。以前紹介したSelfridgeの証明より、 $78557$ の被覆集合として $\{3, 5, 13, 19, 37, 73\}$ がとれることが分かります。

さて、Sierpinskiの定理のSierpinski自身の論文はまだ入手できていないのですが、Izotovの論文に「Sierpinskiは被覆集合が $\{3, 5, 17, 257, 641, 65537, 6700417\}$ であるようなSierpinski数が無数に存在することを示した」とあるので、その証明は想像できます。

すなわち、

$\begin{align} k & \equiv 1 \pmod{3} \\ k &\equiv 1 \pmod{5} \\ k & \equiv 1 \pmod{17} \\ k & \equiv 1 \pmod{257} \\ k & \equiv 1 \pmod{65537} \\ k & \equiv 1 \pmod{6700417} \\ k & \equiv -1 \pmod{641}\end{align}$

を満たすような奇数 $k$ はSierpinski数になるというものです。これは、Fermat数 $F_l$ の素因数 $p$ に対して $k \equiv 1 \pmod{p}$ ならば

$\displaystyle k\cdot 2^{2^{l+1}m+2^l}+1 \equiv 0 \pmod{p}$

となることを用いることによって、 $n$ を

自然数を奇数と偶数、偶数を $4m+2$ 型と $4$ の倍数、 $4$ の倍数を $8m+4$ 型と $8$ の倍数…

と分けていったとき $k\cdot 2^n+1$ のそれぞれが合成数となるというアイデアに基づいています。もし、Fermat数が全て素数であればこの論法では上手く被覆集合を取れないですが、 $F_5$ に至って素因数が二つ現れることによって有限個の素数で被覆集合を作ることが出来たという寸法です
（ $k \equiv -1\pmod{641}$ より $k\cdot 2^{64m}+1 \equiv 0 \pmod{p}$ となる）。 $F_5=641 \times 6700417$ の両方の素因数を用いた証明と言えるでしょう。

これは上手い論法ですが、全てのSierpinski数が被覆集合 $\{3, 5, 17, 257, 641, 65537, 6700417\}$ を持つわけではありません。そのことはSelfridgeの例からも分かりますし、被覆集合をもたないSierpinski数がないとも言えません。

Izotovが何をやったかというと、証明はSierpinskiの証明に基づきつつも上手く因数分解を用いることによって、結果として $\{3, 5, 17, 257, 641, 65537, 6700417\}$
を被覆集合にもたないようなSierpinski数が無数に存在することを示したということです。これは、 $k \equiv 0 \pmod{5}$ から $k\cdot 2^{4m+2}+1 \equiv 1 \not \equiv 0 \pmod{5}$ によって保障されます。

6700417：第五フェルマー数の余素因数

インテジャーズ

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