素数 反例

質問

素数が無限であることの証明について。

http://homepage2.nifty.com/mathfin/hairihou/hairihou03.htm
素数が無限個でないことがある。すなわち，素数が有限個であることがあると仮定し、
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 （反例の存在を仮定）　

その個数をｎ個とする。すべての素数を小さい方から順に　

　　　　　　　　P1，P2，P3 ，・・・・・・，Pn　　

　　　とおける。ここで，

　　　　　　　　P = P1×P2×P3×・・・・・・×Pn + 1
　　　により，自然数Pをつくると，

　　　Pは， P1，P2，P3 ，・・・・・・，Pn のいずれで割っても１余る。

　　　よって，Pは１と自分自身以外に約数を持たないから素数である。

　　　これはPnよりも大きい素数が存在することを意味しており，矛盾が生ずる。
　　　よって，素数が有限個であることはない（反例は存在しない）　

　　 ゆえに，素数は無限に存在する

---------------------------------------------
P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、
上記の証明は間違いということですか？

回答No.16

MagicianKuma

>【全ての素数の積+1】が素数以外の数で割れる可能性もあると思うのですが。
ある数があったとして、素数以外の数で割りきれると言うことは、素数以外の数を割りきる数値があるということだろ？　たとえばｎが12（素数じゃないね)で割り切れると言うことは、12=2*2*3だから、2ないし3という素数で割りきれるだろ？　結局どんな素数をもってきても割りきれなければ、その数は素数になっちゃうわけさ。

回答No.15

he-goshite-

>この回答へのお礼

>最大の素数まで（のｎ個の素数）をもってきて計算してみてください。

「素数は無限」という事実（証明は理解できていないが）があるのに、最大の素数を持ってこいというのは無理だと思いますが。

素数は無限（に存在する）という事実を認めるのですね。
めでたしめでたし　

ついでに，「反例」が反例になっていないという事実も認めてください。

回答No.14

178-tall

>P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、
>上記の証明は間違いということですか？

P は 7 を超える素数 {59, 509} の積、という例ですネ。

　「P は素数、または max {pk} を超える素数の (合成？) 積」
　つまり、(仮想) 最大素数 11 を超える (少なくとも 1 個の) 素数が存在する。

といえば、反例じゃなくなりそう。

回答No.13

he-goshite-

ご質問いただきました。

＞とありますが、
P＝2 × 3 × 5 × 7 × 11 × 13 + 1
の場合は、Pは素数ではないとおもいますが。

そうです。
「素数が有限個で，　2,3,5,7,11,13　だけ（最大の素数は13）　とする仮定」が誤りだからです。
上のPが素数でないことは全然問題ではありません。
最大の素数まで（のｎ個の素数）をもってきて計算してみてください。

お礼

>最大の素数まで（のｎ個の素数）をもってきて計算してみてください。

「素数は無限」という事実（証明は理解できていないが）があるのに、最大の素数を持ってこいというのは無理だと思いますが。

回答No.12

he-goshite-

No.10です。

「反例」について意見を述べましたが，訂正します。
この反例は，何に対する反例か？
もし素数が，２，３，５，７，１１，１３　までの有限個しかないと仮定した場合，
すなわち　最大の素数が存在して，それは１３だとした場合，５９も５０９も（どちらも１３より大きいから）素数ではなく，合成数でなければならない。という（事実に反する）結論が得られます。

素数の範囲（２，３，５，７，１１，１３）同士の掛け算でこの数（＝P）が表されなければ，
上の証明に対する反例になりません。

回答No.11

中村 拓男（@tknakamuri）

>なぜなら【全ての素数の積+1】は全ての素数で割りきれないだろ。
>必ずあまりが１となる。だから【全ての素数の積+1】は素数になるしかないのだよ。

「しかない」じゃ数学にならないです。しっかり証明しないと。
もちろん素数が無数であることを前提にした定理は使えませんので
「自身以外の素数で割り切れない数は素数」は当然使用禁止です(^^;

回答No.10

he-goshite-

話が混乱しているようなので，整理します。

1)素数が無限個存在する　ということの証明として，
http://homepage2.nifty.com/mathfin/hairihou/hairihou03.htm
に書かれていることは正しいです。

2)反例として示されている式は，反例になっていません。
２×７＋１＝３×５　
が反例になりますか？

3)「上記の証明」は間違いではありません。
　「反例」と称する式が，まったく反例になっていないのです。

お礼

当該URLで、----------------------------------------

P = P1×P2×P3×・・・・・・×Pn + 1
　　　により，自然数Pをつくると，

　　　Pは， P1，P2，P3 ，・・・・・・，Pn のいずれで割っても１余る。

　　　よって，Pは１と自分自身以外に約数を持たないから素数である。

------------------
とありますが、
P＝2 × 3 × 5 × 7 × 11 × 13 + 1
の場合は、Pは素数ではないとおもいますが。

回答No.9

178-tall

< ANo.5 へ。

>>max{Pn} を超える素数
>がよく理解できておりません。

　　　　　↓

max{Pn} は、P1，P2，P3 ，・・・・・・，Pn
>　すべての素数を小さい方から順に　P1，P2，P3 ，・・・・・・，Pn　とおける。
でいえば、最大の Pn を指す。

つまり、
　P が 1 および P 自身以外に約数を持つとすれば、それは Pn を超える素数である。
と書いたわけですが、正しくは、QNo.8698323 の ANo.2 に記したように、
　「P は素数、または max {pk} を超える素数の (合成？) 積」
なんでしょうネ。

回答No.8

Tacosan

うん, その証明は間違い.

回答No.7

MagicianKuma

>【全ての素数の積+1】が素数でない可能性もあると思いますが。
ないのだよ。なぜなら【全ての素数の積+1】は全ての素数で割りきれないだろ。必ずあまりが１となる。だから【全ての素数の積+1】は素数になるしかないのだよ。そうすると、今まで考えてた全ての素数より大きい素数があるという矛盾に陥る。これは有限だと仮定したからなのよ。だから無数にあることになる。
2 × 3 × 5 × 7 × 11 × 13 + 1 が素数とは限らないのは、全ての素数で割りきれないとは言えないからだよ。実際59という素数では割りきれるだろ。

お礼

追記のご回答ありがとうございます。

>【全ての素数の積+1】は全ての素数で割りきれないだろ。
これは理解できましたが、
2 × 3 × 5 × 7 × 11 × 13 + 1 が素数とは限らない、があるように、

【全ての素数の積+1】が素数以外の数で割れる可能性もあると思うのですが。
（この辺の知識・理解が不足しています）