素数の積に1を加算すると素数ですか？

質問

誰か素数を順番に掛け算したものに対して１を加算すると素数になる理由を教えてください。
素数1*素数2*素数3*素数4*素数5,,,*素数n +1 = 素数と聞きました。
（2*3*5*7*11,,,,+1=素数）

別に素数a*素数b+ 1 =素数って訳でもないのに。。。
（3*5+1=16）

なぜ素数の１番目から順に掛け算を行ったものに対して１を加算すると素数になるのでしょうか？

回答No.6

SortaNerd · ベストアンサー

それは間違っています。
反例 :
2×3×5×7×11×13 +1 = 30031 = 59×509

なんだか回答者の皆さんも「素数が無限個ある証明」と混同されているようですが、質問の式の誤りは、
「掛け合わせられた最大の素数より大きい素因数がある」
可能性が考えられていない点です。
素数無限個の証明では、「有限個存在する全素数」を掛け合わせているのがこの問題と異なる点です。

お礼

具体例をありがとうございます！
すっきりしました。

先程から、「すげー、すげー、すげー」と連発していたらまわりから
ウザがられています。:)

> 2×3×5×7×11×13 +1 = 30031 = 59×509
この１文が全てを語っていますね。

13を素数の最大値と仮定すると、30031は素数or合成数である。
（素数の場合は一旦無視して）
合成数は素数を持つはずだが2,3,5,7,11,13にはない。
（59,509の素数の存在を示唆している）
おー、すげー。やっぱりすげー。

数字が面白くなってきました。

ありがとうございます！

回答No.5

sanori

最初の回答者です。
コメントにお答えします。

> 素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
> は素数であるから、仮定に反する。
なぜ割り切れないと証明出来るのでしょうか？
割り切れないから素数だと思うのですが、
素数1*素数2,,,,に１を加算して素数になる理由が分かりません。。
私、なにか根本的なところで勘違いしていますでしょうか（汗）
（こーゆーのは中学生ぐらいで習ってたのかな・・・）

割ると、あまりが１になります。

素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１

を素数1で割ると、

素数1*素数2*素数3*素数4*素数5*・・・*素数n

の部分は素数1で割り切れます。
ですから、お尻にある　１　があまります。

算数風の式で書けば、

（素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１）　÷　素数1　＝　素数2*素数3*素数4*素数5*・・・*素数n　　あまり　　１

これは、素数2～素数n　のどれでやっても、同様です。

以上です。

お礼

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

割り算理解できました。

回答No.4

proto

>なぜ割り切れないと証明出来るのでしょうか？

割り切れるとは、余りが0になることです。
(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)を素数1,素数2,...で順番に割っていくと、どの素数で割ったときも余りが1になります。
余りが0ではないので、少なくとも素数1～素数nでは割り切れないということなのです。

この、"少なくとも"素数1～素数nでは割り切れない、という部分がミソです。

>割り切れないから素数だと思うのですが、
>素数1*素数2,,,,に１を加算して素数になる理由が分かりません。。

おそらく背理法をうまく理解していないのでしょうが。
結論から言います。(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)が必ず素数になるとは限りません。

