フェルマー数とその性質

更新日時 2021/03/07

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

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

目次
  • フェルマー数の例

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

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

  • 二重指数的に増える

フェルマー数の例

雰囲気をつかむために,フェルマー数を並べてみます。

  • F0=21+1=3F_0=2^1+1=3
  • F1=22+1=5F_1=2^2+1=5
  • F2=24+1=17F_2=2^4+1=17
  • F3=28+1=257F_3=2^8+1=257
  • F4=216+1=65537F_4=2^{16}+1=65537
  • F5=232+1=4294967297=641×6700417F_5=2^{32}+1=4294967297=641 × 6700417

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

性質1

Fn=i=0n1Fi+2F_n=\displaystyle\prod_{i=0}^{n-1}F_i+2

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

性質1の証明

フェルマー数の定義より,

Fn2=22n1=(22n11)Fn1=(22n21)Fn2Fn1=i=0n1FiF_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つのフェルマー数 Fm,Fn(m<n)F_m,F_n (m <n) が共通因数 pp を持つと仮定すると,性質1より

2=Fni=0n1Fi2=F_n-\displaystyle\prod_{i=0}^{n-1}F_ipp の倍数となり p=2p=2 となる。しかし,フェルマー数は全て奇数なので矛盾。

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

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

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

二重指数的に増える

性質3

フェルマー数はものすごい勢いで大きくなる。

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

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

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

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

三重指数関数とかも理論的には考えられますが,実際に使われている場面を見たことがありません。

人気記事