連立漸化式を用いた素数の無限性の証明
素数の無限性の証明の歴史は古代ギリシャから始まり、その後数学者たちによってさまざまな方法で発展してきました。 今回は連立漸化式を用いたオリジナルの証明を考えてみたので紹介します。この証明が初出なら真に驚くべきことですが、少なくとも珍しい証明ではあると思います。それでは、よろしくお願いします。
主張
素数は無限に存在する。
この命題の最初の証明は、ユークリッドによる背理法での証明です。素数は \(2, \ 3, \ 5, \ 7, \ \cdots\) といった具合に、無限に存在します。
証明
step1.数列の定義
数列 \(\{a_n\}, \{b_n\}\) を以下の漸化式で定める。
\[ a_1 = b_1 = 1, \ \begin{cases} \begin{aligned} a_{n+1} &= a_n + b_n \\ b_{n+1} &= a_n \cdot b_n \end{aligned} \end{cases} \]
step2.数列の性質の証明
\(a_n\) と \(b_n\) が互いに素であることを数学的帰納法を用いて示す。
(i) \(n=1\) の場合
\(a_1 = b_1 = 1\) より、これらは互いに素であるから正しい。
(ii) \(n=k\) での成立を仮定した場合
\(a_{n+1}\) と \(b_{n+1}\) の最大公約数を \(G (\not = 1)\) とし、\(G\) の素因数の一つを \(g\) とする。 \(b_{n+1} = a_n \cdot b_n\) であり、仮定よりこれらは互いに素であるから \(a_n, \ b_n\) のどちらか一方のみが \(g\) の倍数である。 一方で、\(a_n + b_n\) も \(g\) の倍数であるから、\(g\) が素因数であることに矛盾する。よって、\(n=k+1\) においても正しい。
step3.数列の性質を用いた素数の無限性の証明
漸化式より、\(b_{n+1} = a_1 \cdot a_2 \cdot a_3 \cdot \cdots \cdot a_n\) である。一方で、\(a_{n+1}\) と \(b_{n+1}\) は互いに素であるから、 \(a_{n+1}\) は \(a_1 \cdot a_2 \cdot a_3 \cdot \cdots \cdot a_n\) と互いに素である。すなわち、\(a_{n+1}\) は \(a_1, \ a_2, \cdots, \ a_n\) と互いに素である。 よって、数列 \(\{a_n\}\) が無限に続くことより、前までの任意の項と互いに素な項が無限に続くので素数が無限に存在することが示された。\( \blacksquare \)