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

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

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

 

フェルマー数とは

フェルマー数とは, 自然数 \(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\) になっている場合も含めて考えてかまいません.

 

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

 

補題1.

(証明)

・(⇒)

自然数 \(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\) は自然数で \(t<e\) なので, \(e\) の定義に矛盾します.

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

 

・(⇐)

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

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

 

 

定理の証明.

・証明の流れ

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

・証明

\(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*}