数学の未解決問題
  1. のとき、すべてのフェルマー数は合成数か?
  2. 素数(合成数)であるフェルマー数は無数個(有限個)存在するか。

フェルマー数(フェルマーすう、: Fermat number)とは、22n + 1n は非負整数)で表される自然数のことである。n 番目のフェルマー数はしばしば Fn と記される。

概要

編集

その名の由来であるピエール・ド・フェルマーは、この式の n に非負整数を代入したとき常に素数を生成すると主張(予測)したが、1732年レオンハルト・オイラーn = 5 の場合に素数でないことを示し、フェルマーの主張は誤りと確認された[1]。素数であるフェルマー数はフェルマー素数と呼ばれる。

実際にフェルマー数の値の最初の方をいくつか計算してみると、

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65537
F5 = 232 + 1 = 4294967297
F6 = 264 + 1 = 18446744073709551617
F7 = 2128 + 1 = 340282366920938463463374607431768211457
F8 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937

が得られる。

F4 = 65537 までは、257 未満の既知である全ての素数で割りきれないことを確かめることで、容易に素数であることを確認できる。

しかし F5 以降は(17世紀当時の計算技術から見ると)相当に巨大な数であると同時に小さな素因数を含んでいないことが、フェルマーを幻惑し反証の発見にはオイラーを待つこととなった要因の一つである。

性質

編集

基本的性質

編集

フェルマー数は次の漸化式を満たす:

Fn = (Fn−1 − 1)2 + 1
Fn = Fn−1 + 22n−1F0Fn−2
Fn = Fn−12 − 2(Fn−2 − 1)2
Fn = F0Fn−1 + 2

フェルマー数は全て奇数であるから、4番目の式から、どの2つのフェルマー数も互いに素であると分かる。

フェルマー数は、例えば次の合同式を満たす。

  • n ≥ 2 ならば、Fn ≡ 17 or 41 (mod 72)
  • n ≥ 2 ならば、Fn ≡ 17, 37, 57 or 97 (mod 100)

2m + 1 (m ≥ 2) の形の素数はフェルマー数である。一般に、am + 1 (a ≥ 2) が素数ならば、a は偶数で m2 の累乗となる。実際、am + 1 は奇数だから am すなわち a は偶数である。また、m1 より大きい奇数 k で割れるならば am/k + 1 で割れる。

このことから、2m + 1 (m ≥ 2) が素数ならば、m = 2n を満たす自然数 n が存在する。つまり 2m + 1 = Fn である。

フェルマー数の素因数

編集

フェルマー数 Fn (n ≥ 2) の素因数は k · 2n + 2 + 1 (k ≥ 3) の形をしている(エドゥアール・リュカにより証明)。フェルマー数はどの2つも互いに素なので、任意の n に対して k · 2n + 1 (k = 1, 2, …) の形の素数が無数に存在することが導かれる。また実際に 3 · 2n+2 + 1Fn を割り切る例が存在する。

フェルマー数 Fn の最大素因数を P(Fn) とすると

P(Fn) ≥ 2n+2(4n + 9) + 1

が成り立つ[2]

全てのフェルマー数の素因数全体の集合を S とする。Golomb (1955) は S の元の逆数和が収束するか否かという問題を提出したが、(Křížek, Michal, Florian 2002) は S の元で x より小さいものの個数は

O(x1/2log x)

となることを示し、この問題を肯定的に解決した。

その他の性質

編集

22m ≡ −1 (mod Fm) より、2Fm を法とする位数2m+1 で、これは Fm − 1 の約数である。すなわち、フェルマー数は 2 を底とする擬素数である。また、フェルマー数の積

FmFnFs (2s > m > n > ⋯ > s)

も擬素数である (Cipolla, 1904)。

フェルマー数は累乗数にはならず、また、完全数または友愛数にはならず (Luca, 2000a)、二項係数 nCk (n ≥ 2k ≥ 2) の値にもならない(Florian Luca(2001))。

Golomb (1963) は、フェルマー数の逆数和は無理数であることを示した。なお、ポール・エルデシュと Straus はさらに一般的な結果を得ている。

フェルマー数はまた、正多角形の定規とコンパスによる作図の問題とも関係がある。ガウスは、正 n 角形が作図可能になる必要十分条件を求めたが、それは「n2 の冪であるか、異なるフェルマー素数の積と 2 の冪の積であるとき」というものである。

フェルマー数の性質については、(Křížek, Michal, Florian 2002) が詳しい。

フェルマー素数

編集

素数であるフェルマー数をフェルマー素数という。具体的には、既知の範囲において次の5つがある:

3, 5, 17, 257, 65537 (オンライン整数列大辞典の数列 A019434)

F4 までは素数なので、フェルマーは、全てのフェルマー数はフェルマー素数であると予想したが、1732年にレオンハルト・オイラーが5番目のフェルマー数は次のように分解できることを示し、反例が与えられた。

F5 = 225 + 1 = 4294967297 = 641 × 6700417

オイラーは、フェルマー数 Fn の因数は k·2n+1 + 1 の形となることを証明した。これにより n = 5 の場合には、F5 の因数は 64k + 1 の形をとる。このことを利用して、オイラーは因数 641 = 10 × 64 + 1 を見つけたのである。その後、上記「フェルマー数の素因数」の記述の通り、エドゥアール・リュカにより k·2n+2 + 1 の形のものに限られることが示された。

また、定規とコンパスによる作図問題の1つである、正多角形は(定規とコンパスのみで)作図できるかという問題において、正 n 角形が作図可能であるのは、n素因数分解したときに奇数因子が全てフェルマー素数であり、なおかつそれらが相異なる場合のみであることがガウスにより証明されている。

現在 F5 以降のフェルマー数で素数であるものが存在するかどうかは知られていない。また、フェルマー素数やフェルマー合成数が無限にあるかどうかも知られていない。フェルマー数の最大素因数についてはA070592を、最小素因数についてはA093179を参照。

フェルマー数の素数性、素因数分解に関する情報は外部リンクに挙げたサイトが詳しい。

素数判定法

編集

ペピン・テスト

編集

ペピン・テストはフランスの数学者テオフィル・ペピン(en:Théophile_Pépin)によって名付けられたフェルマー数に対する素数判定法である。

Fn = 22n + 1 (n ≥ 1){Fn}を定義すると、

  •   ならば、Fn は合成数である
  •   ならば、Fn は素数である

基数は3以外の数値として以下を取ることを可能とする。

5, 6, 7, 10, 12, 14, 20, 24, 27, 28, …オンライン整数列大辞典の数列 A129802

その他の未解決問題

編集

フェルマー数は平方因子を持たないと予想されているが、未だに解決されていない[3]

m = 20, 24 に対して Fm は合成数であることが知られているが、その素因数は1つも知られていない。k を1つ決めた時に k·2m+2 + 1Fm を割り切る現象が無数に起こるかどうかも知られていない。

表記

編集

フェルマー数を表すにはいくつか等価な表記がある。

名称 表記
クヌースの矢印表記  

脚注

編集
  1. ^ ポール・J・ナーイン, 小山信也『オイラー博士の素敵な数式』日本評論社、2008年、43頁。ISBN 9784535784772国立国会図書館書誌ID:000009277698 
    『オイラー博士の素敵な数式』(2020年)、2020年。ISBN 9784480510204 
  2. ^ Grytczuk, Wójtowicz, Florian 2001.
  3. ^ Guy, Unsolved Problems in Number Theory, p.16. 金光滋による訳本でも p.16.

参考文献

編集

関連項目

編集

外部リンク

編集