素数 無限

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

素数が有限個で 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.15 回答者： tknakamuri 回答日時： 2014/08/05 10:42

蛇足ですが

原論の原文(9巻命題20)では根拠となる定理を
明示していて議論の入る余地はありません。

No.14 回答者： MagicianKuma 回答日時： 2014/08/04 20:25

No13>どんな仮定の下でPが素数だ言えるのかという説明が一切ない。

これで理解しろと言うほうが無理である。
おっしゃるとおり。前言撤回。証明に不備があるね。うん。勉強になった。

No.13 回答者： ramayana 回答日時： 2014/08/04 17:19

質問者さんは別に素数が無限にあることを否定しているわけでないが、念のために証明を書いておく。

１　（素数が無限に存在することの証明）

任意の素数の有限集合に対して、その集合に属さない素数が存在することを言えばよい。 そこで、Ω を 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 が素数であることが導かれた」としても、欠陥品であるという事実は揺るがない。

３　数学に限らず、いったん間違った説明が流布してしまうと、それを払拭するのに多大のエネルギーが必要になる。今回の例では、質問者さんの理解力に問題があるのではなく、無責任な「証明」を流布させた方に問題がある。こんなことが原因で、数学への意欲と能力がある方が、万が一挫折してしまうことがあったりしたら、残念なことである。

No.12 回答者： saboke 回答日時： 2014/08/03 15:13

あなたの疑問は、Ｐが、素数以外の合成数で割り切れる可能性があるので、Ｐは素数と言えないのではないか？というものでしょうか。

この証明では、Ｐが、P1からPｎまでの素数で割り切れないことが重要なのであって、実際にＰは、素数である必要はありません。

ここで、素数の定義と合成数との関係について確認しましょう。

素数とはご承知の通り「１とその数以外の数で割り切れない２以上の自然数」です。
合成数は、「１とその数以外に約数を持つ自然数」ですので、「素数以外の数」ということができます。

合成数は、二つの数の積で表すことができます。つまり合成数Ｎ＝ab a,b>1
このa又はbが、合成数であれば、さらに積で表すことができるため、この操作を繰り返すと、最終的に素数が出てきた段階で、分解することができなくなります。この操作を素因数分解といいます。この素因数分解を行うことで、全ての合成数は、複数の素数の積で表すことができます。（二つとは限りません。複数の素数です）

２以上の自然数は、素数と合成数しかないのですから、素数は素因数分解できません。よって素数は「他の素数で割り切れない数」ということができます。

このことを踏まえて、背理法による「素数は無限にある」ことの証明では、素数が有限と仮定すると、Ｐは、仮定した全ての素数で割り切れません。そのため、Ｐは素数ということになり、矛盾が生じ、素数は有限ではないとの結論が導かれます。

Ｐは、合成数である場合もあるのですが、素数を有限とすると合成数であるＰも素数となってしまう矛盾が生じます。その意味からも素数は無限であるとの結論となります。

他の質問から、ご理解のことと思いますが、この証明は、素数が無限にあることを証明したものであり、Ｐが素数であることを証明したものでは、ありません。

No.11 回答者： tknakamuri 回答日時： 2014/08/02 15:56

>Pが合成数であると、どのような矛盾があるのでしょうか？

既設の定理として、合成数は素因数を持つ。

というのがあります。

P はリスト中の素数で割り切れませんから、他に素数が存在することになります。
これは仮定と矛盾します。

No.10 回答者： he-goshite- 回答日時： 2014/08/02 00:55

ほかでも回答したのですが，また他の回答者さんも親切に教えてくださっているのに，……

この質問で，あなたのわからない点がわかった気がするので，
くどいですが，

０．素数というのは１とその数自身以外に約数をもたない自然数である。それ以外の自然数（１とその数以外の約数をもつ数）を合成数という。

「理解できます」までの文章では何が言われているか？

