インテジャーズ

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

インテジャーズ

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

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

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に対して、素数の有限集合Pkの被覆集合であるとは、任意のnに対してk\cdot 2^n+1Pのある元で割り切れるときにいいます。以前紹介した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}によって保障されます。