Fermat数

$m$ を正の整数とする。 $2^{m} + 1$ が素数ならば $m = 2^{n}$ は $2$ の累乗である。
実際 $m$ が $3$ 以上の奇数 $d$ で割り切れるとき、 $m = d t$ とおくと
$2^{m} + 1 = (2^{t} + 1) (2^{t (d - 1)} - 2^{t (d - 2)} + \dots - 2^{t} + 1)$
となって、 $(2^{t} + 1) ∣ (2^{m} + 1)$ かつ $2^{t} + 1 < 2^{m} + 1$ となるので、 $2^{m} + 1$ は合成数である。

一方、 $m = 2^{n}$ が $2$ の累乗のとき $2^{m} + 1 = 2^{2^{n}} + 1$ は $n = 0, 1, 2, 3, 4$ のとき素数となる。

このことからFermatはこの形の数はすべて素数であると予想したが、一方でその証明はできていないと述べた。
Mersenneもこの形の数はすべて素数であると予想した。しかし、Eulerは $n = 5$ のとき
$2^{2^{5}} + 1 = 2^{32} + 1 = 4294967297 = 641 \times 6700417$
は合成数であることを発見し、この形の数に関するFermatの予想は誤りであることを明らかにした。それで、
$F_{n} = 2^{2^{n}} + 1, n = 0, 1, \dots$
の形の数をFermat数 (Fermat number) という。

Fermat数の素因数と素数判定法

Fermat数について、つぎの合同式が成り立つことがすぐにわかる。

$n \geq 1$ のとき $F_{n} \equiv 2 (\mod 3)$ .
$n \geq 2$ のとき $F_{n} \equiv 2 (\mod 5)$ かつ $F_{n} \equiv 1 (\mod 16)$ .

とくに、 $n \geq 2$ のとき、Fermat数を $10$ 進展開したときの、 $1$ の位は必ず $7$ となる。

$n \geq 1$ のとき $x = 2^{2^{n - 1}}$ とおくと $x$ は $3$ で割り切れないから
$F_{n} = x^{2} + 1 \equiv 2 (\mod 3)$
となる。
また、 $n \geq 2$ のとき $y = 2^{2^{n - 2}}$ とおくと $y$ は $5$ で割り切れないから
$F_{n} = y^{4} + 1 \equiv 2 (\mod 5)$
となる。最後に、 $n \geq 2$ ならば $2^{n} \geq 4$ だから $F_{n} - 1 = 2^{2^{n}}$ は $2^{4} = 16$ で割り切れる。

EulerはFermat数 $F_{n}$ の素因数は $k \times 2^{n + 1} + 1$ の形のものであることを示した。より一般に、Eulerはつぎの定理を示した。

$a, b$ が互いに素な整数で、 $n$ が $0$ 以上の整数であるとき $a^{2^{n}} + b^{2^{n}}$ の素因数は $2$ かあるいは $k \times 2^{n + 1} + 1$ の形をしている。

$p$ を $a^{2^{n}} + b^{2^{n}}$ の奇数の素因数とする。 $p$ が $a$ の素因数ならば $a, b$ は互いに素だから $p$ は $b$ の素因数ではないので $a^{2^{n}} + b^{2^{n}}$ は $p$ で割り切れなくなる。よって $p$ は $a$ の素因数ではないので、合同式:定理5 より
$a x \equiv b (\mod p)$
となる $x (\mod p)$ が存在する。よって
$a^{2^{n}} (1 + x^{2^{n}}) \equiv 0 (\mod p)$
となるが、 $p$ は $a$ の素因数ではないので、 $p$ が奇数であることもあわせて
$x^{2^{n}} \equiv - 1 ≢ 1 (\mod p)$
となる。両辺を $2$ 乗し、
$x^{2^{n + 1}} \equiv 1 (\mod p)$
となるから、 $x (\mod p)$ の乗法的位数は $2^{n + 1}$ に一致する。乗法的位数:定理1 より $p - 1$ は $2^{n + 1}$ で割り切れる。

Fermat数に関しては、Lucasはやや強く、次の定理を示した。

$n$ が $2$ 以上の整数であるとき $F_{n}$ の素因数は $k \times 2^{n + 2} + 1$ の形をしている。