１．素数が有限個であると仮定する
２．その有限個（ｎ個）の素数すべてを使って，Pという数を作る
３．そうすると，Pは，P1からPnまでの数どれをもってきても割り切れない。
　つまり，有限な数（ｎ個）のどの素数をもってきてもPを割り切ることができない。
【ここまでは「理解できます」とおっしゃっていますね。】

そのようにして（計算式で）つくった新たな数（Pのことです）が，
素数でないなら，必ず素数（素数は有限でｎ個。P1からPnまでのどれか）で割り切れる
はずなのに，割り切れない。
ということを示している。
４．ということは，そういう仮定のもとにいままで論理を進めてきたのに，その仮定が崩れて，
５．じつはPは，新たな（ｎ＋１番めの？）素数だと考えざるを得ない。
という論理を
【★ここが理解できません。】
とおっしゃるわけですね？

合成数は必ず，どれかの素数で割り切れます。（この点，いいですか？）繰り返しになりますが，　
【１とその数自身で割り切れるだけで，ほかの数では割り切れない数が「素数」です。それ以外（の自然数）は合成数です。】

＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。
素数で割り切れないものは，合成数（＝いくつかの素数の積として表せる数）で割り切れるはずがありません。

もし，
すべての素数が，２と３と５と７と１１と１３だけ　という（有限の）６個だけだと（仮定）したら，
それらをすべて掛け合わせてさらに１を加えた，Pは，２から１３までのどの素数でも，（つまりすべての素数のうちのどれをもってきても）割り切れない
のです。

５９や５０９は，「すべての素数（２から１３まで）」の仲間に入れてはいけません。そう仮定して話を進めています。
もし，５９や５０９が，「すべての素数」のうちのいくつかを用いた（約数として持つ）「合成数」であるならば，
＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性
　
が成り立ちます。


なのに，ここで，最後の行に示された式のように，
Pが新たな素数である場合以外では，
１と５９以外では割り切れない５９という数や，１と５０９以外では割り切れない５０９という数を用いた（５９や５０９という素因数をもった）「合成数」を使わざるを得ない（つまり，言い方を変えれば，（素数の個数が有限で，２から１３までの７個ですべてである　という）仮定に反して，（Pそのものではないが，）あらたな「素数」が見つかってしまった）
という論理上の「矛盾」に陥ってしまうのです。

No.9 回答者： lx002PH 回答日時： 2014/08/01 11:02

あ、素数を約数に持つはこちらも使ってるか。

素数の約数を少なくともひとつ持つは示しておいた方が無難みたいですね。

No.8 回答者： lx002PH 回答日時： 2014/08/01 10:46

合成数の定義は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が、素数か、合成数でも別の素数を約数に持ってしまう、という一般の証明は、素数を必ず約数にもつという証明をしておかなくとも示すことができますから、お示しになった証明よりそこは優れていると思います。

No.7 回答者： tsuyoshi2004 回答日時： 2014/08/01 10:44

＞Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。

そんわけはないでしょう。
仮にＰ＝Ａ×Ｂ
（Ａは素数以外、Ｂは素数でも合成数でも構わない）
だとすれば、
ＡはＰ１～Ｐｎによる合成数ということになります。
そうであれば当然、ＰはＡの因数である素数で割り切れるはずです。

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

ほら！59とか509っていう新たな素数を見つけてしまったではないですか？
少なくとも、素数は2,3,5,7,11,13のほかに59と509は存在していたわけです。

No.6 回答者： tknakamuri 回答日時： 2014/08/01 09:36

誤って流布されている証明は、数が素因数分解できることが

前提になっています。

数が素因数分解できることは素数が無限であることにかかわりませんかね？

つっこんで検討したことはありませんが、素因数分解を前提に素数の無限を
証明するのは循環に陥りそうな気がします。そういうことはないと明確に
示してくれるのであれば問題はありませんが、少なくとも自明ではないと
思います。

本来のユークリッドの証明は、前提になる定理が、「全ての合成数は素因数を持つ」
だけなので美しいといえます。この定理はユークリッド自身が証明を示していて、
素数が無限であるかにかかわないことが明確です。