tsujimotterのノートブック

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

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

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

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

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



 F_n    p   p  p


tsujimotter
tsujimotter.hatenablog.com

201712
数理科学 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

20202307調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