フェルマー数
[Wikipedia|▼Menu]

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

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

実際にフェルマー数の値の最初の方をいくつか計算してみると、F0 = 21 + 1 = 3F1 = 22 + 1 = 5F2 = 24 + 1 = 17F3 = 28 + 1 = 257F4 = 216 + 1 = 65537F5 = 232 + 1 = 4294967297F6 = 264 + 1 = 18446744073709551617F7 = 2128 + 1 = 340282366920938463463374607431768211457F8 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937

が得られる。F4 = 65537 までは、257 未満の既知であるすべての素数で割りきれないことを確かめることで、容易に素数であることを確認できる。しかし F5 以降は(17世紀当時の計算技術から見ると)相当に巨大な数であると同時に小さな素因数を含んでいないことが、フェルマーを幻惑し反証の発見にはオイラーを待つこととなった要因の一つである。
目次

1 性質

1.1 基本的性質

1.2 フェルマー数の素因数

1.3 その他の性質


2 フェルマー素数

2.1 素数判定法

2.1.1 ぺピン・テスト



3 その他の未解決問題

4 脚注

5 参考文献

6 関連項目

7 外部リンク

性質
基本的性質

フェルマー数は次の漸化式を満たす:Fn = (Fn−1 − 1)2 + 1Fn = Fn−1 + 22n−1F0 ? Fn−2Fn = Fn−12 − 2(Fn−2 − 1)2Fn = F0 ? Fn−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 は偶数で m は 2 の累乗となる。実際、am + 1 は奇数だから am すなわち a は偶数である。また、m が 1 より大きい奇数 k で割れるならば am/k + 1 で割れる。

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

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

フェルマー数 Fn の最大素因数を P(Fn) とするとP(Fn) ? 2n+2(4n + 9) + 1

が成り立つ (Grytczuk, Luca and Wojtowicz, 2001)。

全てのフェルマー数の素因数全体の集合を S とする。Golomb (1955) は S の元の逆数和が収束するか否かという問題を提出したが、Krizek, Luca, Somer (2002) は S の元で x より小さいものの個数はO(x1/2log x)

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

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

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

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

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

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

フェルマー数の性質については、Krizek, Luca, Somer (2001) が詳しい。
フェルマー素数

素数であるフェルマー数をフェルマー素数という。具体的には、既知の範囲において次の5つがある:3, 5, 17, 257, 65537 (オンライン整数列大辞典の数列 A019434)

F4 までは素数なので、フェルマーは、全てのフェルマー数はフェルマー素数であると予想したが、5番目のフェルマー数は次のように分解できることを 1732年オイラーが示し、反例が与えられた。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 以降のフェルマー数で素数であるものが存在するかどうかは知られていない。また、フェルマー素数やフェルマー合成数が無限にあるかどうかも知られていない。

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

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

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

F n ∤ 3 ( F n − 1 ) / 2 + 1 {\displaystyle F_{n}\not \mid 3^{(F_{n}-1)/2}+1} ならば、Fn は合成数である

F n ∣ 3 ( F n − 1 ) / 2 + 1 {\displaystyle F_{n}\mid 3^{(F_{n}-1)/2}+1} ならば、Fn は素数である

基数は3以外の数値として以下を取ることを可能とする。5, 6, 7, 10, 12, 14, 20, 24, 27, 28, …(オンライン整数列大辞典の数列 A129802)
その他の未解決問題

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

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

[ヘルプ]
^ Guy, Unsolved Problems in Number Theory, p.16. 金光滋による訳本でも p.16.

参考文献

P. Erdos and E. G. Straus, On the irrationality of certain Ahmes series, J. Indian Math. Soc.(N. S.) 27(1963), 129--133.

S. W. Golomb, On the sum of the reciprocals of the Fermat numbers and related irrationalities, Canad. J. Math. 15(1963), 475--478.

A. Grytczuk, F. Luca and M. Wojtowicz(2001), Another note on the greatest prime factors of Fermat numbers, Southeast Asian Bull. Math. 25(2001), 111--115.

Florian Luca(2000a), The anti-social Fermat number, Amer. Math. Monthly 107(2000), 171--173.

Florian Luca(2000b), Fermar Numbers in the Pascal Triangle, Divulg. Math. 9(2001), 189--194, ⇒
[1].

Michal Krizek, Florian Luca and Lawrence Somer(2001), 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, CMS Books 9, ISBN 0387953329.

Michal Krizek, Florian Luca and Lawrence Somer(2002), On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97(2002), 95--112.

W. Sierpi?ski, Sue les nombres premiers de la forme nn + 1, L'Enseign. Math. (2) 4(1958), 211--212.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer-Verlag, 2004.

関連項目

素数

メルセンヌ数

外部リンク

Fermat factoring status


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:22 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:FIRTREE