フェルマー数

数学の未解決問題
$n>4$ のとき、すべてのフェルマー数は合成数か？素数（合成数）であるフェルマー数は無数個（有限個）存在するか。

フェルマー数（フェルマーすう、英: Fermat number）とは、 $2 2 n + 1$ （ $n$ は非負整数）で表される自然数のことである。 $n$ 番目のフェルマー数はしばしば $F n$ と記される。

概要

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

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

F 0 = 2 1 + 1 = 3

F 1 = 2 2 + 1 = 5

F 2 = 2 4 + 1 = 17

F 3 = 2 8 + 1 = 257

F 4 = 2 16 + 1 = 65537

F 5 = 2 32 + 1 = 4294967297

F 6 = 2 64 + 1 = 18446744073709551617

F 7 = 2 128 + 1 = 340282366920938463463374607431768211457

F 8 = 2 256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937

が得られる。

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

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

性質

基本的性質

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

F n = (F n -1 - 1) 2 + 1

F n = F n -1 + 2 2 n -1 F 0 \dots F n -2

F n = F n -1 2 - 2(F n -2 - 1) 2

F n = F 0 \dots F n -1 + 2

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

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

$n \geq 2$ ならば、 $F n \equiv 17 or 41 (mod 72)$
$n \geq 2$ ならば、 $F n \equiv 17, 37, 57 or 97 (mod 100)$

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

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

フェルマー数の素因数

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

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

P (F n) \geq 2 n +2 (4 n + 9) + 1

が成り立つ^[2]。

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

O (x 1/2 log x)

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

その他の性質

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

F m F n \dots F s (2 s > m > n > \dots > s)

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

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

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

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

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

フェルマー素数

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

3

,

5

,

17

,

257

,

65537

(オンライン整数列大辞典の数列 A019434)

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

F 5 = 2 25 + 1 = 4294967297 = 641 \times 6700417

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

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

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

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

素数判定法

ペピン・テスト

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

$F n = 2 2 n$ + 1 $(n \geq 1)$ で ${F n$ }を定義すると、

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

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

5, 6, 7, 10, 12, 14, 20, 24, 27, 28, \dots

（オンライン整数列大辞典の数列 A129802）

その他の未解決問題

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

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

表記

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

名称	表記
クヌースの矢印表記	$2\uparrow 2\uparrow n+1,~\left(2\uparrow \right)^{2}n+1$

脚注

[脚注の使い方]

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

参考文献

Erdös, P; Straus, EG (1963). “On the irrationality of certain Ahmes series” (PDF). J. Indian Math. Soc (Citeseer) 27: 129-133.
Golomb, Solomon W. (1963). “On the Sum of the Reciprocals of the Fermat Numbers and Related Irrationalities”. Canadian Journal of Mathematics 15: 475-478. doi:10.4153/CJM-1963-051-0.
Grytczuk, A; Wójtowicz, M; Luca, Florian (2001). “Another note on the greatest prime factors of Fermat issues”. Southeast Asian Bulletin of Mathematics (Springer) 25: 111-115. doi:10.1007/s10012-001-0111-4. (要購読契約)
Luca, Florian (2000). “The anti-social Fermat issue”. The American Mathematical Monthly (Taylor & Francis) 107 (2): 171-173. doi:10.1080/00029890.2000.12005177.
Luca, Florian (2001). “Fermat issues in the Pascal triangle.” (PDF). Divulgaciones Matemáticas (La Universidad del Zulia) 9 (2): 189-194.
Michal Krizek, Florian Luca and Lawrence Somer(2001), 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, CMS Books 9, ISBN 0387953329.
Křížek, Michal; Luca, Florian; Somer, Lawrence (2002). “On the convergence of series of reciprocals of primes related to the Fermat issues”. Journal of Number Theory (Elsevier) 97 (1): 95-112. doi:10.1006/jnth.2002.2782.
W. Sierpiński, "Sue les nombres premiers de la forme $n n + 1$ ", L'Enseign. Math. (2) 4(1958), 211--212.
Richard K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer-Verlag, 2004.

外部リンク

