人気サイト様 最新記事

博士ちゃんねる ヘッドライン

レスの強調ウゼェー!というドクターへ

レス内の強調表示をOFFにする コチラをクリックして切り替えてください。設定は30日間Cookieに保存されます。
現在のステータス:強調有効

素数が無限に存在する証明 @ [数学板]


素数が無限に存在する証明 @ [数学板]
1: 132人目の素数さん 2012/08/09 12:45:23
ユークリッド的な証明では最後の素数 p があると仮定して
p 以下の素数の積に 1 を加えた q = 2・3・・・p + 1 が素数だから矛盾だという.

しかし,これに文句を言うやつがいる.q は素数か,p より大な素数で割りきれるかだと.
しかし,私に言わせればこれらは両方だめだ.
正解は「q は p より大きいので合成数だが,どの素数でも割りきれないので矛盾」である.
素数 (Wikipedia) 素数(そすう、英: prime number)とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。正の約数の個数が 2 である自然数と言い換えることもできる。もし 1 を素数の定義に含めたとすると、算術の基本定理(素因数分解の可能性・一意性、すなわち「1 でない自然数は、素数の積に、素因数の順序を除いて一意に表される」を述べた定理)において、素因数分解の可能性は成り立つが一意性は成り立たなくなるということが起きてしまう。そのため、1 は素数の定義から除外するのが一般的である。
素数は無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。
整数の中で、あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
エウクレイデス (Wikipedia) エウクレイデス アレクサンドリアのエウクレイデス(古代ギリシャ語: Ευκλείδης, Eukleides[1]、ラテン語: Euclides[2]、英語: Euclid(ユークリッド)、紀元前3世紀? - )は、古代ギリシアの数学者、天文学者とされる。数学史上最も重要な著作の1つ『原論』(ユークリッド原論)の著者であり、「幾何学の父」と称される。プトレマイオス1世治世下(紀元前323年-283年)のアレクサンドリアで活動した。『原論』は19世紀末から20世紀初頭まで数学(特に幾何学)の教科書として使われ続けた[3][4][5]。線の定義について、「線は幅のない長さである」、「線の端は点である」など述べられている。基本的にその中で今日ユークリッド幾何学と呼ばれている体系が少数の公理系から構築されている。エウクレイデスは他に光学、透視図法、円錐曲線論、球面天文学、誤謬推理論、図形分割論、天秤などについても著述を残したとされている。
4: 132人目の素数さん 2012/08/09 12:56:40
なんでスレ立てたの?
ほめてもらいたかったの?
13: 132人目の素数さん 2012/08/10 02:20:28
背理法使わないで>>1の証明ってできるの?

