素数の無限性の証明
今回は，素数が無限に存在することの証明を考えてみたので，記事にしてみました．結構シンプルなので，新規性はないかもしれません．とりあえず 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$$とすることで今回の問題に関する証明を得ることができます．
最後に，冒頭の繰り返しになりますが，この証明を知っている場合，教えていただければ幸いです．（そのときできればソースも教えてもらえると嬉しいです．）