$p$ を $F_{n}$ の素因数とする。
$2^{2^{n}} \equiv - 1 ≢ 1 (\mod p)$
となる。両辺を $2$ 乗し、
$2^{2^{n + 1}} \equiv 1 (\mod p)$
となるから、 $2 (\mod p)$ の乗法的位数は $2^{n + 1}$ に一致する。よって、まずは
$p \equiv 1 (\mod 2^{n + 1})$ が成り立つことがわかる。

$n \geq 2$ なので、 $p \equiv 1 (\mod 8)$ であるから、平方剰余の第2補充法則より
$(\frac{2}{p}) = 1$
となる。このことから平方剰余:定理2 より
$2^{(p - 1) / 2} \equiv (\frac{2}{p}) = 1 (\mod p)$
となるが、 $2 (\mod p)$ の乗法的位数は $2^{n + 1}$ に一致するから、 $2^{n + 1}$ は $(p - 1) / 2$ を割り切る。
つまり $p - 1$ は $2^{n + 2}$ で割り切れる。

Fermat数が素数となるかどうかについては、Pepinの判定法が知られている。

Pepinの判定法

$k$ を $2$ 以上の整数とすると、次の $2$ 条件は同値。

$F_{n}$ が素数で、かつ $(k / F_{n}) = - 1$ .
$k^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n})$ .

$F_{n}$ が素数で、かつ $(k / F_{n}) = - 1$ ならば、平方剰余:定理2 より
$k^{(F_{n} - 1) / 2} \equiv (\frac{k}{F_{n}}) = - 1 (\mod F_{n})$
となって、2. が成り立つ。
逆に 2. が成り立つとすると、
$k^{F_{n} - 1} \equiv 1 (\mod F_{n})$
より、 $k (\mod F_{n})$ の乗法的位数は $F_{n} - 1 = 2^{2^{n}}$ に一致するから、乗法的位数:定理1 より
$F_{n} - 1$ は $φ (F_{n})$ を割り切る。つまり $φ (F_{n}) = F_{n} - 1$ となる。よって合同式:Eulerの定理で述べたことから、 $F_{n}$ は素数である。
またこのとき
$(\frac{k}{F_{n}}) = k^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n})$
も成り立つから 1. が成り立つ。

このことから、とくに $F_{n}$ が素数であることの必要十分条件は
$3^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n}), 5^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n}), 10^{(F_{n} - 1) / 2} \equiv - 1 (\mod F_{n})$
のいずれかが成り立つことであるとわかる。実際、定理1 から
$(\frac{3}{F_{n}}) = (\frac{F_{n}}{3}) = (\frac{2}{3}) = - 1,$
$(\frac{5}{F_{n}}) = (\frac{F_{n}}{5}) = (\frac{2}{5}) = - 1,$
および
$(\frac{10}{F_{n}}) = (\frac{2}{F_{n}}) (\frac{5}{F_{n}}) = (\frac{5}{F_{n}}) = - 1$
となることがわかる。

参考

Fermat数に関する初期の歴史については Dic の第15章、p.p.375--380を参照。Fermat数の基本的な性質については Rib の 2.6節、p.p. 83--90 を参照。

Fermat数の素数判定および素因数分解については
FERMATSEARCH.ORG, Distributed Search for Fermat Number Divisors
に詳しく記述されており、既知のFermat素数およびFermat数の素因数分解の一覧のみであれば
Proth Search Page, Fermat factoring status
に記載されている。

参考文献

[1]

G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th Ed., Oxford University Press, 2008

[2]

G. H. Hardy and E. M. Wright, 訳: 示野信一、矢神毅, 数論入門I 原書6版, 数学クラシックス, 丸善出版, 2022

[3]

G. H. Hardy and E. M. Wright, 訳: 示野信一、矢神毅, 数論入門II 原書6版, 数学クラシックス, 丸善出版, 2022

[4]

J. C. Morehead, Factors of Fermat's numbers, Bull. Amer. Math. Soc., 1906, 449

[5]

D. P. Parent, Exercises in Number Theory, Springer-Verlag, 1984

[6]

Trygve Nagell, Introduction to Number Theory, Reprint Edition, American Mathematical Society (original: John Wiler & Sons, Inc.), 2001

[7]

Paulo Ribenboim, The New Book of Prime Number Records (3rd ed. pbk.), Springer, 2013