2014/05/21

フェルマー数とその性質

分野: 整数問題  レベル: 数学オリンピック

非負の整数 $n$ を用いて $F_n=2^{2^n}+1$ と表される整数をフェルマー数と呼ぶ

フェルマー数には様々な性質があります。このページでは特に重要な性質を3つ紹介します。

雰囲気をつかむために実際にフェルマー数を並べてみます。
$F_0=3,F_1=5,F_2=17,F_3=257,F_4=65537,\\F_5=4294967297=641 × 6700417$

フェルマー数を表す漸化式の導出

性質1:$F_n=\displaystyle\prod_{i=0}^{n-1}F_i+2$

フェルマー数に現れる $2^{2^n}$ がいかにも因数分解してほしそうな形をしているので,$a^2-b^2=(a-b)(a+b)$ を繰り返し用いて因数分解してやると漸化式が導出できます。

性質1の証明

フェルマー数の定義より,
$F_n-2=2^{2^n}-1\\
=(2^{2^{n-1}}-1)F_{n-1}\\
=(2^{2^{n-2}}-1)F_{n-2}F_{n-1}\\
\cdots\\
=\displaystyle\prod_{i=0}^{n-1}F_i$
より性質1が示された。

指数に整数が乗っていたらまずは因数分解を疑いましょう。→因数分解公式(n乗の差、和)

フェルマー数が互いに素であることの証明

性質2:フェルマー数どうしは互いに素

性質1を用いれば簡単に証明できます。

(性質2の証明)
背理法で証明する。2つのフェルマー数 $F_m,F_n (m <n)$ が共通因数 $p$ を持つと仮定すると,性質1より
$2=F_n-\displaystyle\prod_{i=0}^{n-1}F_i$ も $p$ の倍数となり $p=2$ となる。しかし,フェルマー数は全て奇数なので矛盾。

ちなみに,性質2と,全てのフェルマー数が素因数を最低1つは含んでいることから,素数が無限にあることが証明されました。

素数が無限にあることの証明はたくさん発見されています(→素数が無限にあることの美しい証明)が,フェルマー数を用いたこの方法はポリア(Polya)によって発見されました。

ちなみに,フェルマー数 $F_0$ から $F_4$ までは素数で $F_5$ は合成数なので,フェルマー数は素数も合成数も含んでいます。しかし,「フェルマー数は無限に多くの素数を含んでいる」のか,「フェルマー数は無限に多くの合成数を含んでいる」のか,いずれも証明されておらず未解決問題です。証明できたらご一報ください。

二重指数的に増える

性質3:フェルマー数はものすごい勢いで大きくなる

最初に実験したように $F_5$ でもかなり大きな数になっています。

$f(x)=a^{b^x}$ の形の関数を二重指数関数と呼び,指数関数よりも発散のスピードが速い関数として知られています。フェルマー数は二重指数関数です。フェルマー数に似た数列にシルベスターの数列がありますが,こちらも二重指数関数です。→シルベスターの数列とその性質

一般的に,多項式関数より指数関数の方が圧倒的に大きくなる(発散する)スピードが速いのですが,二重指数関数は指数関数よりも発散のスピードが速いのです。

ちなみに,二重指数関数は実際に工学的にも応用があります。(数値積分の計算スピードを上げる)

三重指数関数とかも理論的には考えられますが,実際に使われている場面を見たことがありません
分野: 整数問題  レベル: 数学オリンピック