フェルマー数に関する定理
フェルマーの最終定理やフェルマーの小定理にも名前を残している数学者, フェルマーの名前がついた数, フェルマー数というものがあります. ここでは, フェルマー数の定理で重要なものの一つを紹介します.
フェルマー数とは
フェルマー数とは, 自然数 \(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\) は自然数で \(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*}
定理の証明.
・証明の流れ
- 法 \(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*}