前段までで、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は少なくとも素数1～素数nでは割り切れない事が分かりました。
次に二つの可能性が考えられます。
　(1) (素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は素数である。
　(2) (素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は合成数である。

まず、(1)だとすれば、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は素数です。
ですが(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は素数1～素数nのどれよりも大きいので、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は素数1～素数n以外の素数である事になります。
つまり、素数1～素数n以外にも素数は存在したということで、素数1～素数nは素数の全てではなかったということになります。

次に、(2)だとすれば、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は合成数です。
合成数であるということは、何か素数を約数として持つはずです。そしてその素数で割れば割り切れるはずです。
ですが、先ほども示したように(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は少なくとも素数1～素数nでは割り切れません。
ということは、素数1～素数n以外にも別の素数xが存在して、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は素数xであれば割り切れるということになります。
つまり、素数1～素数n以外にも素数xが存在するはずだということになって、素数1～素数nは素数の全てではなかったということになります。

結局、(1)の場合でも(2)の場合でも、素数1～素数n以外に素数が存在することになります。
素数を全部集めてきて素数1～素数nとしたはずなのに、捕まえきれていない素数xが存在することになる。
それはつまり、素数は有限個で全てではなく無限個存在するということなのです。

最後に、もう一度だけ確認しますね。
上に示した証明は、「素数は無限に存在する」証明であって、「(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)が素数である」証明ではありません。
実際、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)は必ず素数になる訳ではなく、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)が合成数になる場合もあります。
反例は、質問者さん自身で挙げていますね。
　　3*5+1=16
これが、(素数1*素数2*素数3*素数4*素数5*・・・*素数n＋１)が必ず素数になる訳ではないという立派な証拠なのです。

お礼

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

途中で頭から煙が出てきましたが、理解できました。

素数1,素数2,素数3,素数n+1=素数 or 合成数
素数の場合、素数（当然ですが）。
合成数の場合、その値を構成する素数が存在するはずだが、
今まで出てきた素数には存在しないので、（割り切れないので）
今まで出てきている素数よりも大きな素数がある。

ということですね。
数字は面白いですね。

回答No.3

oguro-

こんばんは。

１よりも大きな任意の整数ａ，ｂにおいて、
ａ×ｂ＋１
がａでもｂでも割り切れない・・・というのは分かります？
では、１よりも大きな任意の整数ａ，ｂ，ｃ，ｄにおいて
ａ×ｂ×ｃ×ｄ＋１
がａでもｂでもｃでもｄでも割り切れない・・・というのは？

そうです。これらの計算は全て「あまり１」になります。
ですが、ただの整数だと、ａでもｂでもｃでもｄでも割り切れないけど、ｅなら割り切れるかもしれません。
そこで、素数です。

同じ理屈で任意の素数ａ，ｂ，ｃについて
ａ×ｂ×ｃ＋１
は、ａ，ｂ，ｃのいずれの素数でも割り切れません。ただ、「任意の」素数と置くと、質問者様のご指摘にあるように素数ｄや素数ｅで割り切れる可能性があります。

ですが、今回の設問は、２から順に全ての素数を掛け算していきますので、どの素数でも割り切れないということになります。もっと言えば、どの素数で割っても「あまり１」になります。
ｎよりも小さなどの素数でも割り切れないのですから、ｎも素数になります。

お礼

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

>ｎよりも小さなどの素数でも割り切れないのですから、ｎも素数になります

合成数の可能性もあるそうです。
SortaNerd様の回答番号No.6を参照ください。

質問の定義そのものが間違えていました。

回答No.2

rabbit_cat

素数が無限にある証明についてでしょうか。
よくある勘違いですが、
＞素数を順番に掛け算したものに対して１を加算すると素数になる
こう言っているのではありません。

正確には、
「素数を順番に掛け算したものに対して１を加算すると、その数は、素数であるか、もし素数でなければ（合成数であれば）これまでに登場していな素数を素因数として持つ」
と言っています。

＞3*5+1=16
１６は素数ではありませんが、16は、３、５以外の素因数２を持ちます。

お礼

> ＞素数を順番に掛け算したものに対して１を加算すると素数になる
> こう言っているのではありません。

ご回答ありがとうございます。
大変参考になりました。

回答No.1

sanori

こんばんは。

たぶん、素数が無限個あることの証明と混同されています。

＜証明＞
素数が有限個（ｎ個）しかないと仮定し、
それらを、素数1、素数2、素数3、素数4、素数5、・・・、素数n
と置く。

仮定によれば、
素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
は素数ではない。
しかし、
素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
は、素数1～素数nのどれでも割り切れない。
つまり、
素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
は素数であるから、仮定に反する。
よって、素数は無限個ある。

以上、ご参考になりましたら幸いです。

補足

早速のお返事ありがとうございます。
ご指摘の通り、素数が無限個あることの証明から派生した疑問です。

> 素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
> は、素数1～素数nのどれでも割り切れない。
> つまり、
> 素数1*素数2*素数3*素数4*素数5*・・・*素数n　＋　１
> は素数であるから、仮定に反する。

なぜ割り切れないと証明出来るのでしょうか？
割り切れないから素数だと思うのですが、
素数1*素数2,,,,に１を加算して素数になる理由が分かりません。。
私、なにか根本的なところで勘違いしていますでしょうか（汗）
（こーゆーのは中学生ぐらいで習ってたのかな・・・）