Fermat数

$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$ $\newcommand{\relmid}[1]{\mathrel{}\middle|\mathrel{}}$

$m$ を 正の整数とする。$2^m+1$ が素数ならば $m=2^n$ は $2$ の累乗である。 実際 $m$ が $3$ 以上の奇数 $d$ で割り切れるとき、$m=dt$ とおくと $$2^m+1=(2^t+1)(2^{t(d-1)}-2^{t(d-2)}+\cdots -2^t+1)$$ となって、$(2^t+1)\mid (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, \ldots$$ 形の数をFermat数という。

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

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

定理 1

$n\geq 1$ のとき $F_n\equiv 2\mathmod{3}$. $n\geq 2$ のとき $F_n\equiv 2\mathmod{5}$ かつ $F_n\equiv 1\mathmod{16}$.

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

Proof.

$n\geq 1$ のとき $x=2^{2^{n-1}}$ とおくと $x$ は $3$ で割り切れないから $$F_n=x^2+1\equiv 2\mathmod{3}$$ となる。 また、$n\geq 2$ のとき $y=2^{2^{n-2}}$ とおくと $y$ は $5$ で割り切れないから $$F_n=y^4+1\equiv 2\mathmod{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はつぎの定理を示した。

定理 2

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

Proof.

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

□

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

定理 3

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

Proof.

$p$ を $F_n$ の素因数とする。 $$2^{2^n}\equiv -1\not\equiv 1\mathmod{p}$$ となる。両辺を$2$乗し、 $$2^{2^{n+1}}\equiv 1\mathmod{p}$$ となるから、$2\mathmod{p}$ の乗法的位数は $2^{n+1}$ に一致する。よって、まずは $p\equiv 1\mathmod{2^{n+1}}$ が成り立つことがわかる。 $n\geq 2$ なので、$p\equiv 1\mathmod{8}$ であるから、第2補充法則より $$\left(\frac{2}{p}\right)=1$$ となる。このことから平方剰余:定理1.2より $$2^{(p-1)/2}\equiv \left(\frac{2}{p}\right)=1\mathmod{p}$$ となるが、$2\mathmod{p}$ の乗法的位数は $2^{n+1}$ に一致するから、$2^{n+1}$ は $(p-1)/2$ を割り切る。 つまり $p-1$ は $2^{n+2}$ で割り切れる。

□

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

定理 4 (Pepinの判定法)

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

• $(1)$ $F_n$ が素数で、かつ $(k/F_n)=-1$.
• $(2)$ $k^{(F_n-1)/2}\equiv -1\mathmod{F_n}$.

Proof.

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

□

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

参考文献

Fermat数に関する初期の歴史については

• Leonard Eugene Dickson, History of the Theory of Numbers, volume I, Divisibility and Primality, Carnegie Institution of Washington, 1919, Chapter XV, p.p.375--380, Integet Archive

を参考とした。またFermat数の基本的な性質については

• Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, Section 2.VI, p.p.83--90, doi:10.1007/978-1-4612-0759-7

を参考とした。

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