- 締切済み
素数 無限
「素数は無限にある」証明について。（たびたびすみません） 素数が有限個で 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
- 62m652627de37
- お礼率16% (30/181)
- 数学・算数
- 回答数15
- ありがとう数3
- みんなの回答 （15）
- 専門家の回答
みんなの回答
- ramayana
- ベストアンサー率75% (215/285)
こんな当たり前のことがどうして議論になるのか、理解しがたいことです。ANo.3が正しい。 引用された「証明」は、でたらめです。質問者さんの反例がそれを示しています。
- B-juggler
- ベストアンサー率30% (488/1596)
Ｎｏ．１です。 まず、「合成数」とは素数の積であらわされる数です。 それ以外の表現はありません。 素数でないのなら、この数をＡとしておくと、 Ａは素数で割れます、何らかのね（それをＰＡ としておきますね）。 Ａ＝ＰＡ × Ｐ（何個かあるかもしれないけど） で必ずあらわせますね。 素数でない数字は、必ず合成数で、素数の積で現されています。 ＃素因数分解できるということですよ。 で、お礼にもらっている分、２のほうは関係ないです。 ＃答えがはっきりしています。 必ず素数になるのがわかっているから。 １のほうですね。 合成数になるかもしれない？ これがなりませんよヾ（＠⌒ー⌒＠）ノ この辺は無限大絡むので難しいんだけど。 想像してみてください、としか言いようがないのだけど、 今見つかっている、最大の素数を Ｐｎ としておきますね。 素数の積を考えます。 （合成数Ｚ）＝２×３×５×７×・・・・・×５９×・・・・×５９９×・・・・・×Ｐｎ としておきます。 これは素数ではないね。 ここＯＫ？ ＋１はまだしていないからね。 単純に合成数です。 Ｚ＋１＝２×・・・・・×５９９×・・・・×Ｐｎ ＋１ さてこれは何かで割り切れますか？ ってことです。 今最大は Ｐｎ ね。 たとえば２で割っても １余りますね？ ５９９で割っても １ 余るね？ Ｐｎで割っても １余りますね？ 割り切れせんよね？ そしたら合成数ではないよね（！） 割り切れるはずがないから素数ですよね？ これさえいければ問題ないのだけど。 例が挙がっているものだけど、もう一回説明しておくと、 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で割り切れない ・・・理解できます。 この仮定では想定されていなくて、理解できてないってことですよ。 ここをもう一回読み直して、冷静になってください。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
他の質問でも指摘されましたように、 この証明はユークリッドの証明が 何故か誤って流布されているものです。 正しくは、 Pはリストにない素数であるか リストにない素数で割り切れる合成数である。 Pが素数であることを示す必要はありません。 Pが素数でも合成数でも矛盾は起きるのです。
- bgm38489
- ベストアンサー率29% (633/2168)
素数は有限個で、ｎ個あるわけですね。Ｐｎとは、最後の素数です。 どの素数でも割れない。ここで合成数とは、素数の積で表される数である。素数で割れないのに、合成数で割れるということがあり得るか？ ある数は、２でも３でも割れない。すると２×３の６で割れる可能性があるか？ 最後の式はどういうつもりであげたのかわからないが、最後の素数を13としたのに、59あるいは509で割れるやないか、というのは論外です。
お礼
ご回答ありがとうございます。 >合成数とは、素数の積で表される数 私の認識では、合成数は素数以外の数です。 合成数は必ず素数の積で表されるのでしょうか？（簡単に証明できるのでしょうか） 最後の式は、Pは n+1 個目の新たな素数でない反例だと思って記載しました。
- B-juggler
- ベストアンサー率30% (488/1596)
こんばんは。あ～なるほど。 これがすべてですよ。 ＞2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 この式の左辺は １３までの素数 ＋ １ ですね？ 右辺は １３より大きい素数の合成数ですね？ 左辺を大きくしてみて？ それが書かれている定義です。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
お礼
ご回答ありがとうございます。 １．Pは n+1 個目の新たな素数でない場合、素数は無限個とは限らないと思うのですが。 ２．右辺が合成数である場合も、素数である場合もあると思いますが。
- 1
- 2
関連するQ&A
- 素数は無限
質問２点。 １． 「素数は無限に存在する」証明をwikipediaで調べると、 背理法で素数が無数にあることを証明した、 素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、 いずれも正しくない と書かれています。 wikipediaが常に真実とは限りませんが、 Google検索で素数の無限である証明で検索すると、上記の誤解している人による解説ばかりです。 何を（どちらを）信じればよいか分からずに困っています。 ２． wikipediaによる正しい証明によると、、、 素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。 これは、背理法による証明だと思うのですが、、、、 お手数ですが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数 反例
素数が無限であることの証明について。 http://homepage2.nifty.com/mathfin/hairihou/hairihou03.htm 素数が無限個でないことがある。すなわち，素数が有限個であることがあると仮定し、 （反例の存在を仮定） その個数をｎ個とする。すべての素数を小さい方から順に P1，P2，P3 ，・・・・・・，Pn とおける。ここで， P = P1×P2×P3×・・・・・・×Pn + 1 により，自然数Pをつくると， Pは， P1，P2，P3 ，・・・・・・，Pn のいずれで割っても１余る。 よって，Pは１と自分自身以外に約数を持たないから素数である。 これはPnよりも大きい素数が存在することを意味しており，矛盾が生ずる。 よって，素数が有限個であることはない（反例は存在しない） ゆえに，素数は無限に存在する --------------------------------------------- P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、 上記の証明は間違いということですか？
- 締切済み
- 数学・算数
- 素数が無限個存在すること（エルデシュによる証明）
素数が無限個存在することの証明について、 素数―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 に対して ・・・・・・・・ と説明されているのですが、 ★マークの部分がよくわかりません。 素数が無限個存在することを使用しているのでは！？ もし有限なら、はるかに小さいεがとれないのではないでしょうか？ どうかご教授ください。
- ベストアンサー
- 数学・算数
- 4n+1型の素数について
４ｎ＋１型素数の無限性を示せ。 次のように考えた。行き詰まったのでアドバイスをお願いします。 ４ｎ＋１の素数は有限で最大をｐとする。 k=4(5×１３×・・×ｐ)＋１ とおく。 ｋは合成数のとき、ｋは４ｎ＋３型の素数の偶数個の積に素因数分解できるから、 ｋ＝（４ｘ＋１）（４ｙ＋１） ｘ，ｙ自然数 ＝１６ｘｙ＋４ｘ＋４ｙ＋１ となる。 このあとの矛盾の導き方が見えないので、この流れの証明とすると このあとどうなるのか、よろしくお願いします。
- 締切済み
- 数学・算数
- 素数は無限に存在する
素数が有限であると仮定し、その最大のものを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のいずれとも異なる． これは矛盾である。したがって定理が証明された． なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。
素数の分類と無限性に関して。 ※＾は乗数の意味です。 8n+1型の素数が無限に存在することの証明 原始根の存在（素数 p を法とする整数環 Z/pZ の乗法群が位数 p - 1 の巡回群であること）を使う。 x を整数とする時x＾4 + 1 の奇素数因子を p とする。 x＾4 ≡ - 1 (mod. p) より、両辺を2乗することでx^8≡1となる。 x の p を法とする整数環 Z/pZ の乗法群での位数は 8 で有るから、 p ≡ 1 (mod. 8) となる。ここで、 p ≡ 1 (mod. 8) となる素数が有限個であったとする時、その総乗積を P として、 (2P)＾4 + 1 の奇素数因子を考えると矛盾が出る。 私は2PをX"とおいて上と同様に考えました。 この証明の流れや、8n＋1型の素数が無限に存在することは理解できるのですが、上の証明における「位数は 8 で有るから、 p ≡ 1 (mod. 8) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 3n+1 の素数について
３ｎ＋１ 型 の素数の無限性を証明せよ。 次のような証明をしようとしたが、うまくいきません。アドバイスをお願いします。 ３ｎ＋１型の素数は有限とし、最大な素数をｐとする。 k=3(7×13×・・・×ｐ)＋１ とおく。 ｋは合成数であるから、素因数分解され、３ｎ＋２型の偶数個の積になる。（３ｎ＋１型の最大素数がｐであることから） ＊このあとの証明がうまくいきません。よろしくお願いします。
- ベストアンサー
- 数学・算数
- メルセンヌ素数でない素数は無限に存在するか？
素数は無限に存在することが知られています。 ユークリッドやオイラーの証明があります。 また、コンピュータでは、大きい素数を探すときに、 メルセンヌ素数を探します。 しかし、メルセンヌ素数は無限にあるかどうかわかりません。 ここで、質問です。 メルセンヌ素数でない素数は、無限にあるのでしょうか？ 素数はメルセンヌ素数かメルセンヌ素数でない素数のどちらかです。 その二種類を合わせると、無限個ありますから、 メルセンヌ素数が有限個ならば、メルセンヌ素数でない素数は無限個あるとわかります。 でも、メルセンヌ素数は有限個しか見つかっていないだけで、 本当に有限個かどうかはわかりません。 メルセンヌ素数でない素数が無限個あるかどうかもわからないのではないでしょうか？ それとも、他の方法で、わかるのでしょうか？ 例えば、メルセンヌ数（素数とは限らない）とメルセンヌ数（素数とは限らない）の間には、 ２個以上のメルセンヌでない素数が存在することがわかっているとか。 でも、ずっと先に行くと、素数はすべてメルセンヌ素数になっているということは 考えられないでしょうか？ しかし、双子素数が無限に存在するならば、メルセンヌ素数でない素数が無限に存在しそうですね。 双子素数より弱くても、よさそうですね。 素数分布とか考えると、どうなるのでしょうね。 やっぱり、メルセンヌ素数でない素数は無限個あるような気がしてきました。
- ベストアンサー
- 数学・算数
- 素数は無限に多く存在することの証明（ユークリッドの別証）を二つの添削
ユークリッドの証明は背理法を用いた証明。 素数を有限個とするならその最大素数をpnとして素数を小さい順にp1,p2,…,pnとした時 N=p1*p2*p3*…pn + 1 全ての自然数は素因数に分解できるのでｐ1～pnの少なくとも一つ因数に持つはずだが、どれで割っても1あまる。これはpnが最大の素数であることに矛盾 素数は無限に存在する。 といった証明。今回はこれの別称として以下の漸化式を用いたものを解けという問題です。 ◆a_{n}:=2^(2^n) + 1, n=1,2,3,… を用いた証明 この時任意のm≠nに対しa_{m}, a_{n}は互いに素である。実際n>mの時 a_{n} - 2 = 2^(2^n) - 1 ={2^2^(n-1) + 1}{2^2^(n-1) - 1} =a_{n-1}*(a_{n-1} - 2) =a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 2) となるのでa_{m},a_{n}の公約数dは2の約数でなければならない。他方a_{m},a_{n}は奇数であるから（←漸化式より）d=1となる。すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□ ◆正整数の列a_nを次のように定める a_{n+1} = a_{n}*(a_{n} - 1) + 1, a_{1} = 2 これを用いて素数が無限であることを示すのですが 任意のm≠nに対して a_{n} - 1 = a_{n-1}*(a_{n-1} - 1) = a_{n-1}*a_{n-2}*(a_{n-2} - 1) = a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 1) よりa_{n},a_{m}の公約数は1の約数でなければならない。よってa_{n},a_{m}は互いに素である。 すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□ これら2つの証明はこれであっているでしょうか？
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。以前質問させていただいたことの延長になりま
素数の分類と無限性に関して。以前質問させていただいたことの延長になります。 ※＾は乗数の意味です。 8n+1型の素数が無限に存在することの証明 原始根の存在（素数 p を法とする整数環 Z/pZ の乗法群が位数 p - 1 の巡回群であること）を使う。 x を整数とする時x＾4 + 1 の奇素数因子を p とする。 x＾4 ≡ - 1 (mod. p) より、両辺を2乗することでx^8≡1となる。 x の p を法とする整数環 Z/pZ の乗法群での位数は 8 で有るから、 p ≡ 1 (mod. 8) となる。ここで、 p ≡ 1 (mod. 8) となる素数が有限個であったとする時、その総乗積を P として、 (2P)＾4 + 1 の奇素数因子を考えると矛盾が出る。 私は2PをX"とおいて上と同様に考えました。 同じ方法を用いることで証明することはできたのですが、 この証明の中で用いている「位数は 8 で有るから、 p ≡ 1 (mod. 8) となるの部分に関して ラグランジュの定理 位数nの有限郡Gの任意の部分郡Hの位数はGの位数の約数である を用いた場合、GとHに当たる部分はどこになるのでしょうか。今の段階では、nがｐ－１にあたり、Hの位数が８と考えています。ｐが素数で、８はｐ－１の約数になるとの考えは当っているでしょうか・・？ よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
的確なご回答ありがとうございます。 >Pが素数でも合成数でも矛盾は起きるのです。 Pが合成数であると、どのような矛盾があるのでしょうか？