Loading article…
In mathematics, a Fermat number, named after Pierre de Fermat (1601–1665), the first known to have studied them, is a positive integer of the form: where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, 340282366920938463463374607431768211457, ... (sequence A000215 in the OEIS).
If 2k + 1 is prime and k > 0, then k itself must be a power of 2,[1] so 2k + 1 is a Fermat number; such primes are called Fermat primes. As of 2026, the only known Fermat primes are F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65537(sequence A019434 in the OEIS).
The Fermat numbers satisfy the following recurrence relations:
for n ≥ 1,
for n ≥ 2. Each of these relations can be proved by mathematical induction. From the second equation, we can deduce Goldbach's theorem (named after Christian Goldbach): no two Fermat numbers share a common integer factor greater than 1. To see this, suppose that 0 ≤ i < j and Fi and Fj have a common factor a > 1. Then a divides both
そしてF j。したがってa はそれらの差 2 を割り切ります。a > 1なので、これはa = 2を強制します。これは矛盾です。なぜなら、各フェルマー数は明らかに奇数だからです。系として、素数の無限性の別の証明が得られます。各F nに対して、素因数p nを選択します。すると、数列{ p n }は異なる素数の無限列になります。
フェルマー数とフェルマー素数は、ピエール・ド・フェルマーによって初めて研究され、彼はすべてのフェルマー数が素数であると予想しました。実際、最初の 5 つのフェルマー数F 0、 ...、F 4は簡単に素数であることが示されます。フェルマーの予想は、1732 年にレオンハルト・オイラーによって反駁されました。彼は、641 で割ることによって、
オイラーは、 n ≥ 2の場合、F nのすべての因数はk 2 n +1 + 1の形を持たなければならないことを証明しました(後にルーカスによってk 2 n +2 + 1に改良されました) 。
641 がF 5の因数であることは、後から考えると次のように推論できます。 等式 641 = 2 7 × 5 + 1 および 641 = 2 4 + 5 4から、最初の等式から 2 7 × 5 ≡ −1 (mod 641) が成り立ち、したがって (4 乗して) 2 28 × 5 4 ≡ 1 (mod 641) となります。一方、2 番目の等式は 5 4 ≡ −2 4 (mod 641) を意味します。これらの合同式から 2 32 ≡ −1 (mod 641) が成り立ちます。
フェルマーはおそらくオイラーによって後に証明された因数の形を知っていたはずなので、因数を見つけるための単純な計算を最後まで行わなかったのは不思議に思える。[ 2 ]一般的な説明の一つは、フェルマーが計算ミスをしたというものである。
n > 4のフェルマー素数F nは他に知られていませんが、大きなnのフェルマー数についてはほとんど知られていません。[ 3 ]実際、以下のそれぞれは未解決問題です。
2025年12月現在 F n は5 ≤ n ≤ 32の場合合成数であることが知られていますが、これらのうち、F nの完全な因数分解が知られているのは0 ≤ n ≤ 11の場合のみであり、 n = 20およびn = 24の既知の素因数は存在しません。[ 5 ]合成数であることが知られている最大のフェルマー数はF 18233954であり、その素因数7 × 2 18233956 + 1は 2020 年 10 月に発見されました。
経験則によれば、F4は最後のフェルマー素数である。
素数定理によれば、 N の周りの適切な区間内のランダムな整数は、1 / ln N の確率で素数になります。フェルマー数がそのサイズのランダムな整数と同じ確率で素数であり、 F 5、...、F 32が合成数であるというヒューリスティックを用いると、 F 4 (または同等にF 32 )を超えるフェルマー素数の期待値は次のようになります。
この数値は、 F4を超えるフェルマー素数が存在する確率の上限値として解釈できる。
この議論は厳密な証明ではありません。まず、フェルマー数が「ランダム」に振る舞うと仮定していますが、フェルマー数の因数は特別な性質を持っています。ボクランとコンウェイは、別のフェルマー素数が存在する確率は10億分の1未満であることを示唆する、より精密な分析を発表しました。[ 6 ]
アンダース・ビョルンとハンス・リーゼルは、 F 5以降のフェルマー数の平方因子の数を次のように推定した。
言い換えれば、平方因子を持たないフェルマー数は存在しない可能性が高く、一般に平方因子はnが大きい場合、非常にまれである。[ 7 ]
させてn番目のフェルマー数をとする。ペパンの判定法によれば、n > 0の場合、
その表現を法として評価できます繰り返し二乗することで、このテストは高速な多項式時間アルゴリズムとなる。しかし、フェルマー数は非常に急速に増加するため、妥当な時間と空間でテストできるのはごく少数に限られる。
k 2 m + 1の形の数の素数判定には、フェルマー数の因数など、いくつかのテストがあります。
N = F n > 3の場合、上記のヤコビ記号はa = 3に対して常に −1 となり、このプロスの定理の特殊なケースはペパンの判定法として知られています。ペパンの判定法とプロスの定理は、いくつかのフェルマー数の合成数性を証明するためにコンピュータ上で実装されていますが、どちらの判定法も特定の非自明な因子を与えるものではありません。実際、n = 20および 24 に対して特定の素因数は知られていません。
フェルマー数の大きさゆえに、素因数分解はおろか素数判定さえも困難です。ペパンの素数判定法は、フェルマー数の素数判定に必要な十分条件を与え、現代のコンピュータで実装可能です。楕円曲線法は、小さな数の素因数を見つけるための高速な方法です。分散コンピューティングプロジェクトであるFermatsearchは、フェルマー数のいくつかの因数を発見しました。イヴ・ガロの方法はproth.exe、大きなフェルマー数の因数を見つけるために用いられてきました。エドゥアール・リュカは、オイラーの上記の結果を改良し、1878年にフェルマー数のすべての因数がnが少なくとも2の場合、次の形式になります。（プロス数を参照）ここでkは正の整数である。これだけで、既知のフェルマー素数の素数性を容易に証明できる。
最初の12個のフェルマー数の因数分解は次のとおりです。
2025年1月現在 F 0からF 11までが完全に因数分解されている。[ 5 ]分散コンピューティングプロジェクト Fermat Search は、フェルマー数の新しい因数を探している。[ 9 ]すべてのフェルマー因数の集合は、OEISのA050922 (または、ソートするとA023394 ) である。
フェルマー数の以下の因数は1950年以前には知られていました（それ以降、デジタルコンピュータの発展により、さらに多くの因数が発見されています）。
2025年12月現在 フェルマー数の素因数は375個知られており、フェルマー数は合成数であることが330個知られています。[ 5 ]毎年いくつかの新しいフェルマー因子が発見されています。[ 10 ]
2 p − 1の形の合成数と同様に、すべての合成フェルマー数は2 を基数とする強い擬素数です。これは、2 を基数とするすべての強い擬素数がフェルマー擬素数でもあるためです。
すべてのフェルマー数に対して。[ 11 ]
1904年、チポラは、少なくとも2つの異なる素数または合成フェルマー数の積が2 を底とするフェルマー擬素数となるのは、[ 12 ]
フェルマー数は完全数にも、友好数のペアの一部にもなり得ない。（ルカ 2000 ）
フェルマー数のすべての素因数の逆数の級数は収束する。（Křížek、Luca & Somer 2002 ）
n + 1が素数で、整数mが存在し、 n = 2 2 mとなる。 この場合、方程式 n n + 1 = F (2 m + m )が成り立つ。 [ 13 ] [ 14 ]
フェルマー数F nの最大の素因数をP ( F n )とする。すると、
カール・フリードリヒ・ガウスは著書『算術研究』の中でガウス周期の理論を展開し、正多角形の作図可能性の十分条件を定式化した。ガウスはこの条件が必須条件でもあると述べたが[ 15 ]、証明は公表しなかった。ピエール・ワンツェルは1837年に必須条件の完全な証明を与えた。この結果はガウス＝ワンツェルの定理として知られている。
正の整数nが上記の形式であるのは、そのトーシェントφ ( n ) が 2 のべき乗である場合に限る。
フェルマー素数は、1, ... , N ( Nは 2 のべき乗) の範囲で擬似乱数列を生成する際に特に有用です。最も一般的な方法は、1 からP − 1までの任意のシード値 ( Pはフェルマー素数) を取得することです。次に、このシード値に、 Pの平方根より大きく、Pを法とする原始根(つまり、平方剰余ではない)である数Aを掛けます。そして、その結果をPで法とします。この結果が乱数生成器の新しい値となります。
これはコンピュータサイエンスにおいて有用です。なぜなら、ほとんどのデータ構造には 2 X 個の可能な値を持つメンバーがあるからです。たとえば、1 バイトには 256 (2 8 ) 個の可能な値 (0～255) があります。したがって、1 バイトまたは複数のバイトをランダムな値で埋めるには、1～256 の値を生成する乱数生成器を使用し、そのバイトに出力値 -1 を代入することができます。この理由から、非常に大きなフェルマー素数はデータ暗号化において特に注目されています。この方法では、 P - 1 回繰り返すとシーケンスが繰り返されるため、擬似乱数のみが生成されます。乗数が不適切に選択されると、シーケンスがP - 1 回よりも早く繰り返される可能性があります。
形式の数字a、b が互いに素な任意の整数 ( a > b > 0 )は、一般化フェルマー数と呼ばれます。奇素数pが一般化フェルマー数であるのは、 p が1 (mod 4)と合同である場合のみです。(ここではn > 0 の場合のみを考慮します。したがって3 =（反例ではない。）
この形式の素数の可能性のある例としては、200 262144 + 119 262144 (ケレン・シェントンによって発見) がある。[ 16 ]
通常のフェルマー数との類推により、一般化フェルマー数は次の形式で表されるのが一般的である。F n ( a )のように表記します。この表記では、例えば、100,000,001 という数はF 3 (10) と表記されます。以下では、この形式の素数に限定します。このような素数は「 aを底とするフェルマー素数」と呼ばれます。もちろん、これらの素数はa が偶数の場合にのみ存在します。
素数であることを証明しやすいことから、一般化フェルマー素数は近年、数論の分野における研究テーマとして注目を集めている。現在知られている最大の素数の多くは、一般化フェルマー素数である。
一般化フェルマー数は、 aが偶数の場合 にのみ素数となり得る。aが奇数の場合、すべての一般化フェルマー数は2で割り切れるからである。最小の素数はとは、または 30 32 + 1。さらに、奇数基数に対する「半一般化フェルマー数」を定義することができ、基数a (奇数aの場合)に対する半一般化フェルマー数は次のようになります。また、各奇数基数に対して、半一般化フェルマー素数は有限個しか存在しないことも予想される。
このリストには、一般化フェルマー数（）は、奇数の場合、それらはa が奇数指数を持つ完全べき乗である場合( OEISのシーケンスA070265 )、すべての一般化フェルマー数は代数的に因数分解できるため、素数にはなり得ません。
1000までの偶数基数については[ 17 ] [ 18 ]を、奇数基数については[ 19 ]を参照してください。最小数についてはそのため素数です。（OEISの配列A253242を参照）。
最小の偶数底aに対して、素数です。（OEISの配列A056993を参照）。
一般化フェルマー素数F 14 (71) は、基底b ≤ 1000で知られている最大の一般化フェルマー素数であり、楕円曲線素数証明により素数であることが証明されています。[ 20 ]
F n ( b ) = b 2 n + 1 ( n = 0, 1, 2, ...) が素数となる最小の偶数基数b は
F n ( b ) = ( b 2 n + 1)/2 ( n = 0, 1, 2, ...) が素数 (または素数の可能性が高い)となる最小の奇数基数b は
逆に、 (2 n ) k + 1 (与えられたnに対して) が素数となる最小のk は
より精緻な理論は、塩基の数を予測するために使用できます。固定価格に最適一般化フェルマー素数の数は、おおよそ半減すると予想される。1増加します。
次のような一般化フェルマー素数を構成することも可能である。b = 1の場合と同様に、 a + bが偶数であれば、この形式の数は常に 2 で割り切れますが、このタイプの一般化されたハーフフェルマー素数を定義することは可能です。この形式の最小の素数については、（奇数の場合））、 （OEISの配列A111635も参照）。
以下は、既知の最大規模の一般化フェルマー素数トップ10のリストです。[ 22 ]トップ10はすべてPrimeGridプロジェクトの参加者によって発見されました。
素数ページでは、現在の上位20個の一般化フェルマー素数と上位100個の一般化フェルマー素数を見つけることができます。
