tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

フェルマー数を使った素数の無限性の証明

今日は数論の話をしましょう。

今回の主役は フェルマー数 です。フェルマー数とは、0以上の整数  n に対して

 F_n = 2^{2^n} + 1 \tag{1}

の形をした数のことです。

 F_n が自然に現れる問題としては 正多角形の作図 がよく知られています。 p を素数として、正  p 角形が作図可能である必要十分条件が知られています。その条件は「素数  p がフェルマー数であること」です。フェルマー数の形をした素数をフェルマー素数といいます。

宣伝です!!

フェルマー素数と作図の関係についての解説は、tsujimotterのノートブックの過去の記事でも紹介しています:
tsujimotter.hatenablog.com

また、私の執筆した数理科学の記事(2017年12月号)でも、丁寧に紹介しています。よろしければご覧ください。

数理科学 2017年 12 月号 [雑誌]

数理科学 2017年 12 月号 [雑誌]

  • 発売日: 2017/11/20
  • メディア: 雑誌

最初の5つのフェルマー数

 F_0 = 3
 F_1 = 5
 F_2 = 17
 F_3 = 257
 F_4 = 65537

を観察すると、これがすべて素数となることに気づきます。

フェルマー数の由来となった数学者フェルマーは、フェルマー数が素数ばかりであることに驚き、この先も素数が続くことを予想していたようです。

ところが、すぐ次のフェルマー数は素数ではありません。

 F_5 = 4294967297 = 641 \times 6700417

もっというと、この先フェルマー素数は一つも見つかっていません。2020年2月現在、307個のフェルマー数が合成数であることが調べられています。フェルマー数の列の中に、6個目もフェルマー素数を見つける試みは、大変難しいことがわかります。


今紹介したフェルマー数を使うと、なんと 素数の無限性の別証明 が得られるのです。今日はその方法を紹介したいと思います。

フェルマー数から素数の無限性が得られると聞いて、ぱっと頭に浮かぶのは「フェルマー素数の無限性」を示すという方針でしょう。フェルマー素数が無限にあることが示せれば、当然素数も無限にあるというわけです。

フェルマー素数の無限性  \;\; \Longrightarrow \;\; 素数の無限性

しかしながら、フェルマー素数の無限性を示すのはとても困難です。そもそも「~〜素数の無限性」を示すこと自体、とても難しい問題です。ほとんどの場合(たとえば「フィボナッチ素数の無限性」「メルセンヌ素数の無限性」「双子素数の無限性」など)が未解決問題で、うまくいっているのは「 an + b 型素数の無限性(算術級数定理)」ぐらいです。

もっと違ったアプローチが必要というわけですね。


フェルマー数の漸化式

フェルマー数は  2^{2^n} + 1 と表せますが、 2^{2^n} (2^{2^{n-1}})^2 であることに注意しましょう。

私もよくこんがらがるので、丁寧に計算してみましょう。
 \begin{array}{ll}
(2^{2^{n-1}})^2 & \\
= 2^{2^{n-1} \times 2} & \left(\because (a^b)^c = a^{b\times c}\right) \\ 
= 2^{2^n} & \left(\because 2^{n-1} \times 2 = 2^n\right)  
\end{array}

よって、 2^{2^n} + 1 は「(二乗)+(二乗)」の形をしていることがわかります。

「(二乗)ー(二乗)」であれば、因数分解の公式がありましたので、これを使いたいというのが最初の発想です。

 F_n - 2 = 2^{2^n} - 1 = (2^{2^{n-1}} + 1)(2^{2^{n-1}} - 1) = F_{n-1}(F_{n-1} - 2)

よって次の漸化式が得られました。

 F_n - 2 = F_{n-1}(F_{n-1} - 2) \tag{2}

 n 番目のフェルマー数は  n-1 番目から計算できるのですね!


右辺を見ると、 F_{n-1} - 2 という因子があります。ここにもう一度式  (2) を適用できるでしょう。

 \begin{align} F_n - 2 &= F_{n-1}(F_{n-1} - 2) \\ 
&= F_{n-1}F_{n-2}(F_{n-2} - 2) 
\end{align}

