素数が無限にあることの証明

表題のとおりですがいったいどんな手順で導き出されるのでしょうか？（概要で結構です）

No.3 ベストアンサー 回答者： waseda2003 回答日時： 2006/02/12 15:27

背理法で証明します。

素数がn個（有限個）しかないとして，その素数を
P(1)，P(2)，・・・P(n)とすると，

Q = P(1)P(2)・・・P(n)+1

はP(1)，P(2)，・・・，P(n)のいずれとも互いに素となり
ます。もしそうでないとすれば，Q-1がそのn個の素数
すべての倍数なので，P(1)，P(2)，・・・，P(n)すべてが
１の約数ということになってしまうからです。

Q≧2 ですから Qは必ず素因数を持つはずですが，
それはP(1)，P(2)，・・・，P(n)のいずれでもないので，
素数がn個ですべてとしたことに反します。
したがって，素数が有限個としたのが誤りで，
素数は無限個存在します。

ここで，Qは素数と決め付けることはできないので，
注意しましょう。

この回答へのお礼

ご回答ありがとうございます。
前の方と重複しますがもっと難しい理論だと思っていたので拍子抜けしてしまいました。

お礼日時：2006/02/12 16:09

No.2 回答者： anapaultole 回答日時： 2006/02/12 15:24

いまから二千年以上前にかの数学者ユークリッドによる背理法で証明されています。

概要は以下の通りです。
もし素数が有限数であり、その最大素数をMとする。
そして２からMまでのすべての素数全てを掛け合わせ
それに１を加えると２×３×５・・・M＋１との新たな数Nを作り出せる。
これNは明らかにMより多きい合成数で、これが素数でなければ
少なくとも存在する素数の一つで割れるだろう。だが、２から最大素数のMまでの
あるゆる素数で割ると、余りが1残る。
したがって、スタートの仮定（最大素数が存在する）が誤りであることが判明し
素数が無限であると証明される。　以上

この回答へのお礼

ご回答ありがとうございます。
前の方と重複しますがもっと難しい理論だと思っていたので拍子抜けしてしまいました。

お礼日時：2006/02/12 16:08

No.1 回答者： nice-guy7762 回答日時： 2006/02/12 15:07

素数が有限個とする。

その有限個の素数をすべて掛け合わせた数に１を足す。そうするとその数は、既知の素数では割れません。したがって、その数が既知の素数で素因数分解できないので、また素数となります。

この回答へのお礼

ご回答ありがとうございます。
もっと難しい理論だと思っていたので拍子抜けしてしまいました。

お礼日時：2006/02/12 16:06