素数が無限にあることの証明に注意

登場人物
慈道
数学科の大学院生.男.コミュ障.
柴山
数学科の大学生.女.教職を目指しているらしい.

「素数が無限に存在することはユークリッドが既に証明している.知っているか?」

「有名なやつですよね.まず素数が有限個だとして,それら全体をp1,p2,,pnとします.このときP=p1p2pn+1なる自然数を考えると,Pp1,p2,,pnで割り切れないので,Pは素数になります.しかし,Pはどのpiよりも大きいので,素数全体がp1,p2,,pnであることに矛盾します.よって,素数は無限に存在します」

「Wikipedia?」

「え,どうだったかな……なんとなく記憶に残っていた証明なんですが.なにか問題あります?」

Pp1,p2,,pnで割り切れないから,Pは素数,とお前は言ったが端折り過ぎだ.もっと詳しく説明をしてくれよ」

「えー.だって,Pはすべての素数で割り切れない数なんだから,Pは素数じゃないですか」

「結構滅茶苦茶なこと言ってるぞ.集合全体の集合は集合,みたいな」

「確かに自分で言ってておかしい気がしました」

「そもそも素数の定義はなんだ」

1と自分自身以外に正の約数をもたない,1より大きな整数です」

「そうだな.だったら,Pが素数かどうかをいうには,1P以外に正の約数をもたないことを示すのが筋だろ.言葉ではなく論理で説明せい」

「それじゃあ,1P以外に正の約数dをもったとします」

「また背理法か」

d1より大きいので,dを割り切る素数がp1,p2,,pnのどれかに存在します.それをpiとします.Pnで割り切れ,npiで割り切れるということは,Ppiで割り切れます.しかし,これはPpiで割り切れないことに矛盾します.よって,P1P以外の正の約数はありません.よってPは素数です.しかし,これはp1,p2,,pnがすべての素数であることに矛盾します.よって素数は無限に存在します」

「なるほど.そういう説明だったら俺も納得しよう.しかし,少しばかり回り道をしているな.柴山の証明の肝心な所は,1より大きい整数dを割り切る素数pが必ず存在することだ.これは極めて当たり前だが証明は必要.しかし,この事実を認めてしまえば,正の約数dなどと言わずに初めからPを割り切る素数piが存在するが,それはPの構成法に矛盾する,で終わりだ」

「あー,ちょっと整理させてくださいよ.最初から戻りますけど,素数が有限個だとして,それらをp1,p2,,pnとしますよね.そしてP=p1p2pn+1とします.P>1よりPを割り切る素数pi(1in)が存在しますが,Pの表示式より,piでは割り切れないので矛盾,ということですか」

「そういうこと.次に俺が言いたいことは分かるか?」

「……Pが素数だから矛盾って議論はもしかして必要ない?」

「ああ.俺はそう思うね.色々な場面でP=p1p2pn+1が素数だから矛盾っていう書き方を見るが,なぜそれが素数なのかどうかを詳しく説明してる人はあまりいない.もともとおかしな仮定で話を進めているから,Pが素数かどうかはうやむやになる.また,こういった説明が氾濫することによって,有限個の素数をかけて1を足せばそれが必ず素数になっていると勘違いしている人が現われるほどだ.こういった面から背理法は害だという人もいる」

「精読し切れていないことの弊害ですね.先輩が大衆批判をするときの切り口」

「人聞きの悪いことを言うなよ.まあ,確かに証明を骨の髄まで理解しようと心掛けていれば,誤解することもないのだがな.ちなみにユークリッドは背理法で証明するのではなく,有限個の素数から新たな素数を見出す方法をとっているらしい.完全にユークリッドの証明と同じかは知らないが,だいたい次のような流れだ.p1,p2,,pnを相異なる素数とするとき,P=p1p2pn+1とおくと,各piPを割り切らない.ここで,Pを割り切る素数をpとすれば,こいつはPを割り切らないpiとは異なる素数であるので,n+1 個目の素数が出てくる」

「有限個の素数から,新しい素数を構成できる……つまり素数は無限である,と.どっちの証明でも,1より大きな整数を割り切る素数pが存在することが重要ですね」

「その通り.しかし,これがいえたから本当に素数が無限に存在するといえるのだろうか……」

「まだ納得がいかないんですか.だって,素数全体の集合が有限だとしたら,今の先輩の証明で矛盾が起こるじゃないですか.あ……」

「結局背理法頼りか.最初,ユークリッドの証明は背理法を用いないといっているわりに,最後の最後で背理法使っちゃってるよな.別に背理法を用いることに異論はまったくないが,世の中には背理法を毛嫌いする人もいてな」

「ああ,Wikipediaに書いてありますね.

ユークリッドは,背理法で素数が無数にあることを証明した(中略)などの誤解をする者がいるが,いずれも正しくない

ですって」

「有限個の素数から新たな素数を構成できるから素数は無限に存在するという議論は,素朴な理解であって,現代数学の集合論的な理解ではない気がするよね」

「本当に面倒くさい人ですよね,先輩は」

「なんとでも言え.集合論的に素数が無限にあることを言い換えよう.『Aが素数全体の集合ならばAは無限集合である』これを示せば,素数は無限にあるよな」

「ええ」

「で,これの対偶をとると,Aが有限集合ならばAは素数全体の集合ではない,となる.これの証明は容易い.Aに素数が1つもなければ,Aは素数全体の集合ではない.Aに素数が少なくとも1つ存在するとき,Aは有限集合だから,Aに属する素数全体はまた有限であり,それらをp1,p2,,pnとする.ユークリッドの方法より,これらとは相異なる素数pが存在し,それはAに属さない.よって,Aは素数全体の集合ではない」

「でも,個人的には背理法の方がシンプルな気がしますね」

「まあ,人それぞれだね.もっと簡単な直説法があったら教えてくれ」

「あとで私も考えてみまーす」

コメントする