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

質問

素数が無限にあることをどうすれば証明できますか?

回答No.5

Tacosan

他にも
・∀n≧2 ∃prime ∈ (n, 2n)
・∀ε>0 ∃N ∀n≧N ∃prime ∈ (n, (1+ε)n)
・Fermat数 F_n = 2^(2^n)+1 は全て互いに素
も証明に使えます. こいつらの証明とか, これを使ってどのように「素数が無限にある」ことを示すかは「専門家」に聞けば教えてくれるんじゃないですかね.

回答No.4

Tacosan

何の「専門家」が参考にするんだろうなぁ＞#5
Π(1-1/p) = 0 は使っていいんだっけ?

回答No.3

zk43

pを任意の素数とし、p1を2^p－1の素因数の一つとする。
フェルマーの小定理から2^(p1-1)≡1（mod p1）
2^p≡1（mod p1）より、p|p1-1
よって、p＜p1
同様に、p2を2^p1－1の素因数の一つとすると、p1＜p2
この繰り返しにより、素数の無限列p＜p1＜p2＜p3＜・・・が構成できる。
（これも釣り？）

回答No.2

tysdtyhsdy

ユークリッドによる証明
背理法による。
素数が有限個しかないと仮定し、それらを次のようにおく。

ただし n は定数。

を考えよう。q は合成数であるか素数であるかのいずれかである。
q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。

参考URL：

http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

回答No.1

Ichitsubo

素数の数は有限であることを仮定し、背理法を用いることで証明可能です。
今まで知られた素数を小さい方からp1,p2,……,pn-1,pnとします。
さて、その全てを掛け合わせた数＋１
　p1*p2*……pn-1*pn + 1
はp1,p2,……,pn-1,pnのうちどれで割り切ることができますか？