背理法嫌いだーって人たちいるでしょ?
20: 132人目の素数さん 2012/08/10 17:28:45
>>13
1/1+1/2+1/3+1/4+1/5+1/6+...+1/n+...
=(1+1/2+1/4+1/8+...)*(1+1/3+1/9+1/27+...)*(1+1/5+1/25+1/125+...)*...*(1+1/p+1/p^2+1/p^3+...)*...
={1/(1-1/2)} * {1/(1-1/3)} * {1/(1-1/5)} *....* {1/(1-1/p)} *...
=(2/1)*(3/2)*(5/4)*...*(p/(p-1))*...
一行目は発散する量なので、最終行も発散する。つまり、素数は無限にある
23: 132人目の素数さん 2012/08/10 22:59:25
>>20
これって背理法は使ってないの?
26: 132人目の素数さん 2012/08/11 02:04:48
>>13
ユークリッドのオリジナルの証明は背理法を使っていない。有限個の素数を集めれば、それ以外に必ず素数が見つかるという、いわば素数生成のアルゴリズムを示している。
その手の背理法を使わない、素数をいくらでも見つけられるという方法による「素数が無限に存在することの証明」もいくつか知られている。
背理法 (Wikipedia) 背理法(はいりほう、英: proof by contradiction, reduction to the absurd, indirect proof, apagogical argument など、羅: reductio ad absurdum)とは、ある命題 Pについて、P の否定 ¬P を仮定すると、矛盾(ある命題とその否定が同時に証明されること)または明らかに偽であるような結論が導けることにより、 P を結論付けることである。帰謬法(きびゅうほう)とも。
管理人より:>>20のやつは帰納法による証明…ということで合ってるのかな?
ドミノ倒し式にすべての要素に対して成り立つことを証明する→帰納法…という認識です。(管理人的に)
2.14追記:コメ欄でご指摘があり、「ウソを書くな」ということで、オイラーの証明へリンクを貼っておきます。どうもスミマセン…。('A`)
素数が無数に存在することの証明 > オイラーの証明
15: 132人目の素数さん 2012/08/10 02:24:54
任意の素数pに対して、pよりも大きい素数を(そのような素数が存在するという仮定を使わずに)具体的に構成できたら、世紀の大発見です
17: 132人目の素数さん 2012/08/10 02:47:51
勢いで>>15を書いたけど、構成的な証明はあるみたいね
任意の自然数nに対して、nより大きい素数が存在すること

n!+1が素数ならば、それでよし
n!+1が素数でないならば、n!+1の、1でない正の約数のうち最小のものは素数である
しかもこれはnより大きい(n以下の数でn!+1を割った余りは1)
27: 132人目の素数さん 2012/08/11 02:07:11
って>>17にもあったか。
そもそもユークリッドの時代にはいわゆる実無限の概念は一般的ではないため、可能無限的な証明にならざるを得ない。
25: 132人目の素数さん 2012/08/11 02:00:37
>>15
素数列の漸化式ならつまらないものがたくさんある。まあたいてい2以上の自然数nと2nの間に素数が存在することは利用してるけどね。
32: 132人目の素数さん 2012/08/12 01:13:01
>>25
チェビシェフの定理の証明には素数が無限にあることは使っていない
パフヌティ・チェビシェフ (Wikipedia) パフヌティ・チェビシェフ パフヌーティー・リヴォーヴィッチ・チェビシェフ(露: Пафну́тий Льво́вич Чебышёв、ラテン転写: Pafnuty Lvovich Chebyshev、1821年5月16日(ユリウス暦5月4日) - 1894年12月8日(ユリウス暦11月26日))は、ロシアの数学者。
(中略)
チェビシェフは確率論、統計学および数論における業績で知られている。チェビシェフの不等式は、標準偏差を持つ確率変数Xに対して、Xの実現値とXの平均値のずれが以上になる確率は、決して1/を超えないということを示している。すなわち、 チェビシェフの不等式 チェビシェフの不等式は、大数の法則を証明するために用いられる。
36: 132人目の素数さん 2012/10/08 08:00:02
素数が有限だったらそれ以上の数はどれかの素数の合成数なので、その素数のどれかでかならず割れる。
全部の素数をかけていちたすとどの素数でも割れない。
37: 132人目の素数さん 2012/10/08 08:33:02
2,3,7,43,43^2+43,...
q(q+1)(q(q+1)+1)(q(q+1)(q(q+1)+1)+1)...
38: 132人目の素数さん 2012/10/08 09:19:48
>>37
ケアレスミスがあるけどそれはどうでもいいとして、
そのやり方は互いに素な多項式が無限個あることの証明の副産物だね。
42: 132人目の素数さん 2012/12/10 20:39:35
素数の集合について考える
 命題:最大の素数は存在する
 対偶:存在しないのは、「最大の素数」でない素数

  2、3、5、7、11・・・・など「最大の素数」でない素数は存在する。
  したがって、対偶は偽。命題も偽。「最大の素数」というものは、存在しない。
  すべての素数は、「最大でない素数」である。
 結論:素数は無限に存在する。

上の文章の「素数」という語を、例えば「双子素数」や「完全数」という言葉にに置き換える。
さらに、最大でない双子素数(3と5、5と7など)や最大でない完全数(6や28など)を示す。
すると、「双子素数は無限に存在する」と「完全数は無限に存在する」が証明できる。
43: 132人目の素数さん 2012/12/10 20:59:16
空集合でない。「4の約数」「100以下の偶数」のように区間・範囲も限定しない。
つまり、自然数全体を対象とした「○○の集合」について考える
 命題A:最大の○○が存在する
 対偶A:存在しないのは、最大でない○○

  もし命題が真なら、「最大の○○」が1個だけ存在する。例、偶素数の集合。
  もし命題が偽なら、「最大でない○○」が無限個存在する。例、素数の集合。

 命題B:最大の○○、最大でない○○が存在する
 対偶B:存在しないのは、「最大の○○」でない○○、「最大でない○○」でない○○
     =存在しないのは、最大でない○○、最大の○○
  真だと仮定すると矛盾が生じるので偽。「最大」と「最大でない」が共に存在する、
  または共に存在しない、どちらもありえない。常に一方だけが存在する。
以下、  命題Aと同じ。

結論:2個(または2組)存在するなら、それは無限個(無限組)存在する。
45: 132人目の素数さん 2012/12/11 00:46:13
>>42
命題 Pが素数集合であるなら、∃p_max∈P ≧ ∀p∈P が成り立つ。
対偶 ∃p_max∈P ≧ ∀p∈P が成り立たないなら、Pは素数集合ではない。

対偶法を使う意味は無さそう。
双子素数 (Wikipedia) 双子素数(ふたごそすう、twin prime)とは、差が 2 である2つの素数の組のこと。2 と 3 の組を除くと、双子素数はもっとも数の近い素数の組である。双子素数の例としては、 3 と 5 、 11 と 13 、 857 と 859 などがある。
素数が無限に存在することが古代ギリシャ時代から知られていたのに対し、双子素数は無限に存在するかという問題、いわゆる「双子素数の予想」や「双子素数の問題」と呼ばれる問題は、多くの数論学者が無限に存在するだろうと予想するが、2013年の時点で、いまだに数学上の未解決問題である。
完全数 (Wikipedia) 完全数(かんぜんすう,英: perfect number)とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。例えば 6 (= 1 + 2 + 3)、28 (= 1 + 2 + 4 + 7 + 14) や496が完全数である。『聖書』の研究者は、最初の完全数が 6 なのは「神が6日間で世界を創造した」こと(天地創造)、次の完全数が 28 なのは「月の公転周期が28日である」ことと関連があると考えていたとされる[1]。2013年2月現在、発見されている完全数はメルセンヌ素数と同じく48個である。紀元前より考察されている対象であるにもかかわらず、「偶数の完全数が無数に存在するか?」、「奇数の完全数は存在するか?」、「末尾が6か8以外の完全数は存在するか?」、という問題は未解決である。
44: 132人目の素数さん 2012/12/10 23:48:26
最大の素数p_maxが存在すると仮定する。
x=p_1×p_2×・・・×p_max+1と置くと、xは1とx以外では割り切れないので素数であり、かつx>p_maxであるから、仮定と矛盾する。
よって最大の素数は存在しない。
48: 132人目の素数さん 2013/04/06 20:53:41
>>44
それって>>1とどこが違うの?
49: 132人目の素数さん 2013/07/13 07:43:24
素数が無限にあると仮定すると
そっすうそっすうそっすうそっすうそっすうそっすうそっすうそっす・・・

仮定は嘘っすということで
背理法により素数は有限個しかないことになってしまう。
50: 132人目の素数さん 2013/09/21 23:14:56
51: カンカンガクガク 2013/12/04 22:01:53
背理法である事をひとまず忘れて、最後の素数pが存在する(素数は有限個しかない)為の条件を導き出したら、矛盾する結果となるから、「素数は無限に存在する」という結論が得られる、と考えればどうでしょうか?
52: 132人目の素数さん 2013/12/04 23:28:52
それを背理法と云う
53: 132人目の素数さん 2013/12/06 01:29:03
ユークリッドのオリジナル証明は背理法じゃなく当時らしい可能無限性を示したもの。
55: 132人目の素数さん 2013/12/06 11:49:26
>>53
ルート2が無理数の証明はどうだったっけ?
54: 132人目の素数さん 2013/12/06 02:53:41
背理法が嫌いな人もいるからな。
56: 132人目の素数さん 2013/12/06 12:17:20
無理数の定義が「有理数ではない」だから、pと仮定すると矛盾だからpでない、という否定導入則は必要。しかし、pでないと仮定すると矛盾だからpが成り立つ、という本来の背理法は必要ない。
58: 132人目の素数さん 2013/12/07 16:24:29
>>56
pとqの二者があって二者のみ存在するとき、pでないと仮定して矛盾が生じれば、「qである」と結論する(できる)、というのが背理法、ではないでしょうか?
59: 132人目の素数さん 2013/12/07 16:58:20
否定導入則の特殊な場合としてそれも含まれるという意味ならその通り。その場合はq=¬pだから。
60: 132人目の素数さん 2013/12/07 18:25:18
そか。
二重否定の除去が要らないんだね。
61: 132人目の素数さん 2013/12/07 18:30:24
pでないと仮定して矛盾が生じれば、「pである」だろw
62: 132人目の素数さん 2013/12/07 18:33:29
二者のみである必要は無い
何でもいいからある仮定をして矛盾が導かれれば、その仮定が誤りと言える
63: 132人目の素数さん 2013/12/07 18:40:59
否定導入則なら直観主義でも成立するが、背理法は直観主義では成立せず、古典論理で成り立つ。
管理人より:√2が無理数であることの証明は、こちらなどいかがでしょう?素人の管理人はギリで理解できるレベル。ゆえに、こちらにおいでのドクターは誰でも理解できるはず。
無理数であることの証明

どうでもいいですが、無理数を発見したのはピタゴラスの弟子なんだそうですが、それを師匠に言ったら「神聖な数の法則を乱した」みたいな理由で殺されたとか。こわっ!
このエピソードゆえに、管理人はピタゴラスをあまり尊敬できない。
2.14追記:コメ欄でご指摘があり、「素因数分解の一意性を利用した証明も書いたほうが良い」ということで、以下のリンクも追加しておきます。
簡単!無理数であることの証明
背理法がテーマですから、こっちのがより適当だったですね。どうもありがとうございます。
64: 133人目の素数さん 2013/12/15 19:17:58
つまらない質問で恐縮なんですけど、
素数に素数を掛けて1を足したものは必ず素数になると聞いたんですが、それは本当ですか?
65: 132人目の素数さん 2013/12/15 21:31:45
3*5+1=16
66: 132人目の素数さん 2013/12/15 23:14:39
その命題が真なら、いくらでも巨大素数を生成できるだろ
67: 132人目の素数さん 2013/12/15 23:54:45
単に素数だけを生成する式ならいくらでもある。実用的じゃないけど。
68: 132人目の素数さん 2013/12/16 22:52:18
>>64
ちょっと違う。
素数に、その素数未満の全ての素数を掛けて+1。
3x2+1=7
5x3x2+1=31
7x5x3x2+1=211
73: 132人目の素数さん 2013/12/18 01:25:47
>>64
それは間違い。
ただし、素数が有限個であると仮定した場合
それらの素数を全て掛け合わせて1足した数は、どの素数でも割りきれないから素数になる


と同時に、最初に仮定した有限個の素数の何れとも等しくないから素数ではないとも言える
これは矛盾だから、最初の仮定は偽である

というのが背理法での証明の流れ


背理法の証明中に出てくる命題は実際には真とも偽ともなりうるから注意が必要になる
背理法嫌いで有名な某教授も、これが嫌だから背理法は嫌いみたい
管理人より:2.14追記:コメ欄でご指摘があり、「具体例くらい書いとけ」とのことですが、ドクターの説明がわかりやすかったのでそのまま引用させていただきます。
例えば、2 × 3 × 5 × 7 × 11 × 13 + 1は59 × 509に分解されるから、素数ではない。
ただし、左辺2,3,5,7,11,13を「素数を有限個と仮定した場合の(素数の)リスト」とすると、仮に分解できたとしても右辺59,509はそのリストに含まれないという矛盾。
なるほど、そういうことか…。ありがとうございます、そしてアホでスミマセン。('A`)
74: 132人目の素数さん 2013/12/18 18:57:08
最初の仮定が矛盾するから背理法なのか・・・・
対偶とか背理法とか難しいな。
75: 132人目の素数さん 2013/12/18 20:01:44
だからかユークリッドは背理法は使ってないんだよな。
76: 132人目の素数さん 2013/12/21 16:38:25
背理法で証明した場合
証明中に出てくる論証は正しいこともあるし、正しくないこともある

それを確かめる為には、別途に証明が必要になる

対偶で証明した場合
証明中で出てくる論証は正しいことがいえる
78: 132人目の素数さん 2013/12/21 18:35:03
あ~わかんねぇ~w
管理人より:同じく。
79: 132人目の素数さん 2013/12/22 16:53:24
Aが偽の時、Bが真であっても偽であってもA⇒Bは真になる
つまり、偽の前提からは真の命題も偽の命題も導かれてしまう


背理法でPを証明する時、¬Pという偽の命題を仮定しているから
そこから導かれる命題は真にも偽にもなりえてしまう
80: 132人目の素数さん 2013/12/22 17:56:39
んで素数は本当に無限に存在するの?
81: 132人目の素数さん 2013/12/22 18:56:29
無限じゃないなら何個?
82: 132人目の素数さん 2013/12/22 19:46:41
何個あるかわからんから、皆無限個あると思ってるだけ。
86: 132人目の素数さん 2013/12/22 21:34:20
>>82
じゃあ、自然数は全部で何個あると思う?自然数というのは1, 2, 3, 4, 5, ...と続いていく数のこと。

仮に自然数が全部で10個だとすると、自然数は次のものだけということになる。
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
でも、これはおかしい。なぜなら、10に1を加えた11は自然数。それなのに、上のリストに含まれていない。
つまり、自然数が10個だと言うことはできない。

では、自然数が全部で10000個だとするとどうか?このとき、自然数は次のものだけということになる。
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ..., 9998, 9999, 10000.
でも、これはおかしい。なぜなら、10000に1を加えた10001は自然数。それなのに、上のリストに含まれていない。
つまり、自然数が10000個だと言うこともできない。

一般に、自然数が全部でN個だと仮定すると、自然数の全体は
  1, 2, 3, ..., N-2, N-1, N
と表される。しかし、Nに1を加えたN+1は自然数であるのに、上のリストに含まれていない。

つまり、「自然数は全部で△△個だ」と仮定すると、どうしても矛盾が生じてしまうことになる。
このような性質を持つものに対して、我々は”無限個”という呼び方を与えた。
したがって、「自然数は何個あるかわからんから、皆無限個あると思ってる」のではなく、ハッキリと「自然数は”無限個”存在する」ということができる。

「素数は”無限個”存在する」というのも、これと似たような考察によって導かれるのであって、間違っても「何個あるかわからん」から誤魔化しているわけではない。
管理人より:超わかりやすい!数学の先生がこんな風に教えてくれたら管理人も数学好きなバリバリのカッコイイ理系のひとになれたのに!良レスなので特別に色つけちゃう!
87: 132人目の素数さん 2013/12/22 21:53:09
仮に自然数が全部で10個だとすると、自然数は次のものだけということになる。
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
だから10に1を加えた11は自然数ではない。衝撃の事実。
88: 132人目の素数さん 2013/12/22 22:12:48
>>87
もしそうしたいのであれば、自然数が全部で10個しかない体系を作って、そこで好きなようにやってて下さいというのが、普通の数学の立場。

その体系の中では、みんなお金は10円までしか持てない。だってそれ以上あっても数えられないから。
日付を1月1日から1月10日まで数えられたとしても、その後は分からない。
もちろん、年齢も10歳から先は数えられない。
そうなると、「18禁」というような概念が意味を成さなくなる。

それに代わるものを考えようとしても、10までしか数えられない以上は「10禁」にするしかない。
だから、日本では10歳になれば酒もタバコも自由だし、結婚もできる。仮にいかがわしいビデオに出演したとしても咎められない。
……ある意味幸せかもね
93: 132人目の素数さん 2013/12/25 01:43:31
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

すでに広く知られている証明をどや顔で記入するバカ
またはくそつまらないネタをどや顔で記入するバカ

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
95: 132人目の素数さん 2013/12/25 23:18:51
>>93
生温かく見守れ

ハイ、今回もまた素数ネタということで、2回続いてしまってすみませんが、管理人は素数というやつが好きなのです。
ジョジョの奇妙な冒険の第6部に素数好きのプッチ神父というラスボスがいますが、

プッチ神父
落ち着け…心を平静にして考えるんだ…こんな時どうするか…
2…3、5…7…
落ち着くんだ…『素数』を数えて落ち着くんだ…
11…13…17…19……
『素数』は1と自分の数でしか割ることのできない孤独な数字…わたしに勇気を与えてくれる
管理人は、最後の1行をなんと美しい言葉なんだろう、と思っています。誰にも心を許さないプッチ神父の内面をよく表現している。

トップ絵はヴィンチェンゾ・ナタリ監督の、傑作シチュエーションスリラー「CUBE」より。これ以降、あちこちで似たような映画を量産することになるのです。
この映画でも素数がひとつのキーになりますが…、作中で素数の扱われ方がひどいと、一時期話題になりました。
映画CUBEのおかしいとこについて (この記事がけっこうおもしろい)
映画自体は大変よくできています、ので、細かいところを来にしなければ楽しめますヨ!
CUBE キューブ [Blu-ray]
CUBE キューブ [Blu-ray]
posted with amazlet at 14.02.10
ポニーキャニオン (2014-01-08)
売り上げランキング: 2,061
今回のアフィは「ふたつ」あったッッ!!


元スレ:http://uni.2ch.net/test/read.cgi/math/1344483923/

人気サイト様 最新記事

博士ちゃんねる ヘッドライン

    • ※1 : ドクター・ノオ・ネーム
    • 2014.2.12 1:55
    わからないならあんまり無理してまとめるなよ
    • ※2 : ドクター・ノオ・ネーム
    • 2014.2.14 17:07
    >>20はEulerによる証明。分からないことを無理してまとめるから平気で嘘の説明するんだろ。勘弁してくれよ。

    それと√2が無理数の証明のリンク先のものは高校数学の範囲だから、管理人は高校数学も分からないとみてとれる。素因数分解の一意性を利用した証明くらい補っておけ。

    最後に、有限個の素数の総積+1は構成法ではないことくらい、具体例で説明しろ。例えば、2 × 3 × 5 × 7 × 11 × 13 + 1は59 × 509に分解されるから、素数ではない。ただし、左辺2,3,5,7,11,13を「素数を有限個と仮定した場合の(素数の)リスト」とすると、仮に分解できたとしても右辺59,509はそのリストに含まれないという矛盾。
    • ご指摘ありがとうございます。

      ----------
      >分からないことを無理してまとめるから平気で嘘の説明するんだろ。
      どうもスミマセン…
      ----------
      >管理人は高校数学も分からないとみてとれる。
      まぁそんなところです。
      ----------
      >素因数分解の一意性を利用した証明くらい補っておけ。
      追記しておきました。
      ----------
      >有限個の素数の総積+1は構成法ではないことくらい、具体例で説明しろ。
      説明がわかりやすかったので引用させていただきました。
      ----------


      あんまり数学詳しい方の気を悪くさせても仕方ないですし、数学カテゴリーはまとめんのやめましょうかねぇ…。('A`)
    • ※4 : ドクター・ノオ・ネーム
    • 2015.4.19 9:23
    ※2 他人にネットで高圧的な態度をとる人間ってアホが多いってよく言うよね。
    数学の大先生には頭が上がりませんわ笑
  1. トラックバックはまだありません。


コメ欄での議論はおおいにけっこうですが、当サイトではドクター同士の罵り合いは禁止となっております。反論する際には、相手の意見・人格を尊重し、どうぞ冷静に。
*