数学の未解決問題
n > 4 {\displaystyle n>4} のとき、すべてのフェルマー数は合成数か?
素数(合成数)であるフェルマー数は無数個(有限個)存在するか。
フェルマー数(フェルマーすう、英: Fermat number)とは、22n + 1(n は非負整数)で表される自然数のことである。n 番目のフェルマー数はしばしば Fn と記される。 その名の由来であるピエール・ド・フェルマーは、この式の n に非負整数を代入したとき常に素数を生成すると主張(予測)したが、1732年にレオンハルト・オイラーが n = 5 の場合に素数でないことを示し、フェルマーの主張は誤りと確認された[1]。素数であるフェルマー数はフェルマー素数と呼ばれる。 実際にフェルマー数の値の最初の方をいくつか計算してみると、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世紀当時の計算技術から見ると)相当に巨大な数であると同時に小さな素因数を含んでいないことが、フェルマーを幻惑し反証の発見にはオイラーを待つこととなった要因の一つである。 フェルマー数は次の漸化式を満たす: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つのフェルマー数も互いに素であると分かる。 フェルマー数は、例えば次の合同式を満たす。 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 が成り立つ[2]。 全てのフェルマー数の素因数全体の集合を S とする。Golomb (1955) は S の元の逆数和が収束するか否かという問題を提出したが、(K?i?ek, Michal, Florian 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) の値にもならない(Florian Luca(2001))。 Golomb (1963) は、フェルマー数の逆数和は無理数であることを示した。なお、ポール・エルデシュと Straus はさらに一般的な結果を得ている。 フェルマー数はまた、正多角形の定規とコンパスによる作図の問題とも関係がある。ガウスは、正 n 角形が作図可能になる必要十分条件を求めたが、それは「n が 2 の冪であるか、異なるフェルマー素数の積と 2 の冪の積であるとき」というものである。 フェルマー数の性質については、(K?i?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 フェルマー数の素数性、素因数分解に関する情報は外部リンクに挙げたサイトが詳しい。 ペピン・テストはフランスの数学者テオフィル・ペピン(en:Theophile_Pepin Fn = 22n + 1 (n ? 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 を割り切る現象が無数に起こるかどうかも知られていない。 フェルマー数を表すにはいくつか等価な表記がある。 名称表記
概要
性質
基本的性質
n ? 2 ならば、Fn ≡ 17 or 41 (mod 72)
n ? 2 ならば、Fn ≡ 17, 37, 57 or 97 (mod 100)
フェルマー数の素因数
その他の性質
フェルマー素数
素数判定法
ペピン・テスト
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 は素数である
その他の未解決問題
表記
クヌースの矢印表記 2 ↑ 2 ↑ n + 1 , ( 2 ↑ ) 2 n + 1 {\displaystyle 2\uparrow 2\uparrow n+1,~\left(2\uparrow \right)^{2}n+1}
脚注[脚注の使い方]^ ポール・J・ナーイン, 小山信也『オイラー博士の素敵な数式』日本評論社、2008年、43頁。.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 9784535784772。
Size:29 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef