インテジャーズ

INTEGERS

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

フェルマー数とオイラーの素因数641

641は合成数であるような最小のFermat数F_5の小さい方の素因数です。

定義 非負整数nに対し、第nFermat数F_nF_n:=2^{2^n}+1で定義する。

例)  F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257, F_4 = 65537.
驚くべきことに、これらは全て素数です。Fermatは次のような予想を立てました:

予想 Fermat数は全て素数である。

この予想は実は誤りです。EulerがF_5が641で割り切れることを証明しました。

定理 (Euler) F_5641で割り切れる。

証明. 641=5^4+2^4なので、

5^4\cdot 2^{28}+2^{32}=2^{28}(5^4+2^{4})

641で割り切れる。一方、因数分解x^4-1=(x-1)(x+1)(x^2+1)より、641=5\cdot 2^7+1

5^4\cdot 2^{28}-1=(5\cdot 2^7)^4-1

を割り切る。従って、

F_5=2^{32}+1=(5^4\cdot 2^{28}+2^{32})-(5^4\cdot 2^{28}-1)

641で割り切れる。 Q.E.D.

結局、次の2つは未解決です:

未解決問題1 最初の5個のFermat数以外に、素数であるようなFermat数(Fermat素数)は存在するか?

未解決問題2 合成数であるようなFermat数は無数に存在するか?

素数定理を用いたheuristicな議論によれば、Fermat素数は有限個しかなさそうです:
integers.hatenablog.com
の最後に述べたように、与えられた数xが素数である確率を1/\log xと考えることにすると、Fermat数の個数の期待値は

\displaystyle \sum_{n=0}^{\infty}\frac{1}{\log (2^{2^n}+1)} < \frac{1}{\log 2}\sum_{n=0}^{\infty}\frac{1}{2^n} = \frac{2}{\log 2}

となります。


Fermat数の素因数を発見することは一般に難しいですが、それがどのような形をしているかということについて、次の定理が知られています:

Lucasの定理 n\geq 2のとき、F_nの素因数はある自然数kを用いてk\cdot 2^{n+2}+1と書ける。

証明. pF_n=2^{2^n}+1の素因数とする(明らかに奇数)。このとき、2^{2^n}\equiv -1\pmod{p}であるから、法p2の位数は2^{n+1}であることがわかる。n\geq 2および、Fermatの小定理よりp\equiv 1 \pmod{8}なので、Eulerの規準および第二補充則より2^{\frac{p-1}{2}} \equiv 1 \pmod{p}である。よって、2^{n+1}\frac{p-1}{2}の約数であることがわかった。すなわち、p \equiv 1 \pmod{2^{n+2}}Q.E.D.

Fermat数の性質として、次は基本的です:

定理 どの2つのFermat数をとっても、互いに素である。

証明. 非負整数nと自然数kに対してF_nF_{n+k}が互いに素であることを示す。因数分解

x^{2^k}-1=(x+1)(x^{2^k-1}-x^{2^k-2}+\cdots -1)

より、x=2^{2^n}とすればF_{n+k}-2=2^{2^{n+k}}-1F_nで割れることがわかる。よって、もしF_nF_{n+k}が共通素因数pをもてば、p2=F_{n+k}-(F_{n+k}-2)を割り切ることになる。Fermat数は奇数なので、これは生じ得ない。 Q.E.D.

この性質から素数の無限性の1つの証明が得られる*1: Fermat数の素因数を1つずつ取っていけば素数が無数に得られる。 Q.E.D.

最後に、F_n (n\geq 5)の素因数分解について分かっていることを纏めます(執筆時点での有効情報。最新情報はFermat factoring status参照)。

素因数分解が完全に決定されているもの(P_mm桁のある素数):
F_5 = 641\times 6700417
F_6 = 274177\times 67280421310721
F_7 = 59649589127497217\times 5704689200685129054721
F_8 = 1238926361552897\times P_{62}
F_9 = 2424833\times 7455602825647884208337395736200454918783366342657\times P_{99}
F_{10} = 45592577\times 6487031809\times 4659775785220018543264560743076778192897\times P_{252}
F_{11} = 319489\times 974849\times 167988556341760475137\times 3560841906445833920513\times P_{564}

素因数が6個決定されているもの:
F_{12}^*
素因数が4個決定されているもの:
F_{13}^*
素因数が3個決定されているもの:
F_{15}^*, F_{19}^*, F_{25}, F_{52}
素因数が2個決定されているもの
F_{16}^*, F_{17}^*, F_{18}^*, F_{27}, F_{30}, F_{36}, F_{38}, F_{39}, F_{42}, F_{77}, F_{147}, F_{150}, F_{284}, F_{416}, F_{417}
素因数が1個決定されているもの:
F_{14}^*, F_{21}^*, F_{22}^*, F_{23}^*, F_{26}, F_{28}, F_{29}, F_{31}, F_{32}, F_{37}, F_{43},
他にも43 < n \leq 3329780に240個ある。
素因数は一切見つかっていないが、合成数であることは証明されているもの:
F_{20}, F_{24}
何もわかっていないもの:
F_{33}, F_{34}, F_{35}, F_{40}, F_{41}, F_{44}, F_{45}, F_{46}, F_{47}, F_{49}, F_{50}, \dots

{}^*が付いているものは、分かっている素因数で割った残りの因数が合成数であることが証明されているもの。

*1:この証明はPolyaによるとされる文献が多数存在するが、それが一体なぜなのかを議論した mathoverflow.net が面白い。GoldbachやEulerは既にFermat数達が互いに素であることを知っていたらしい。しかし、素数の無限性証明が得られるという指摘はしていなかった。この指摘を最初にしたのはどうやらHurwitz(1891)らしい。Polyaによると言われ出した理由とされるPolya and Szego(1924)よりもだいぶ前のことである。こういった歴史はよくあることだ。もちろん、間違った歴史は修正していくことが望ましい。