数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

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

定義・定理・公式

スポンサードリンク

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

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

フェルマー数とは

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

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

と表される数です.

具体的に計算すると,

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

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

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

$F_5 = 641 \times 6700417$

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

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

定理

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

定理.

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

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

が成り立つ.

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

ここでは, $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{align*}
k \geqq e
\end{align*}

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

\begin{align*}
k = se + t
\end{align*}

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

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

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

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

\begin{align}
(a^e)^s\cdot a^t &\equiv 1^s\cdot a^t\\
&\equiv a^t
\end{align}

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

ここで $t\neq 0$ とすると, $t$ は自然数で [tex: t定理の証明.

・証明の流れ

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

・証明

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

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

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

ここから式変形して,

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

法 $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{align*}
2^{2^{i}}\equiv 1
\end{align*}

このとき,

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

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

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

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

\begin{align*}
2^{2^k}\equiv 1
\end{align*}

$j = k+1$ のとき,

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

より成り立つ.

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

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

一方で,

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

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

なので,

\begin{align*}
1\equiv -1 \pmod{p}
\end{align*}

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

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

ここで, Fermat の小定理より

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

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

つまり,

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