これを繰り返していくと、次の式が得られます:

 F_n - 2 = F_{n-1}F_{n-2}\cdots F_2F_1F_0(F_{0} - 2) \tag{3}


 F_0 = 2^{2^0} + 1 = 3 より、以下の式が得られます:

命題1: フェルマー数の漸化式
 F_n = \begin{cases} F_{n-1}F_{n-2}\cdots F_2F_1F_0 + 2 & (n \geq 1) \\ 3 & (n = 0) \end{cases} \tag{4}

とても綺麗な式になりました!

フェルマー数の定義から、こんな式が得られるというのは面白いです。

すべてのフェルマー数は互いに素

上の式  (4) を使うと、次の事実が分かります。

命題2: フェルマー数は互いに素
相異なる 0 以上の整数  n, m に対して、 F_n F_m は互いに素。

これを証明しましょう。

 n, m の大小関係を入れ替えても一般性を失わないので、 n > m としておきます。フェルマー数の漸化式より

 F_n = F_{n-1} \cdots F_m \cdots F_0 + 2 \tag{5}

が成り立ちます。

ここで、 F_n, F_m を割り切る共通の素数が存在すると仮定して、それを  q とします。このとき、式  (5) の左辺と右辺の第1項を  q が割り切ります。

f:id:tsujimotter:20200212195101p:plain:w380

したがって、 q 2 を割り切るはずなので、 q = 2 です。

一方、 F_n, F_m は定義から直ちに奇数であることが分かるので、 2 を素因数に持つはずがありません。したがって、「 F_n, F_m を割り切る共通の素数が存在する」という仮定が誤りであることがわかり、 F_n, F_m は互いに素であることが示されました。■


よって、すべてのフェルマー数は互いに素です。ここから素数の無限性が鮮やかに導かれます!

素数の無限性の証明

フェルマー数  F_n は 1 より大きいので、必ず素因子を持ちます。その素因子の一つを選んで  q_n とします。これを  n = 0 から順に行い、 F_n を割り切る素数の列

 q_0, q_1, q_2, q_3, \ldots, q_{n-1}, q_n

を得ます。

ここで、すべてのフェルマー数は互いに素であることを使うと、 q_n q_0, q_1, q_2, q_3, \ldots, q_{n-1} のいずれとも一致しません。

すなわち、与えられた  n-1 個の素数から、新しい素数を一つ見出すことができました。フェルマー数は無限に存在するので、この方法によって無限に素数の列を生み出すことが出来ます。

以上で素数の無限性が証明されました。■

おわりに

今回は、フェルマー数の「相異なるフェルマー数は互いに素」という性質を使って「素数の無限性」を証明する方法について紹介しました。

フェルマー数に「いい感じ」の漸化式があるというのも面白かったですし、それを使うと「すべてが互いに素」であることが示せるのも面白いですね。

最後の「素数の無限性」を示す論法では、(今回はフェルマー数を用いましたが)ほかの似たような数列でも実現できそうです。無限に続く数列  a_0, a_1, a_2, \ldots

 a_n = a_{n-1} a_{n-2} \cdots a_{1} a_{0} + d

なる漸化式を満たし、さらに任意の  n について  a_n d が互いに素である、を満たす数列が存在するとしましょう。前節と同様の議論により、 a_n の素因子の一つを  q_n することで、無限に続く素数の列  q_0, q_1, q_2, \ldots を得ることができます。

 a_n として  F_n を使ったのが今回紹介した証明で、 a_n として  n 番目の素数を使うとユークリッドの証明そのものだったというわけですね。


今回のお話は橋本喜一朗先生の著書の第一章の内容を参考にさせていただきました。

探検! 数の密林・数論の迷宮

探検! 数の密林・数論の迷宮

橋本先生の本では、第二章で同様の性質をもつ、すなわち素数の無限性の証明に使える数列について研究しています。ほかにも魅力的な数論の話がたくさん載っている本なので、(本当はあまり人に教えたくないですが)よかったらご覧になってみてください。

それでは今日はこの辺で。

関連記事

 F_5 の素因数分解の方法や、 F_n k\cdot 2^{n+2} + 1 という形の素数でしか割り切れないことの証明などが書いてある記事です。
tsujimotter.hatenablog.com