フェルマー数に関する定理

2016/12/10 高校範囲を超える定理など

この記事の所要時間：約 8分11秒

フェルマー数に関する定理

フェルマーの最終定理やフェルマーの小定理にも名前を残している数学者, フェルマーの名前がついた数, フェルマー数というものがあります. ここでは, フェルマー数の定理で重要なものの一つを紹介します.

フェルマー数とは

フェルマー数とは, 自然数 $n$ に対して,

$\begin{equation*} F_n = 2^{2^n}+1 \end{equation*}$

と表される数です.

具体的に計算すると,

$\begin{eqnarray*} F_1 &=& 2^{2^1}+1 = 5\\ F_2 &=& 2^{2^2}+1 = 17\\ F_3 &=& 2^{2^3}+1 = 257\\ &\vdots& \end{eqnarray*}$

と小さい $n$ に対しても $F_n$ はどんどん大きな数になっていきます.

フェルマーはこの $F_n$ がすべて素数であると予想したのですが, 実際には

$F_5 = 641 \times 6700417$

という反例をオイラーが見つけました.

一方, 後に「 $p$ :素数として, 正 $p$ 角形がコンパスと定規のみで作図可能であるのは, $p$ がフェルマー数のときのみ」ということがガウスにより証明されました.

定理

ここでは, フェルマー数に関する定理を紹介します.

定理.

フェルマー数 $F_n$ が素数 $p$ を約数にもつとき,

$\begin{equation*} p\equiv 1 \pmod{2^{n+1}} \end{equation*}$

が成り立つ.

(合同式に関してはこちら. )

ここでは, $F_n$ 自身が素数 $p$ になっている場合も含めて考えてかまいません.

定理の証明の前に, まず補題を証明します.

補題1.

補題.

自然数 $a, m$ に対して, $a^k\equiv 1 \pmod{m}$ を満たす最小の自然数 $k$ を, 法 $m$ に関する $a$ の位数と呼び, $e$ と表記することにする.

このとき,

自然数 $k$ が $a^k\equiv 1 \pmod{m}$ を満たす

⇔ $k$ は位数 $e$ を約数にもつ.

(証明)

・(⇒)

自然数 $k$ が $a^k\equiv 1\pmod(m)$ を満たすとき, 位数 $e$ の定義により,

$\begin{equation*} k \geqq e \end{equation*}$

$k$ を $e$ で割った商を $s$ , 余りを $t$ とおくと, ( $s, t$ は整数で $s\geqq 1, 0\leqq t\leqq e$ )

$\begin{equation*} k = se + t \end{equation*}$

(以下では合同式の法はすべて $m$ とします. )

$a^k\equiv 1$ より, $a^{se+t}\equiv 1$ .

(1) $\begin{equation*} \therefore (a^e)^s\cdot a^t\equiv 1 \end{equation*}$

一方, $a^e\equiv 1$ を用いると

(2) $\begin{eqnarray*} (a^e)^s\cdot a^t &\equiv& 1^s\cdot a^t\\ &\equiv& a^t \end{eqnarray*}$

(1), (2) より, $a^t\equiv 1$ .

ここで $t\neq 0$ とすると, $t$ は自然数で $t<e$ なので, $e$ の定義に矛盾します.

よって, $t = 0$ , つまり $k=se$ となり $k$ は $e$ を約数にもつ.

・(⇐)

$k$ が $e$ を約数にもつので, $k = se$ ( $s$ :自然数) とおけて,

$\begin{eqnarray*} a^k &=& a^{se}\\ &=& (a^e)^s\\ &\equiv& 1^s\\ &=& 1 \end{eqnarray*}$

定理の証明.

・証明の流れ

法 $p$ に関する $2$ の位数 $e$ が $2^{n+1}$ の約数であることを示す.
$e=2^{n+1}$ を背理法で示す. (背理法の中で帰納法を使う)
フェルマーの小定理を利用して定理を導く.

・証明

$F_n = 2^{2^n}+1$ が $p$ の倍数より,

$\begin{equation*} 2^{2^n}+1\equiv 1\pmod{p} \end{equation*}$

(以下では, 合同式の法が $p$ のときは表記を省略します. )

ここから式変形して,

$\begin{eqnarray*} (\ast)\,\,\,\,2^{2^n}&\equiv& -1\\ \left(2^{2^n}\right)^2 &\equiv& (-1)^2\\ \therefore 2^{2^{n+1}} &\equiv& 1 \end{eqnarray*}$

法 $p$ に関する $2$ の位数を $e$ とすると, (補題1) により,

$2^{n+1}$ は $e$ を約数にもつので,

$e$ は $2^0, 2^1, \ldots, 2^{n+1}$ のいずれかになります.

そこで, 背理法を使って, $e = 2^{n+1}$ であることを示していきます.

$e = 2^i$ , ( $i$ は自然数で $0\leqq e\leqq n$ ) と仮定します. (つまり, $e$ が $2^{n+1}$ でないと仮定します. )

つまり,

$\begin{equation*} 2^{2^{i}}\equiv 1 \end{equation*}$

このとき,

「 $j\geqq i$ を満たす自然数 $j$ について $2^{2^j}\equiv 1$ が成り立つ」

ことを帰納法で示します.

[1] $j=i$ のときは明らか.

[2] $j=k$ で成り立つと仮定すると,

$\begin{equation*} 2^{2^k}\equiv 1 \end{equation*}$

$j = k+1$ のとき,

$\begin{eqnarray*} 2^{2^{k+1}} &=& 2^{2^k\cdot 2}\\ &=& (2^{2^k})^2\\ &\equiv& 1^2\\ &\equiv& 1 \end{eqnarray*}$

より成り立つ.

[1], [2] より, $j\geqq i\Rightarrow 2^{2^j}\equiv 1$ .

ここで, $n\geqq i$ の仮定から, $2^{2^n}\equiv 1$ .

一方で,

はじめに出て来た式 $(\ast)$ は

$\begin{equation*} (\ast)\,\,\,\,2^{2^n}\equiv -1 \end{equation*}$

なので,

$\begin{equation*} 1\equiv -1 \pmod{p} \end{equation*}$

ところが, $p$ は素数で, $F_n = 2^{2^n}+1$ (奇数) の約数より $p$ は奇数なので, 上の式を満たさない. よって, 矛盾が生じたので, 背理法の仮定が誤りで, 位数 $e$ は

$\begin{equation*} e = 2^{2^{n+1}} \end{equation*}$

ここで, Fermat の小定理より

$\begin{equation*} 2^{p-1} \equiv 1 \end{equation*}$

が成り立ち, (補題)により, $p-1$ は $e$ の倍数.

つまり,

$\begin{eqnarray*} p-1 $\equiv$ 0 \pmod{e}\\ \therefore p&\equiv& 1 \pmod{2^{n+1}} \end{eqnarray*}$

関連

スポンサーリンク

フェルマー数黒猫の三角