素数の無限性の証明

3602

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

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

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

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

$n \neq m$ ならば $a_{n}$ と $a_{m}$ は互いに素である．

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

　ここまで来たら， $a_{n} \geq 2$ がすべての $n$ で成立することは明らかなので，
$a_{1}$ は $1$ つ以上素因数を持ち，
$a_{2}$ は $a_{1}$ が持たない素因数を $1$ つ以上持ち，
$a_{3}$ は $a_{1}$ と $a_{2}$ が持たない素因数を $1$ つ以上持ち， $\dots$
という感じで $a_{i}$ までの項を計算することで少なくとも $i$ 個以上の素数を発見できます． $i$ に上限はないので，結局いくらでも多くの素数を見つけることができます．

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

投稿日：2023年3月29日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

fff

4469

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

他の人のコメント

コメントはありません。

読み込み中

fff

素数の無限性の証明