プロが教える店舗&オフィスのセキュリティ対策術

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

http://homepage2.nifty.com/mathfin/hairihou/hair …
素数が無限個でないことがある。すなわち,素数が有限個であることがあると仮定し、
                                          (反例の存在を仮定) 

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

        P1,P2,P3 ,・・・・・・,Pn  

   とおける。ここで,
 
        P = P1×P2×P3×・・・・・・×Pn + 1
   により,自然数Pをつくると,

   Pは, P1,P2,P3 ,・・・・・・,Pn のいずれで割っても1余る。
 
   よって,Pは1と自分自身以外に約数を持たないから素数である。

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

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

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

A 回答 (16件中1~10件)

>【全ての素数の積+1】が素数以外の数で割れる可能性もあると思うのですが。


ある数があったとして、素数以外の数で割りきれると言うことは、素数以外の数を割りきる数値があるということだろ? たとえばnが12(素数じゃないね)で割り切れると言うことは、12=2*2*3だから、2ないし3という素数で割りきれるだろ? 結局どんな素数をもってきても割りきれなければ、その数は素数になっちゃうわけさ。
    • good
    • 0

>この回答へのお礼



>最大の素数まで(のn個の素数)をもってきて計算してみてください。

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


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

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

>P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、


>上記の証明は間違いということですか?

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

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

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

  
    • good
    • 0

ご質問いただきました。



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

そうです。
「素数が有限個で, 2,3,5,7,11,13 だけ(最大の素数は13) とする仮定」が誤りだからです。
上のPが素数でないことは全然問題ではありません。
最大の素数まで(のn個の素数)をもってきて計算してみてください。
    • good
    • 0
この回答へのお礼

>最大の素数まで(のn個の素数)をもってきて計算してみてください。

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

お礼日時:2014/08/01 17:01

No.10です。


 
「反例」について意見を述べましたが,訂正します。
この反例は,何に対する反例か?
もし素数が,2,3,5,7,11,13 までの有限個しかないと仮定した場合,
すなわち 最大の素数が存在して,それは13だとした場合,59も509も(どちらも13より大きいから)素数ではなく,合成数でなければならない。という(事実に反する)結論が得られます。

素数の範囲(2,3,5,7,11,13)同士の掛け算でこの数(=P)が表されなければ,
上の証明に対する反例になりません。
    • good
    • 0

>なぜなら【全ての素数の積+1】は全ての素数で割りきれないだろ。


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

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

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



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

2)反例として示されている式は,反例になっていません。
2×7+1=3×5 
が反例になりますか?

3)「上記の証明」は間違いではありません。
 「反例」と称する式が,まったく反例になっていないのです。
    • good
    • 0
この回答へのお礼

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

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

   Pは, P1,P2,P3 ,・・・・・・,Pn のいずれで割っても1余る。
 
   よって,Pは1と自分自身以外に約数を持たないから素数である。

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

お礼日時:2014/07/31 22:02

< 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} を超える素数の (合成?) 積」
なんでしょうネ。

  
    • good
    • 0

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

    • good
    • 0

>【全ての素数の積+1】が素数でない可能性もあると思いますが。


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

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

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

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

お礼日時:2014/07/31 21:59

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!