[1] ポール・J・ナーイン, 小山信也『オイラー博士の素敵な数式』日本評論社、2008年、43頁。ISBN 9784535784772。国立国会図書館書誌ID:000009277698。、
『オイラー博士の素敵な数式』（2020年）、2020年。ISBN 9784480510204。

[FOOTNOTEGrytczuk,_Wójtowicz,_Florian2001-2] Grytczuk, Wójtowicz, Florian 2001.

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

[1]

[2]

[3]

表話編歴素数の分類
生成式	フェルマー ( $2 2 n + 1$ ) メルセンヌ ( $2 p - 1$ ) 二重メルセンヌ ( $2 2 p -1 - 1$ ) ワグスタッフ ( $(2 p + 1)/3$ ) プロス ( $k \cdot2 n + 1$ ) 階乗 ( $n! \pm 1$ ) 素数階乗 ( $p n # \pm 1$ ) ユークリッド ( $p n # + 1$ ) ピタゴラス ( $4 n + 1$ ) ピアポント ( $2 u \cdot3 v + 1$ ) Quartan（英語版） ( $x 4 + y 4$ ) ソリナス（英語版） ( $2 a \pm 2 b \pm 1$ ) カレン ( $n \cdot2 n + 1$ ) ウッダル ( $n \cdot2 n - 1$ ) Cuban（英語版） ( $(x 3 - y 3)/(x - y)$ ) キャロル ( $(2 n - 1) 2 - 2$ ) Kynea ( $(2 n + 1) 2 - 2$ ) レイランド ( $x y + y x$ ) サービト（英語版） ( $3\cdot2 n - 1$ ) ミルズ ( $[A] 3 n$ )
漸化式（英語版）	フィボナッチリュカペルニューマン–シャンクス–ウィリアムズペラン分割ベルモツキン
各種の性質	ヴィーフェリッヒ（英語版） (対（英語版）) ウォール–孫–孫（英語版）ウォルステンホルムウィルソン幸運フォーチュンラマヌジャン（英語版）ピライ正則強（英語版）スターン Supersingular (楕円曲線)（英語版） Supersingular (ムーンシャイン理論)（英語版）良いスーパーヒッグス（英語版）高度コトーティエント（英語版）
基数依存	ハッピー二面（英語版）回文エマープレピュニット ( $(10 n - 1)/9$ ) 置換可能 Circular（英語版）切り捨て可能 Strobogrammatic（英語版） Minimal（英語版）弱いフルサイクルプライム Unique（英語版） Primeval（英語版）自己スマランダチェ–ウェラン（英語版）
組	互いに素双子 ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) 三つ子 ( $p, p + 2$ or $p + 4, p + 6$ ) 四つ子 ( $p, p + 2, p + 6, p + 8$ ) k−Tuple いとこ ( $p, p + 4$ ) セクシー ( $p, p + 6$ ) 陳ソフィー・ジェルマン ( $p, 2 p + 1$ ) カニンガム鎖 ( $p, 2 p \pm 1, \dots$ ) 安全 ( $p, (p - 1)/2$ ) 算術数列（英語版） ( $p + an; n = 0, 1, \dots$ ) 平衡 ( $p - n, p, p + n$ )
桁数	タイタニック ( $103$ 桁以上) 巨大 ( $104$ 桁以上) メガ ( $106$ 桁以上)
複素数	アイゼンシュタイン素数（英語版）ガウス素数
合成数	擬素数概素数半素数楔数 Interprime（英語版）
関連する話題	確率的素数 Industrial-grade prime（英語版）違法素数素数の公式（英語版）素数の間隔『巨大な素数の一覧』
最初の50個	$2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ $31$ $37$ $41$ $43$ $47$ $53$ $59$ $61$ $67$ $71$ $73$ $79$ $83$ $89$ $97$ $101$ $103$ $107$ $109$ $113$ $127$ $131$ $137$ $139$ $149$ $151$ $157$ $163$ $167$ $173$ $179$ $181$ $191$ $193$ $197$ $199$ $211$ $223$ $227$ $229$
素数の一覧

概要

性質