- ベストアンサー
素数の積に1を加算すると素数ですか？
誰か素数を順番に掛け算したものに対して１を加算すると素数になる理由を教えてください。 素数1*素数2*素数3*素数4*素数5,,,*素数n +1 = 素数と聞きました。 （2*3*5*7*11,,,,+1=素数） 別に素数a*素数b+ 1 =素数って訳でもないのに。。。 （3*5+1=16） なぜ素数の１番目から順に掛け算を行ったものに対して１を加算すると素数になるのでしょうか？
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (5)
- sanori
- ベストアンサー率48% (5664/11798)
最初の回答者です。 コメントにお答えします。 > 素数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 のどれでやっても、同様です。 以上です。
お礼
ご回答ありがとうございます。 割り算理解できました。
- proto
- ベストアンサー率47% (366/775)
>なぜ割り切れないと証明出来るのでしょうか？ 割り切れるとは、余りが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 合成数 素数の場合、素数（当然ですが）。 合成数の場合、その値を構成する素数が存在するはずだが、 今まで出てきた素数には存在しないので、（割り切れないので） 今まで出てきている素数よりも大きな素数がある。 ということですね。 数字は面白いですね。
- oguro-
- ベストアンサー率45% (192/419)
こんばんは。 １よりも大きな任意の整数ａ，ｂにおいて、 ａ×ｂ＋１ がａでもｂでも割り切れない・・・というのは分かります？ では、１よりも大きな任意の整数ａ，ｂ，ｃ，ｄにおいて ａ×ｂ×ｃ×ｄ＋１ がａでもｂでもｃでもｄでも割り切れない・・・というのは？ そうです。これらの計算は全て「あまり１」になります。 ですが、ただの整数だと、ａでもｂでもｃでもｄでも割り切れないけど、ｅなら割り切れるかもしれません。 そこで、素数です。 同じ理屈で任意の素数ａ，ｂ，ｃについて ａ×ｂ×ｃ＋１ は、ａ，ｂ，ｃのいずれの素数でも割り切れません。ただ、「任意の」素数と置くと、質問者様のご指摘にあるように素数ｄや素数ｅで割り切れる可能性があります。 ですが、今回の設問は、２から順に全ての素数を掛け算していきますので、どの素数でも割り切れないということになります。もっと言えば、どの素数で割っても「あまり１」になります。 ｎよりも小さなどの素数でも割り切れないのですから、ｎも素数になります。
お礼
ご回答ありがとうございます。 >ｎよりも小さなどの素数でも割り切れないのですから、ｎも素数になります 合成数の可能性もあるそうです。 SortaNerd様の回答番号No.6を参照ください。 質問の定義そのものが間違えていました。
- rabbit_cat
- ベストアンサー率40% (829/2062)
素数が無限にある証明についてでしょうか。 よくある勘違いですが、 ＞素数を順番に掛け算したものに対して１を加算すると素数になる こう言っているのではありません。 正確には、 「素数を順番に掛け算したものに対して１を加算すると、その数は、素数であるか、もし素数でなければ（合成数であれば）これまでに登場していな素数を素因数として持つ」 と言っています。 ＞3*5+1=16 １６は素数ではありませんが、16は、３、５以外の素因数２を持ちます。
お礼
> ＞素数を順番に掛け算したものに対して１を加算すると素数になる > こう言っているのではありません。 ご回答ありがとうございます。 大変参考になりました。
- sanori
- ベストアンサー率48% (5664/11798)
こんばんは。 たぶん、素数が無限個あることの証明と混同されています。 ＜証明＞ 素数が有限個（ｎ個）しかないと仮定し、 それらを、素数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,,,,に１を加算して素数になる理由が分かりません。。 私、なにか根本的なところで勘違いしていますでしょうか（汗） （こーゆーのは中学生ぐらいで習ってたのかな・・・）
関連するQ&A
- 桁上げ保存加算器（2進数計算）
2進数の積で桁上げ保存加算器で求めよと出てきました。 たとえばA=15、B=23（もちろん10進数表記です）のとき 2進数で表すと、A=(1111)、B=(10111)となります。 桁上げ保存加算器で求めよというのは 10進数の積の方法と同様に下の方法で1111*10111を解けばいいのでしょうか？ 1111 10111 ――― 1111 1111 1111 1111 ――――― 101011001＝345
- ベストアンサー
- その他（学問・教育）
- 双子素数についてのことです
双子素数がむげんにあるということの証明は これで充分じゃないでしょうか？ nは2以上の自然数 (1～n 番目の素数をかけていった積)+1 は素数 (1～n 番目の素数をかけていった積)-1 は素数 (1～n 番目の素数をかけていった積)±1 は双子素数 素数は無限個あるので双子素数も無限個あることになる これでいいのではないでしょうか？
- ベストアンサー
- 数学・算数
- 2進数の加算の繰り上がり
２進数の四則演算のプログラムを作りたいと思い、２進数を表示するところまではできたのですが、加算になると繰り上がりという壁にぶつかってしまいました。繰り上がりや桁上げなどがよく分からないので、お教えください。(下のソースコードが繰り上がりのない加算をするまでのものです) #include <stdio.h> int main(void) { int a,b,i,j,x[8],y[8],z[8]; do{ puts("二つの符号なし整数を入力してください。(ただしa>bとし、bはのべき乗の値とする)"); printf("a="); scanf("%d",&a); printf("b="); scanf("%d",&b); if(a < = b) puts("入力した値がa>bになっていません。\a"); }while(a < = b); for( i = 0; i < = 7; i + +){ x[i] = a % 2; a = a / 2; y[i] = b % 2; b = b / 2; } puts("aとbをそれぞれ二進数で表すと"); printf("a="); for( i = 7; i > = 0; i - -){ printf("%d",x[i]); } puts(""); printf("b="); for( i = 7; i > = 0; i - -){ printf("%d",y[i]); } printf("となります。\n\n"); printf("<加算>\n"); printf("c=a+b="); for( j = 7; j > = 0; j - -){ z[j]=x[j]^y[j]; printf("%d",z[j]); } return(0); }
- ベストアンサー
- C・C++・C#
- 素数が無限個存在すること（エルデシュによる証明）
素数が無限個存在することの証明について、 素数―wikipedia―によれば、エルデシュによる素数の逆数和の 発散性の証明は、素数が無限個存在することの証明にもなっているらしいです。 （証明において、素数が無限個存在することを用いていないため・・・？） http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0 その証明は、 背理法による。 n 番目の素数を pn とする。 素数の逆数和が収束すると仮定すると、 任意の ε > 0 に対してある自然数 N が存在して、 1/pN+1 + 1/pN+2 + 1/pN+3 + ... < ε となる。 ★ いま、 ε = 1/2 としよう。任意の自然数 n に対して ・・・・・・・・ と説明されているのですが、 ★マークの部分がよくわかりません。 素数が無限個存在することを使用しているのでは！？ もし有限なら、はるかに小さいεがとれないのではないでしょうか？ どうかご教授ください。
- ベストアンサー
- 数学・算数
- 2進数の加算回路について
こんばんわ。 2進数の加算回路を行う回路は、1ビット目（LSB）の加算に半加算器を使って、2ビット目以降の加算に全加算回路を用いることで実現できますよね？でもこの方法の場合、下位の桁から毛か上げが順次確定していくことによってビット数が大きくなればなるほど結果が算出されるまでの応答速度が遅くなってしまいます。それを克服するために、何か別の方法はないでしょうか？別の方法で回路を作ることは可能でしょうか。 ご指導お願いします。
- ベストアンサー
- 高校
- 素数についての質問です。
いくつか聞きたいことがあります。 ●素数は無限個あるということは証明されているのでしょうか？ ●nと2nの間に必ず素数があるかどうかという問題は解かれているのでしょうか？ ●ある素数が何番目に出てくる素数であるかを求める公式はありますか？ もし、ない場合そのような公式を作れば大発見？ ●1000万桁の最小の素数はXであるとを発表したとき、それが正しいかを調べるのは誰？ ●素数関連で単純だけど解けていない問題で賞金のかかったものはありますか？ 一応自分で調べてはいるものもあるのですが、見つけた情報が いつのもので正しいかどうかがいまいち不明なので書かせてもらいました。お願いします。
- ベストアンサー
- 数学・算数
- 素数は無限に存在する
素数が有限であると仮定し、その最大のものをNとする。 ａ、b、cを自然数とした場合、すべてのａについて Ｎ＋ａ＝b＊cとなるｂ、ｃが存在する。 この式を変形すると Ｎ＝ｂ＊ｃ－ａとなる。 ところがａ＝ｂの場合、ａはＮの約数となり最初の仮定と矛盾する。 よって素数は無数にある。 この証明は正しいのですか？というのはこの矛盾をつくことによって、有限ではない！！って感じがしないんですよね。a=bの時はＮは素数ではない！！っていうのは分かるんですけど、a≠bでちょっと特別の場合（a=1,b=4,c=5など）は成立しちゃうんじゃない！？っていうのもあるし（aの値が変化することによってｂ、ｃの値も変化するだろうし・・・）、Ｎは素数ではないっていう証明をしただけで、「最大の」素数ではないって感じがしないんですよね・・・ こっちの証明は普通に納得するんですが・・・ 定理が成立しないとすると，素数は有限個である．それらの素数をP1,P2,P3,・・・,Pnとする．このとき，Q=(P1P2P3…Pn)+1を考えると， QはP1,P2,P3,・・・,Pnのどれでも割り切れない．したがって， Qを素数の積として表したとき，この積に現れる素数はP1,P2,P3,・・・,Pnのいずれとも異なる． これは矛盾である。したがって定理が証明された． なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
- ベストアンサー
- 数学・算数
- すごく大きい数を素因数分解する方法について教えてください。
すごく大きい数を素因数分解する方法について教えてください。 問題：m,nを2以上の整数とする。√2009＝m√nのとき、m=(a) n=(b)である この問題の答えがa=49 B=41でした。 解説には√2009＝√49×41＝7√41と書いてあります。 解き方は、2009が何で割れるか小さい数から順に試すしかないのでしょうか。 なにか早く解く裏ワザなどあったらいいな・・・と思いました。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数の分類に関して
前回質問させていただいた証明に関することなのですが、最後の一文が分からないためもう一度質問させていただきます。 ［類題］ 「8n + 3 型の素数は無限に多くある事を示せ。」の略解。 ＊）文中のｐ＾は複素数ｐの共役な複素数です。例えば、ｐ＝１＋iの場合、ｐ＾は１－iのことです。 また、a2 はaの二乗という意味です。 証明）もし 8n + 3 型の素数が有限個であったとし、その全体を p1, p2, ... , pn とする。 P = p1p2 ... pn + √2 i と置いて、これを単項イデアル整域 Z[√2 i ] で素元分解する。 N (P) = PP^ は奇数であるから（正確には、 N (P) ≡ 3 ( mod. 8 ) 、） P の有理整数の素因数は奇数である。この因子は PP^ の中では偶数冪で出てくるから、その部分は 8n + 1 型である。又、 P は有理整数に同伴でないから、a + b √2 i 型 (b ≠ 0, 有理整数の素因子と同伴でない物) の因子がある。PP^ は奇数であるから a は奇数である。更に、この a + b √2 i 型の因子の b が偶数であるとすると、 N( a + b √2 i ) = a2 + 2b2 ≡ 1 (mod. 8) であるから、 この形の b が全て偶数であるとすると PP^ ≡ 3 (mod. 8) と矛盾する。従って b が奇数の物 a + b √2 i が有るが、素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。故にこの型の素数は無限個。 素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。 における a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8）となった場合なぜ有限性に矛盾していると言えるのでしょうか。 a2＋2b2が素数でないならば矛盾はしてないのでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数の分類に関して
［類題］ 「8n + 3 型の素数は無限に多くある事を示せ。」の略解。 ＊）文中のｐ＾は複素数ｐの共役な複素数です。例えば、ｐ＝１＋iの場合、ｐ＾は１－iのことです。 また、a2 はaの二乗という意味です。 証明）もし 8n + 3 型の素数が有限個であったとし、その全体を p1, p2, ... , pn とする。 P = p1p2 ... pn + √2 i と置いて、これを単項イデアル整域 Z[√2 i ] で素元分解する。 N (P) = PP^ は奇数であるから（正確には、 N (P) ≡ 3 ( mod. 8 ) 、） P の有理整数の素因数は奇数である。この因子は PP^ の中では偶数冪で出てくるから、その部分は 8n + 1 型である。又、 P は有理整数に同伴でないから、a + b √2 i 型 (b ≠ 0, 有理整数の素因子と同伴でない物) の因子がある。PP^ は奇数であるから a は奇数である。更に、この a + b √2 i 型の因子の b が偶数であるとすると、 N( a + b √2 i ) = a2 + 2b2 ≡ 1 (mod. 8) であるから、 この形の b が全て偶数であるとすると PP^ ≡ 3 (mod. 8) と矛盾する。従って b が奇数の物 a + b √2 i が有るが、素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。故にこの型の素数は無限個。 この証明における、この因子は PP^ の中では偶数冪で出てくるから、その部分は 8n + 1 型である。がなぜ言えるのかという点と 最後の一文である 素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。 における a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8）がなぜ分かるのかが理解できません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
具体例をありがとうございます！ すっきりしました。 先程から、「すげー、すげー、すげー」と連発していたらまわりから ウザがられています。:) > 2×3×5×7×11×13 +1 = 30031 = 59×509 この１文が全てを語っていますね。 13を素数の最大値と仮定すると、30031は素数or合成数である。 （素数の場合は一旦無視して） 合成数は素数を持つはずだが2,3,5,7,11,13にはない。 （59,509の素数の存在を示唆している） おー、すげー。やっぱりすげー。 数字が面白くなってきました。 ありがとうございます！