数学の未解決問題
n
>
4
{\displaystyle n>4}
のとき、すべてのフェルマー数は合成数か?
素数(合成数)であるフェルマー数は無数個(有限個)存在するか。
フェルマー数 (フェルマーすう、英 : Fermat number )とは、22n + 1 (n は非負整数 )で表される自然数 のことである。n 番目のフェルマー数はしばしば Fn と記される。
概要
その名の由来であるピエール・ド・フェルマー は、この式の n に非負整数を代入したとき常に素数 を生成すると主張(予測)したが、1732年 にレオンハルト・オイラー が n = 5 の場合に素数でないことを示し、フェルマーの主張は誤りと確認された[1] 。素数であるフェルマー数はフェルマー素数 と呼ばれる。
実際にフェルマー数の値の最初の方をいくつか計算してみると、
F 0 = 21 + 1 = 3
F 1 = 22 + 1 = 5
F 2 = 24 + 1 = 17
F 3 = 28 + 1 = 257
F 4 = 216 + 1 = 65537
F 5 = 232 + 1 = 4294967297
F 6 = 264 + 1 = 18446744073709551617
F 7 = 2128 + 1 = 340282366920938463463374607431768211457
F 8 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937
が得られる。
F 4 = 65537 までは、257 未満の既知である全ての素数で割りきれないことを確かめることで、容易に素数であることを確認できる。
しかし F 5 以降は(17世紀 当時の計算技術から見ると)相当に巨大な数であると同時に小さな素因数 を含んでいないことが、フェルマーを幻惑し反証の発見にはオイラーを待つこととなった要因の一つである。
性質
基本的性質
フェルマー数は次の漸化式 を満たす:
Fn = (F n −1 − 1)2 + 1
Fn = F n −1 + 22n −1 F 0 ⋯ F n −2
Fn = F n −12 − 2(F n −2 − 1)2
Fn = F 0 ⋯ F n −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 ) の形をしている(エドゥアール・リュカ により証明)。フェルマー数はどの2つも互いに素なので、任意の n に対して k · 2n + 1 (k = 1, 2, …) の形の素数が無数に存在することが導かれる。また実際に 3 · 2n +2 + 1 が Fn を割り切る例が存在する。
フェルマー数 Fn の最大素因数を P (Fn ) とすると
P (Fn ) ≥ 2n +2 (4n + 9) + 1
が成り立つ。
全てのフェルマー数の素因数全体の集合を S とする。Golomb (1955) は S の元の逆数和が収束するか否かという問題を提出したが、(Křížek, Michal, Florian 2002 ) は S の元で x より小さいものの個数は
O (x 1/2 log x )
となることを示し、この問題を肯定的に解決した。
その他の性質
22m ≡ −1 (mod Fm ) より、2 の Fm を法とする位数 は 2m +1 で、これは Fm − 1 の約数である。すなわち、フェルマー数は 2 を底とする擬素数 である。また、フェルマー数の積
Fm Fn ⋯Fs (2s > m > n > ⋯ > s )
も擬素数である (Cipolla, 1904)。
フェルマー数は累乗数 にはならず、また、完全数 または友愛数 にはならず (Luca, 2000a)、二項係数 n Ck (n ≥ 2k ≥ 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 = 225 + 1 = 4294967297 = 641 × 6700417
オイラーは、フェルマー数 Fn の因数は k ·2n +1 + 1 の形となることを証明した。これにより n = 5 の場合には、F 5 の因数は 64k + 1 の形をとる。このことを利用して、オイラーは因数 641 = 10 × 64 + 1 を見つけたのである。その後、上記「フェルマー数の素因数」の記述の通り、エドゥアール・リュカ により k ·2n +2 + 1 の形のものに限られることが示された。
また、定規とコンパスによる作図 問題の1つである、正多角形 は(定規とコンパスのみで)作図できるか という問題において、正 n 角形が作図可能であるのは、n を素因数分解 したときに奇数因子が全てフェルマー素数であり、なおかつそれらが相異なる場合のみであることがガウス により証明されている。
現在 F 5 以降のフェルマー数で素数であるものが存在するかどうかは知られていない。また、フェルマー素数やフェルマー合成数が無限にあるかどうかも知られていない。フェルマー数の最大素因数 についてはA070592 を、最小素因数 についてはA093179 を参照。
フェルマー数の素数性、素因数分解に関する情報は外部リンクに挙げたサイトが詳しい。
素数判定法
ペピン・テスト
ペピン・テストはフランスの数学者テオフィル・ペピン(en:Théophile_Pépin )によって名付けられたフェルマー数に対する素数判定法である。
Fn = 2 2 n + 1 (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 )
その他の未解決問題
フェルマー数は平方因子を持たないと予想されているが、未だに解決されていない[3] 。
m = 20, 24 に対して Fm は合成数であることが知られているが、その素因数は1つも知られていない。k を1つ決めた時に k ·2m +2 + 1 が Fm を割り切る現象が無数に起こるかどうかも知られていない。
表記
フェルマー数を表すにはいくつか等価な表記がある。
名称
表記
クヌースの矢印表記
2
↑ ↑ -->
2
↑ ↑ -->
n
+
1
,
(
2
↑ ↑ -->
)
2
n
+
1
{\displaystyle 2\uparrow 2\uparrow n+1,~\left(2\uparrow \right)^{2}n+1}
脚注
参考文献
Erdös, P; Straus, EG (1963). “On the irrationality of certain Ahmes series” (PDF). J. Indian Math. Soc (Citeseer) 27 : 129-133. https://users.renyi.hu/~p_erdos/1957-07.pdf .
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 . https://doi.org/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 . https://doi.org/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 . https://doi.org/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. https://www.emis.de/journals/DM/v92/art8.pdf .
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 . https://doi.org/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.
関連項目
外部リンク
生成式 漸化式 (英語版 ) 各種の性質 基数依存 組
互いに素
双子 (p , p + 2 )
Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, … )
三つ子 (p , p + 2 or p + 4, p + 6 )
四つ子 (p , p + 2, p + 6, p + 8 )
k −Tuple
いとこ (p , p + 4 )
セクシー (p , p + 6 )
陳
ソフィー・ジェルマン (p , 2p + 1 )
カニンガム鎖 (p , 2p ± 1, … )
安全 (p , (p − 1)/2 )
算術数列 (英語版 ) (p + an ; n = 0, 1, … )
平衡 (p − n , p , p + n )
桁数 複素数 合成数 関連する話題 最初の50個
素数の一覧