素数は無限に多く存在することの証明（ユークリッドの別証）を二つの添削

質問

ユークリッドの証明は背理法を用いた証明。
素数を有限個とするならその最大素数をpnとして素数を小さい順にp1,p2,…,pnとした時
N=p1*p2*p3*…pn + 1
全ての自然数は素因数に分解できるのでｐ1～pnの少なくとも一つ因数に持つはずだが、どれで割っても1あまる。これはpnが最大の素数であることに矛盾
素数は無限に存在する。

といった証明。今回はこれの別称として以下の漸化式を用いたものを解けという問題です。

◆a_{n}:=2^(2^n) + 1, n=1,2,3,…　を用いた証明

この時任意のm≠nに対しa_{m}, a_{n}は互いに素である。実際n>mの時
a_{n} - 2 = 2^(2^n) - 1
　　　　={2^2^(n-1) + 1}{2^2^(n-1) - 1}
　　　　=a_{n-1}*(a_{n-1} - 2)
　　　　=a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 2)
となるのでa_{m},a_{n}の公約数dは2の約数でなければならない。他方a_{m},a_{n}は奇数であるから（←漸化式より）d=1となる。すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□

◆正整数の列a_nを次のように定める
a_{n+1} = a_{n}*(a_{n} - 1) + 1, a_{1} = 2
これを用いて素数が無限であることを示すのですが

任意のm≠nに対して
a_{n} - 1 = a_{n-1}*(a_{n-1} - 1)
　　　　　　= a_{n-1}*a_{n-2}*(a_{n-2} - 1)
　　　　　　= a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 1)
よりa_{n},a_{m}の公約数は1の約数でなければならない。よってa_{n},a_{m}は互いに素である。
すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□

これら2つの証明はこれであっているでしょうか？

回答No.1

Tacosan · ベストアンサー

ざっと見ましたが, どちらもこれで OK だと思います. フェルマー数を使う, 前者の証明は (そこそこ) 有名ですね.

お礼

ありがとうございます。
期末テスト前に先生から配布された問題プリントを解いていて不安だったもので。
前者の証明は有名ですよね
僕も中学か高校の時にならった記憶があります。