- 締切済み
素数 無限
「素数は無限にある」証明について。（たびたびすみません） 素数が有限個で 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）
- 専門家の回答
みんなの回答
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
蛇足ですが 原論の原文(9巻命題20)では根拠となる定理を 明示していて議論の入る余地はありません。
- MagicianKuma
- ベストアンサー率38% (135/348)
No13>どんな仮定の下でPが素数だ言えるのかという説明が一切ない。これで理解しろと言うほうが無理である。 おっしゃるとおり。前言撤回。証明に不備があるね。うん。勉強になった。
- ramayana
- ベストアンサー率75% (215/285)
質問者さんは別に素数が無限にあることを否定しているわけでないが、念のために証明を書いておく。 １ （素数が無限に存在することの証明） 任意の素数の有限集合に対して、その集合に属さない素数が存在することを言えばよい。 そこで、Ω を P1, P2, ...,Pn という n 個の素数から成る集合とする。 P = P1・P2・,,, ・Pn +1 と置く。 P の素因子の１つを Q とすれば、Q は、 P1, P2, ...,Pn のどれでも割り切れないから、Ωに属さない素数である。（証明終わり） ここで、任意の整数が一意的に素因数分解できる、という事実を使った。これまでの回答の中に、素因数分解の一意性の証明でもし素数の無限性を使っているなら循環論法に陥るのではないかとの指摘があった。しかし、本題から外れるので説明を省略するが、通常、素因数分解の一意性の証明は有理整数環が「ユークリッド環」であるという事実から導かれており、素数の無限性は使われない。よって、循環論法にはならない。直感的にも、「素因子の個数が有限個の素元分解環」が珍しくもないことから、素因数分解の一意性の証明に素数の無限性が使われる、という状況は考えにくい。 ２ （質問者さんが引用した「証明」がなぜ欠陥品か） ご質問文の記号の下、一般に P = P1・P2・,,, ・Pn +1 が素数とは限らないのだから、それを根拠とした引用の「証明」が間違いなのは明らか。 なお、これまでの回答の中に、素数が有限個との仮定の下で P が素数であることが導かれることを指摘したものがある。これは、論理的に間違いではないものの、この「証明」を擁護したことにならない。 論理学の初歩であるが、事実に反する仮定を置けばどんな結論も導くことができる。「 P は素数である」だけでなく、「 P は合成数である」「P =1 である」「P = 0 である」など、なんでも導くことができる。背理法を無定見に使うなら「もし素数が有限個なら、 P = 1 でありかつ P = 0 である。これは矛盾だから素数は無限個である」といった訳の分からない「証明」を許すことになる。これを避けるため、背理法の仮定を使って何かの結論を導いたとき、少なくともその仮定を使ったという事実をいちいち明示することが求められる。 引用された「証明」にはそうした配慮が欠落しており、どんな仮定の下でPが素数だ言えるのかという説明が一切ない。これで理解しろと言うほうが無理である。よって、「素数が有限個との仮定の下で P が素数であることが導かれた」としても、欠陥品であるという事実は揺るがない。 ３ 数学に限らず、いったん間違った説明が流布してしまうと、それを払拭するのに多大のエネルギーが必要になる。今回の例では、質問者さんの理解力に問題があるのではなく、無責任な「証明」を流布させた方に問題がある。こんなことが原因で、数学への意欲と能力がある方が、万が一挫折してしまうことがあったりしたら、残念なことである。
- saboke
- ベストアンサー率50% (31/62)
あなたの疑問は、Ｐが、素数以外の合成数で割り切れる可能性があるので、Ｐは素数と言えないのではないか？というものでしょうか。 この証明では、Ｐが、P1からPｎまでの素数で割り切れないことが重要なのであって、実際にＰは、素数である必要はありません。 ここで、素数の定義と合成数との関係について確認しましょう。 素数とはご承知の通り「１とその数以外の数で割り切れない２以上の自然数」です。 合成数は、「１とその数以外に約数を持つ自然数」ですので、「素数以外の数」ということができます。 合成数は、二つの数の積で表すことができます。つまり合成数Ｎ＝ab a,b>1 このa又はbが、合成数であれば、さらに積で表すことができるため、この操作を繰り返すと、最終的に素数が出てきた段階で、分解することができなくなります。この操作を素因数分解といいます。この素因数分解を行うことで、全ての合成数は、複数の素数の積で表すことができます。（二つとは限りません。複数の素数です） ２以上の自然数は、素数と合成数しかないのですから、素数は素因数分解できません。よって素数は「他の素数で割り切れない数」ということができます。 このことを踏まえて、背理法による「素数は無限にある」ことの証明では、素数が有限と仮定すると、Ｐは、仮定した全ての素数で割り切れません。そのため、Ｐは素数ということになり、矛盾が生じ、素数は有限ではないとの結論が導かれます。 Ｐは、合成数である場合もあるのですが、素数を有限とすると合成数であるＰも素数となってしまう矛盾が生じます。その意味からも素数は無限であるとの結論となります。 他の質問から、ご理解のことと思いますが、この証明は、素数が無限にあることを証明したものであり、Ｐが素数であることを証明したものでは、ありません。
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
>Pが合成数であると、どのような矛盾があるのでしょうか？ 既設の定理として、合成数は素因数を持つ。 というのがあります。 P はリスト中の素数で割り切れませんから、他に素数が存在することになります。 これは仮定と矛盾します。
- he-goshite-
- ベストアンサー率23% (189/802)
ほかでも回答したのですが，また他の回答者さんも親切に教えてくださっているのに，…… この質問で，あなたのわからない点がわかった気がするので， くどいですが， ０．素数というのは１とその数自身以外に約数をもたない自然数である。それ以外の自然数（１とその数以外の約数をもつ数）を合成数という。 「理解できます」までの文章では何が言われているか？ １．素数が有限個であると仮定する ２．その有限個（ｎ個）の素数すべてを使って，Pという数を作る ３．そうすると，Pは，P1からPnまでの数どれをもってきても割り切れない。 つまり，有限な数（ｎ個）のどの素数をもってきてもPを割り切ることができない。 【ここまでは「理解できます」とおっしゃっていますね。】 そのようにして（計算式で）つくった新たな数（Pのことです）が， 素数でないなら，必ず素数（素数は有限でｎ個。P1からPnまでのどれか）で割り切れる はずなのに，割り切れない。 ということを示している。 ４．ということは，そういう仮定のもとにいままで論理を進めてきたのに，その仮定が崩れて， ５．じつはPは，新たな（ｎ＋１番めの？）素数だと考えざるを得ない。 という論理を 【★ここが理解できません。】 とおっしゃるわけですね？ 合成数は必ず，どれかの素数で割り切れます。（この点，いいですか？）繰り返しになりますが， 【１とその数自身で割り切れるだけで，ほかの数では割り切れない数が「素数」です。それ以外（の自然数）は合成数です。】 ＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。 素数で割り切れないものは，合成数（＝いくつかの素数の積として表せる数）で割り切れるはずがありません。 もし， すべての素数が，２と３と５と７と１１と１３だけ という（有限の）６個だけだと（仮定）したら， それらをすべて掛け合わせてさらに１を加えた，Pは，２から１３までのどの素数でも，（つまりすべての素数のうちのどれをもってきても）割り切れない のです。 ５９や５０９は，「すべての素数（２から１３まで）」の仲間に入れてはいけません。そう仮定して話を進めています。 もし，５９や５０９が，「すべての素数」のうちのいくつかを用いた（約数として持つ）「合成数」であるならば， ＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性 が成り立ちます。 なのに，ここで，最後の行に示された式のように， Pが新たな素数である場合以外では， １と５９以外では割り切れない５９という数や，１と５０９以外では割り切れない５０９という数を用いた（５９や５０９という素因数をもった）「合成数」を使わざるを得ない（つまり，言い方を変えれば，（素数の個数が有限で，２から１３までの７個ですべてである という）仮定に反して，（Pそのものではないが，）あらたな「素数」が見つかってしまった） という論理上の「矛盾」に陥ってしまうのです。
- lx002PH
- ベストアンサー率62% (10/16)
あ、素数を約数に持つはこちらも使ってるか。素数の約数を少なくともひとつ持つは示しておいた方が無難みたいですね。
- lx002PH
- ベストアンサー率62% (10/16)
合成数の定義は1と自分自身以外の約数をもつ自然数というものであり、合成数は少なくともひとつ素数の約数を持ちます。なぜならば合成数cについて、cは必ず1より大きくcより小さな約数の積で書けますが、そのような約数のうち最小なものをaとし、c=abとおくと、aが素数になるからです。これはaが合成数ならばa=stとなる1より大きくaより小さな自然数s,tがあることから、 c=ab=(st)b=s(tb) となり、sがaより小さな約数となってしまうためaが最小であることに反するので示されます。 よって、素数がP[1],P[2],...,P[n]の有限個しかないと仮定すると、 P=P[1]P[2]...P[n]+1 が合成数であればP[1]～P[n]のいずれかを素因数として持つはずですが、どれで割っても1余るから、合成数にはなり得ません。よって1か素数のはずですが、1とP[1]～P[n]のどれよりも大きいので、P[1]～P[n]がすべての素数であることに反します。 という流れをきちんと示してあれば、正しい証明になります。 Pが、素数か、合成数でも別の素数を約数に持ってしまう、という一般の証明は、素数を必ず約数にもつという証明をしておかなくとも示すことができますから、お示しになった証明よりそこは優れていると思います。
- tsuyoshi2004
- ベストアンサー率25% (665/2600)
＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。 そんわけはないでしょう。 仮にＰ＝Ａ×Ｂ （Ａは素数以外、Ｂは素数でも合成数でも構わない） だとすれば、 ＡはＰ１～Ｐｎによる合成数ということになります。 そうであれば当然、ＰはＡの因数である素数で割り切れるはずです。 ＞2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 ほら！59とか509っていう新たな素数を見つけてしまったではないですか？ 少なくとも、素数は2,3,5,7,11,13のほかに59と509は存在していたわけです。
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
誤って流布されている証明は、数が素因数分解できることが 前提になっています。 数が素因数分解できることは素数が無限であることにかかわりませんかね？ つっこんで検討したことはありませんが、素因数分解を前提に素数の無限を 証明するのは循環に陥りそうな気がします。そういうことはないと明確に 示してくれるのであれば問題はありませんが、少なくとも自明ではないと 思います。 本来のユークリッドの証明は、前提になる定理が、「全ての合成数は素因数を持つ」 だけなので美しいといえます。この定理はユークリッド自身が証明を示していて、 素数が無限であるかにかかわないことが明確です。
- 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の位数が８と考えています。ｐが素数で、８はｐ－１の約数になるとの考えは当っているでしょうか・・？ よろしくお願いします。
- ベストアンサー
- 数学・算数
