Fermat数
概要
Fermat数（Fermat number）とは、$0$ 以上の整数 $n$ に対する $F_n=2^{2^n}+1$ の形の数のことである。$F_0,\dots,F_4$（$3,5,17,257,65537$）は素数だが $F_5=641\cdot6700417$ は合成数であり、すべて素数だという Fermat の予想は Euler が否定した。$2^m+1$（$m\geq1$）が素数なら $m$ は $2$ の冪であり、Fermat 数どうしは $F_0\cdots F_{n-1}=F_n-2$ から互いに素である。$F_n$ の素因数は $2^{n+1}$ で割って $1$ 余り、$n\geq1$ のとき $F_n$ が素数かどうかは Pépin の判定法で決まる。Fermat 素数は作図できる正多角形の角数を決める。$F_4$ より後の Fermat 素数は未発見である。
前提知識: 素数, 合同式, 互いに素, 元の位数, Fermatの小定理, 平方剰余
$2$ から始めて 2 乗を繰り返すと $2,4,16,256,65536,\dots$ となる。それぞれに $1$ を足した
$$
3,\quad 5,\quad 17,\quad 257,\quad 65537
$$
はどれも素数である。Fermat は 1640 年の手紙で、この形の数はすべて素数だろうと述べた（証明はないと認めている）。ところが次の $2^{32}+1=4294967297$ は $641$ で割り切れ、$4294967297=641\cdot6700417$ となることを 1732 年に Euler が見つけた（Dic19 Chapter XV, p. 375）。その後、この形の数で素数と分かったものは一つもなく、2026 年初めの時点で、6 番目から 33 番目までの $2^{2^5}+1,\dots,2^{2^{32}}+1$ はすべて合成数と分かっている。$2^{2^n}+1$ の形の数を Fermat 数という。素数にはならなかったが、Fermat 数どうしは $1$ 以外の共通の約数をもたないこと（互いに素であること）、素因数の形が強く制限されること、正 $17$ 角形のように定規とコンパスで作図できる正多角形の角数を決めることなど、豊かな性質をもつ。
定義
$0$ 以上の整数 $n$ に対し
$$
F_n:=2^{2^n}+1
$$
を $n$ 番目の Fermat 数（Fermat number）という。$F_n$ が素数であるとき、$F_n$ を Fermat 素数（Fermat prime）という。
番号は $n=0$ から数える。$F_0=3$、$F_1=5$、$F_2=17$、$F_3=257$、$F_4=65537$、$F_5=4294967297$ である。Fermat 数はすべて奇数であり、$F_{n+1}=(F_n-1)^2+1$ という関係で次々に定まる。
直感
Fermat 数は「$2^m+1$ が素数になりうる $m$」だけを集めたものである。$m$ が $3$ 以上の奇数 $d$ で割り切れると $2^m+1$ は $2^{m/d}+1$ で割り切れてしまうので（prop-fermat-number-power-of-two）、$m$ は $2$ の冪でなければならない。Fermat 数どうしは $F_0F_1\cdots F_{n-1}=F_n-2$ という積の関係で結ばれており（prop-fermat-number-product）、このため 2 つの Fermat 数は共通の素因数をもたない。一方、$F_n$ の素因数 $q$ では $2$ の位数がちょうど $2^{n+1}$ になるので、$q-1$ は大きな $2$ の冪で割り切れる。素因数の候補がこのように限られることが、Euler が $641$ を見つけられた理由である。
例と反例
$$
\begin{array}{c|l}
n & F_n\\ \hline
0 & 3\\
1 & 5\\
2 & 17\\
3 & 257\\
4 & 65537\\
5 & 4294967297=641\cdot6700417\\
6 & 18446744073709551617=274177\cdot67280421310721
\end{array}
$$
$F_0,\dots,F_4$ は素数であり、$F_5,F_6$ は合成数である。$n\geq2$ のとき $F_n$ の一の位は $7$ である。実際 $n\geq2$ なら $2^{2^n}=16^{2^{n-2}}$ であり、一の位が $6$ の数どうしの積の一の位は $6$ なので、$2^{2^n}$ の一の位は $6$、$F_n$ の一の位は $7$ である。
$F_5$ は素数でない。これは次のように暗算に近い形で確かめられる。$641$ には
$$
641=5\cdot2^7+1=5^4+2^4
$$
という 2 通りの表し方がある。1 つ目から $5\cdot2^7\equiv-1\pmod{641}$、2 つ目から $2^4\equiv-5^4\pmod{641}$ である。よって
$$
2^{32}=2^4\cdot2^{28}\equiv-5^4\cdot2^{28}=-(5\cdot2^7)^4\equiv-(-1)^4=-1\pmod{641}
$$
となり、$641\mid2^{32}+1=F_5$ である。満たす性質は「$F_0,\dots,F_4$ が素数」、満たさない性質は「$F_5$ が素数」であり、破る含意は Fermat の予想「すべての $F_n$ は素数」である。
$2^m+1$ で $m$ が $2$ の冪でないと、合成数になる。
$$
2^3+1=9=3\cdot3,\qquad 2^6+1=65=5\cdot13,\qquad 2^{10}+1=1025=5^2\cdot41,\qquad 2^{12}+1=4097=17\cdot241.
$$
$m=6=2\cdot3$ では $2^2+1=5$ が、$m=12=4\cdot3$ では $2^4+1=17$ が約数になっている。これは prop-fermat-number-power-of-two の証明で使う因数分解の表れである。
性質
2 の冪の指数
$m$ を正の整数とする。$2^m+1$ が素数ならば、$m$ は $2$ の冪であり、したがって $2^m+1$ は Fermat 数である。
$m$ が $2$ の冪でないとすると、$m=2^u d$（$u\geq0$、$d\geq3$ は奇数）と書ける。$x:=2^{2^u}$ とおくと、$d$ が奇数なので
$$
2^m+1=x^d+1=(x+1)(x^{d-1}-x^{d-2}+\dots-x+1)
$$
である（右辺を展開すると隣り合う項が打ち消し合う）。$x\geq2$ から $x+1\geq3$ であり、$d\geq3$ から $x+1< x^d+1$ である。よって $2^m+1$ は $1$ でも自身でもない約数 $x+1$ をもち、素数でない。対偶を取れば主張を得る。$\square$
$m=0$ の $2^0+1=2$ は素数だが Fermat 数ではない。この命題により、$2^m+1$（$m\geq1$）の形の素数はちょうど Fermat 素数である。同じ因数分解は 作図可能数 の記事の定理「Gauss–Wantzel の定理」の証明でも使われている。
積の公式と互いに素であること
すべての $n\geq1$ について
$$
F_0F_1\cdots F_{n-1}=F_n-2
$$
が成り立つ。
$n$ に関する数学的帰納法で示す。$n=1$ では $F_0=3=5-2=F_1-2$ である。$n$ で成り立つとすると、
$$
F_0\cdots F_{n-1}F_n=(F_n-2)F_n=(2^{2^n}-1)(2^{2^n}+1)=2^{2^{n+1}}-1=F_{n+1}-2
$$
となり、$n+1$ でも成り立つ。$\square$
$F_n-2=2^{2^n}-1$ は Mersenne素数 の記事の Mersenne 数 $M_{2^n}$ にほかならない。この命題は、$M_{2^n}$ が $F_0,\dots,F_{n-1}$ の積に分解されることを述べている。たとえば $2^{16}-1=65535=3\cdot5\cdot17\cdot257$ である。
$m\neq n$ ならば $F_m$ と $F_n$ は互いに素である。
$m< n$ としてよい。$d$ を $F_m$ と $F_n$ の正の公約数とする。prop-fermat-number-product により $F_m$ は $F_n-2$ を割るので、$d$ は $F_n-2$ と $F_n$ の両方を割り、したがって $F_n-(F_n-2)=2$ を割る。Fermat 数は奇数なので $d$ も奇数であり、$d=1$ である。$\square$
この系は Mos11 の Miscellaneous Problems 第 39 問（p. 77）に演習として挙がっている。
素数は無限に存在する。より詳しく、小さい順に $k$ 番目の素数を $p_k$ とすると、すべての $n\geq0$ について $p_{n+1}\leq F_n=2^{2^n}+1$ である。
$n\geq0$ を固定する。$F_0,F_1,\dots,F_n$ はいずれも $2$ 以上なので、それぞれ素因数をもつ（素数 の記事の命題「素因数の存在」）。$F_k$ の最小の素因数を $q_k$ とすると、cor-fermat-number-coprime により $q_0,\dots,q_n$ は相異なる。これらはすべて $F_n$ 以下である（$q_k\leq F_k\leq F_n$）。よって $F_n$ 以下に少なくとも $n+1$ 個の素数があり、$p_{n+1}\leq F_n$ である。$n$ はいくらでも大きく取れるので、素数は無限に存在する。$\square$
この証明は Goldbach が 1730 年ごろ Euler への手紙で述べた観察（2 つの Fermat 数は共通の因子をもたない）に基づく（Dic19 Chapter XV, p. 375）。素数の無限性 の証明のうち、Euclid の証明とは違って、互いに素な数の無限列を 1 つ具体的に与えるものである（Cla Chapter 10, §1.2, p. 133, Theorem 10.4、Cri24 Proposition 12.1.4, pp. 185–187）。
素因数の形
$n\geq0$ とし、素数 $q$ が $F_n$ を割るとする。
- $q\equiv1\pmod{2^{n+1}}$ である。
- $n\geq2$ ならば $q\equiv1\pmod{2^{n+2}}$ である。
$F_n$ は奇数なので $q$ は奇素数である。$q\mid F_n$ から
$$
2^{2^n}\equiv-1\pmod q,\qquad 2^{2^{n+1}}=\left(2^{2^n}\right)^2\equiv1\pmod q
$$
である。$q$ を法とする $2$ の位数を $d:=\operatorname{ord}_q(2)$ とする。Fermatの小定理 の記事の命題「位数は p−1 を割る」により、$2^k\equiv1\pmod q$ であることと $d\mid k$ であることは同値であり、$d\mid q-1$ である。$2^{2^{n+1}}\equiv1$ なので $d\mid2^{n+1}$、すなわち $d=2^j$（$0\leq j\leq n+1$）である。$j\leq n$ なら $d\mid2^n$ なので $2^{2^n}\equiv1$ となり、$-1\equiv1$、すなわち $q\mid2$ となって $q$ が奇数であることに反する。よって $d=2^{n+1}$ であり、$2^{n+1}\mid q-1$ である。これが 1 である。
2 を示す。$n\geq2$ なら 1 により $8\mid2^{n+1}\mid q-1$ なので $q\equiv1\pmod8$ である。平方剰余 の記事の定理「第2補充法則と相互法則」の 1 により $2$ は $q$ を法とする平方剰余であり、同じ記事の定理「Eulerの規準」により $2^{(q-1)/2}\equiv1\pmod q$ である。よって $d=2^{n+1}$ は $(q-1)/2$ を割り、$2^{n+2}\mid q-1$ を得る。$\square$
1 は Euler が、2 は Lucas が示した（Dic19 Chapter XV, pp. 375–376）。$n=0,1$ では 2 は成り立たない。$F_0=3$ の素因数 $3$ は $3\not\equiv1\pmod4$ であり、$F_1=5$ の素因数 $5$ は $5\not\equiv1\pmod8$ である。
$F_5=2^{32}+1$ の素因数は、prop-fermat-number-factor-form の 2 により $2^7=128$ で割って $1$ 余る素数に限られる。$128k+1$ の形の数を小さい順に見ると、$129=3\cdot43$、$257$（素数）、$385=5\cdot7\cdot11$、$513=3^3\cdot19$、$641$（素数）である。$257=F_3$ は cor-fermat-number-coprime により $F_5$ を割らない。次の候補 $641$ が実際に $F_5$ を割る（ex-fermat-number-641）。1 の条件（$64$ で割って $1$ 余る）だけを使っても、$641$ は $64k+1$ の形の素数のうち小さい方から 5 番目（$193,257,449,577,641$）である。Euler は 1 を示したあとで、この条件から $641$ が $k=10$ の候補として見つかることを注意している（Dic19 Chapter XV, p. 375）。
同様に $F_6$ の素因数 $274177=1071\cdot2^8+1$ と $67280421310721$ は、どちらも $2^8=256$ で割って $1$ 余る。
Pépinの判定法
$n\geq1$ とする。$F_n$ が素数であることと
$$
3^{(F_n-1)/2}\equiv-1\pmod{F_n}
$$
であることは同値である。
$F:=F_n$ とおく。$F-1=2^{2^n}$ であり、$n\geq1$ なので $2^n\geq2$、$4\mid F-1$ である。
($\Rightarrow$) $F$ が素数であるとする。$2^{2^n}=4^{2^{n-1}}\equiv1\pmod3$ なので $F\equiv2\pmod3$ であり、特に $F\neq3$、$3\nmid F$ である。$F\equiv1\pmod4$ なので、平方剰余 の記事の定理「第2補充法則と相互法則」の 2（平方剰余の相互法則）により
$$
\left(\frac{3}{F}\right)=\left(\frac{F}{3}\right)=\left(\frac{2}{3}\right)=-1
$$
である。最後の等号は、$3$ を法とする $0$ でない平方数の余りが $1^2\equiv2^2\equiv1$ だけで $2$ が現れないことによる。同じ記事の定理「Eulerの規準」により $3^{(F-1)/2}\equiv\left(\frac{3}{F}\right)=-1\pmod F$ である。
($\Leftarrow$) $3^{(F-1)/2}\equiv-1\pmod F$ とする。$F\mid 3^{(F-1)/2}+1$ なので、$3\mid F$ なら $3\mid 3^{(F-1)/2}+1$ となり、$3\mid1$ となって矛盾する。よって $\gcd(3,F)=1$ である。両辺を 2 乗して $3^{F-1}\equiv1\pmod F$ となる。$F$ を法とする $3$ の位数（$3^k\equiv1\pmod F$ となる最小の正の整数 $k$）を $d$ とする。これは $F$ と互いに素な剰余類のなす群 $(\mathbb{Z}/F\mathbb{Z})^{\times}$ における $3$ の類の元の位数であり、$3^k\equiv1$ と $d\mid k$ は同値である（元の位数 の記事の命題「位数と冪の整除関係」）。$d\mid F-1=2^{2^n}$ なので $d$ は $2$ の冪である。$d\neq F-1$ なら $d\mid(F-1)/2$ となり $3^{(F-1)/2}\equiv1$、すなわち $-1\equiv1\pmod F$ となって $F\mid2$ に反する。よって $d=F-1$ である。
このとき $3^1,3^2,\dots,3^{F-1}$ を $F$ で割った余りは相異なる（$3^i\equiv3^j$、$1\leq i< j\leq F-1$ なら $3^{j-i}\equiv1$ で $0< j-i< d$ となり $d$ の最小性に反する）。どの余りも $F$ と互いに素で、$0$ ではない。したがってこれらの $F-1$ 個の余りは $1,2,\dots,F-1$ のすべてであり、$1,\dots,F-1$ はすべて $F$ と互いに素である。これは $F$ が $1$ と自身以外に正の約数をもたないこと、すなわち $F$ が素数であることを意味する。$\square$
$F_1=5$ では $3^{2}=9\equiv-1\pmod5$、$F_2=17$ では $3^2=9$、$3^4=81\equiv13$、$3^8\equiv13^2=169\equiv-1\pmod{17}$ であり、どちらも素数と判定される。$F_4=65537$ でも $3^{32768}\equiv-1\pmod{65537}$ となる。$F_5=4294967297$ では $3^{2^{31}}$ を $F_5$ で割った余りは $10324303$ であって $-1\equiv4294967296$ ではないので、$F_5$ は合成数と判定される。この判定は $641$ という約数を見つけずに合成数であることを示す。
$n=0$ では判定法は使えない。$F_0=3$ は素数だが $3^{1}\equiv0\not\equiv-1\pmod3$ である。prop-fermat-number-pepin の仮定 $n\geq1$ はこの場合を除くためのものである。
Pépin が 1877 年に与えた判定法は、$3$ の代わりに $5$ など $F_n$ を法とする平方非剰余を使う形であった。$3$ を使う形は 1878 年に Proth が述べ、Lucas はそれが Pépin の判定法で平方非剰余に $3$ を取った場合であることを注意した（Dic19 Chapter XV, pp. 376–377）。$3$ を使う形の証明は Cri24 Fact 17.5.1（§17.5.2, pp. 306–307）にもある。
正多角形の作図
Gauss は、正 $17$ 角形が定規とコンパスで作図できることを示し、作図できる正多角形の角数を Fermat 素数を用いて述べた（Dic19 Chapter XV, p. 375）。現在の形では、作図可能数 の記事の定理「Gauss–Wantzel の定理」により、$n\geq3$ について正 $n$ 角形が作図可能であることは、
$$
n=2^kp_1p_2\cdots p_s\qquad(k\geq0,\ s\geq0)
$$
で $p_1,\dots,p_s$ が相異なる Fermat 素数であることと同値である。たとえば $17=F_2$ なので正 $17$ 角形は作図でき、$7$ は Fermat 素数でないので正 $7$ 角形は作図できない。$9=3^2$ は同じ Fermat 素数 $3$ を 2 回含むので、正 $9$ 角形も作図できない。知られている Fermat 素数は $3,5,17,257,65537$ の 5 個だけなので、作図できると分かっている奇数角の正多角形は、これらのうち相異なるものの積を角数とする 31 種類である。
補足
Fermat は 1640 年の Frenicle 宛ての手紙などで、すべての $F_n$ が素数だと信じていると述べたが、証明はもっていないと認めていた（Dic19 Chapter XV, p. 375）。$F_5$ の約数 $641$ を見つけたのは Euler（1732 年）である。
Fermat 素数が無限に存在するかどうか（Mos11 Classical Unsolved Problems 第 10 問、p. 73）は未解決であり、$F_4=65537$ より後に 1 つでも存在するかどうかも知られていない。Keller の集計（2025 年 12 月時点）では、$5\leq n\leq32$ のすべての $F_n$ が合成数であり、$F_{33}$ が素数か合成数かは分かっていない。このうち $F_{20}$（1987 年、Buell と Young）と $F_{24}$（1999 年、Mayer・Papadopoulos・Crandall）は、Pépin の判定法などで合成数と示されているが、素因数は 1 つも知られていない（Kel25、この一覧に依拠する形で Cow26 も同じ内容を整理している）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
