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

この記事の所要時間: 811

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

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

フェルマー数とは

フェルマー数とは, 自然数 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 と表記することにする.

このとき,

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

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

(証明)

・(⇒)

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

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

ke で割った商を 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 となり ke を約数にもつ.

・(⇐)

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

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

定理の証明.

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

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

\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 を約数にもつので,

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

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

e = 2^i, (i は自然数で 0\leqq e\leqq n) と仮定します. (つまり, e2^{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-1e の倍数.

つまり,

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

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加