19

素数の無限性の証明

3312
2
$$$$

 今回は,素数が無限に存在することの証明を考えてみたので,記事にしてみました.結構シンプルなので,新規性はないかもしれません.とりあえず Wikipedia とか 高校数学の美しい物語 にはのってなかったです.(どなたか知っている方がいれば教えてください.)

【2023.3.30追記】
今回のような証明は既出だったようです.
詳しくは こちらのツイート のリプや引用をご確認ください.

素数が無限に存在することを示せ.

$$ a_{1}=2,\qquad a_{n+1}=a_n^2-a_n+1$$
で整数列$\{a_n\}$を定めます.このとき,以下の性質が成り立ちます.

  • $n\ne m$ならば$a_n$$a_m$は互いに素である.

この証明は結構簡単です.$m>n$の場合のみを考えればよく,
$$ \begin{aligned} a_{n+1}=a_n^2-a_n+1&\equiv 1\pmod{a_n}\\ a_{n+2}=a_{n+1}^2-a_{n+1}+1&\equiv1\pmod{a_n}\\ \vdots \end{aligned}$$という感じに$a_m\equiv1\pmod{a_n}$が示されるので,互いに素であることが分かります.

 ここまで来たら,$a_n\ge2$がすべての$n$で成立することは明らかなので,
$a_1$$1$つ以上素因数を持ち,
$a_2$$a_1$が持たない素因数を$1$つ以上持ち,
$a_3$$a_1$$a_2$が持たない素因数を$1$つ以上持ち,$\cdots$
という感じで$a_i$までの項を計算することで少なくとも$i$個以上の素数を発見できます.$i$に上限はないので,結局いくらでも多くの素数を見つけることができます.

 いかがだったでしょうか.この証明をみてもわかる通り,$$ f(1)=0,\qquad f(n)\ge1(n=2,3,\ldots)$$となる整数係数多項式$f$すべてで
$$ a_1=2,\qquad a_{n+1}=f(a_n)+1$$とすることで今回の問題に関する証明を得ることができます.
 最後に,冒頭の繰り返しになりますが,この証明を知っている場合,教えていただければ幸いです.(そのときできればソースも教えてもらえると嬉しいです.)

投稿日:2023329

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

fff
fff
26
3897
間違いなどがあればご指摘お願いします

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中