素数 無限

質問

「素数は無限にある」証明について。（たびたびすみません）

素数が有限個で n 個と仮定し
素数を P1, P2, P3, …, Pn とする
P = (P1 x P2 x P3 x…x Pn) + 1
とおくと、
PはP1からPnで割り切れない　・・・理解できます。
従って、
Pは n+1 個目の新たな素数　　・・・★ここが理解できません。

Pは、１～P-1の数で割り切れないなら、素数（定義そのもの）ですが。
Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。

中学生ぐらいの証明のようですが、自分の頭の悪さに苦しんでいます。

2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509

回答No.5

ramayana

こんな当たり前のことがどうして議論になるのか、理解しがたいことです。ANo.3が正しい。

引用された「証明」は、でたらめです。質問者さんの反例がそれを示しています。

回答No.4

B-juggler

Ｎｏ．１です。

まず、「合成数」とは素数の積であらわされる数です。

それ以外の表現はありません。

素数でないのなら、この数をＡとしておくと、

Ａは素数で割れます、何らかのね（それをＰＡ　としておきますね）。

Ａ＝ＰＡ　×　Ｐ（何個かあるかもしれないけど）　で必ずあらわせますね。

素数でない数字は、必ず合成数で、素数の積で現されています。

　＃素因数分解できるということですよ。

で、お礼にもらっている分、２のほうは関係ないです。
　＃答えがはっきりしています。　必ず素数になるのがわかっているから。

１のほうですね。

合成数になるかもしれない？　これがなりませんよヾ（＠⌒ー⌒＠）ノ

　この辺は無限大絡むので難しいんだけど。

想像してみてください、としか言いようがないのだけど、

今見つかっている、最大の素数を　Ｐｎ　としておきますね。

素数の積を考えます。

（合成数Ｚ）＝２×３×５×７×・・・・・×５９×・・・・×５９９×・・・・・×Ｐｎ

としておきます。

これは素数ではないね。　ここＯＫ？　＋１はまだしていないからね。

単純に合成数です。

Ｚ＋１＝２×・・・・・×５９９×・・・・×Ｐｎ　＋１

さてこれは何かで割り切れますか？　ってことです。

今最大は　Ｐｎ　ね。　たとえば２で割っても　１余りますね？

５９９で割っても　１　余るね？　Ｐｎで割っても　１余りますね？

割り切れせんよね？　そしたら合成数ではないよね（！）

割り切れるはずがないから素数ですよね？　これさえいければ問題ないのだけど。

例が挙がっているものだけど、もう一回説明しておくと、

2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509

最大の素数が１３　なわけですね。

３００３１かな？　これは　２で割れる？　３は？　５は？　７は？

１１は？　１３は？

次は１７か、それより大きいものに関しては、

＞素数が有限個で n 個と仮定し
＞素数を P1, P2, P3, …, Pn とする
＞P = (P1 x P2 x P3 x…x Pn) + 1
＞とおくと、
＞PはP1からPnで割り切れない　・・・理解できます。

この仮定では想定されていなくて、理解できてないってことですよ。

ここをもう一回読み直して、冷静になってください。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.3

中村 拓男（@tknakamuri）

他の質問でも指摘されましたように、
この証明はユークリッドの証明が
何故か誤って流布されているものです。

正しくは、

Pはリストにない素数であるか
リストにない素数で割り切れる合成数である。

Pが素数であることを示す必要はありません。
Pが素数でも合成数でも矛盾は起きるのです。

お礼

的確なご回答ありがとうございます。

>Pが素数でも合成数でも矛盾は起きるのです。
Pが合成数であると、どのような矛盾があるのでしょうか？

回答No.2

bgm38489

素数は有限個で、ｎ個あるわけですね。Ｐｎとは、最後の素数です。
どの素数でも割れない。ここで合成数とは、素数の積で表される数である。素数で割れないのに、合成数で割れるということがあり得るか？
ある数は、２でも３でも割れない。すると２×３の６で割れる可能性があるか？
最後の式はどういうつもりであげたのかわからないが、最後の素数を13としたのに、59あるいは509で割れるやないか、というのは論外です。

お礼

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

>合成数とは、素数の積で表される数
私の認識では、合成数は素数以外の数です。
合成数は必ず素数の積で表されるのでしょうか？（簡単に証明できるのでしょうか）

最後の式は、Pは n+1 個目の新たな素数でない反例だと思って記載しました。

回答No.1

B-juggler

こんばんは。あ～なるほど。

これがすべてですよ。

＞2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509

この式の左辺は　１３までの素数　＋　１　ですね？

右辺は　１３より大きい素数の合成数ですね？

左辺を大きくしてみて？　それが書かれている定義です。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

お礼

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

１．Pは n+1 個目の新たな素数でない場合、素数は無限個とは限らないと思うのですが。

２．右辺が合成数である場合も、素数である場合もあると思いますが。