- 締切済み
素数 反例
素数が無限であることの証明について。 http://homepage2.nifty.com/mathfin/hairihou/hairihou03.htm 素数が無限個でないことがある。すなわち,素数が有限個であることがあると仮定し、 (反例の存在を仮定) その個数を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 という反例がありますが、 上記の証明は間違いということですか?
- みんなの回答 (16)
- 専門家の回答
みんなの回答
- 中村 拓男(@tknakamuri)
- ベストアンサー率35% (674/1896)
Pn+1~√(P)で割り切れないことを証明していないので 駄目です。素数であることの基本です。
- 178-tall
- ベストアンサー率43% (762/1732)
>Pは, P1,P2,P3 ,・・・・・・,Pn のいずれで割っても1余る。 >よって,Pは1と自分自身以外に約数を持たないから素数である。 ↓ P が 1 および P 自身以外に約数を持つとすれば、それは max{Pn} を超える素数である。 …って、どこかに書いたことの繰り返しだよネ。
- 中村 拓男(@tknakamuri)
- ベストアンサー率35% (674/1896)
>P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、 >上記の証明は間違いということですか? 17も素数だよね、といわれてしまうと反例が粉砕されてしまいます。 要は、素数の積+1 は素数という推論は、それを証明しない限り使えないということです。
お礼
ご回答ありがとうございます。 結局、URLは証明としてはダメということなのでしょうか?
- MagicianKuma
- ベストアンサー率38% (135/348)
>P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、 >上記の証明は間違いということですか? 反例になっていません。現在何個の素数が見つかっているか知りませんが、相当多くの素数がみつかっています。で証明は「何個あるかは現在分かってないけれど、有限とすると2,3,5,・・・,Pnと並べて・・・」と言っているのです。つまり有限個としたらその【有限個の全ての素数の積+1】も素数になってしまうじゃん。といっているのです。上記の反例は【全ての素数の積+1】になっていないでしょう?
お礼
ご回答ありがとうございます。 P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例 のように、 【全ての素数の積+1】が素数でない可能性もあると思いますが。
- FEX2053
- ベストアンサー率37% (7991/21371)
ごめんなさい一部訂正 1.Pが素数ならば、これは初めの素数以外なので矛盾 2.Pが合成数なら、初めの素数以外の積になるので矛盾
お礼
ご回答ありがとうございます。
- FEX2053
- ベストアンサー率37% (7991/21371)
>Pは1と自分自身以外に約数を持たないから素数である。 ここがまちがい。 1.Pが素数ならば、これは初めの素数以外なので矛盾 2.Pが合成数なら、初めの素数以外になるので矛盾 これが正しい解です。
- 1
- 2
お礼
ご回答ありがとうございます。 >max{Pn} を超える素数 がよく理解できておりません。