先日、親戚に頼まれて、高校生(1年)の勉強の面倒を見る機会がありました。数学見てくれと言われ、その時やっていた背理法のところを解説していたのですが……。

彼の通っている学校の先生が作ったプリントを見て、「おう……」となりました。

背理法の具体例として、「素数が無数にある」という証明が書かれていたんですね。こんなやつです。

  1. 素数が有限個である、と仮定する。
  2. 有限な素数の最大値をPとする。
  3. Pまでの素数の積をMとする。(2x3x5x……xP=M)
  4. Mは全ての素数で割り切れる数であるから、M+1は素数である。
  5. しかし、最大の素数Pより大きな素数(M+1)が存在するため、「素数は有限」という命題は偽。 
  6. よって、素数は無限である。
いわゆるユークリッドの背理法です。実はこれにはちょっと懐かしい思い出がありまして。

皆さん、上の証明を見てどう思われます?

学生だったころ、私には、4の部分がわからなかった。「M+1は素数」という部分が、証明として微妙にコケてるように見えたんです。ちょっとやればわかるんで確認しましょうか。

2x3x5x7x11x13=30030 (2~13までの素数をかけました)
30030+1=30031 (その結果に1を足しました)
59x509=30031

というわけで、30031は素数ではありません。

どうして「Mは全ての素数で割り切れる数であるから、M+1は素数」なんだろう? 先生に訊ねたら、「素数で割り切れる数に1を足してるんだから当然だろう」みたいな答えが返ってきた。はあ、そんなものかと思ったんですが、上のことに気づいたので突っ込んだんですね。すると、詳しく説明をしてくれました。

その時の説明は、こんな具合。(ちゃんとした内容は忘れましたが、おおまかに)
証明過程「2」の時点で、素数というのは2~Pまでとされている。「素因数分解」ということばがあるように、2以上の自然数は素数の積によってあらわされる。したがって、どんな素数で割っても1余る「M+1」という自然数は(それまでの素数の積によってあらわせないので)素数と考えるしかない。(もちろん、これは「偽」なのだけれど)
なるほどね~という感じです。30031は、確かに59と509という、2つの素数の積によってあらわすことができますが、最初にP(最大の素数)を13としている以上、13より大きな素数は存在しないはずです。なので、59や509という素数が存在することは「おかしい」わけで、そのことをもって「素数が有限個である」という仮定はおかしいと言ってしまえるわけですね。

ちなみに、本家ユークリッドの考えたもともとの証明を確認すると、この辺りはもうすこし分かりやすいものでした。

ユークリッドが『原論』の中で述べているのは、だいたい次のような感じです。

まず、「M+1」は素数か素数でないかのどちらかである、と場合分けをする。
  (1)M+1が素数なら、Pより大きい素数が存在することになる。
  (2)M+1が素数でないなら、M+1を割り切る素数Xが存在する。
(1)の場合、端的に仮定は偽です。(2)の場合、MはPまでのあらゆる素数で割り切ることができるため、Pまでの素数の中に、M+1を割り切れる素数は存在しない。したがって、M+1を割り切れる素数XはPより大きい、とこうことになり、やはり仮定命題は偽ということになりますね。

このようにユークリッド自身はどうやら、「M+1は素数だ」とは言っていないっぽいのですが(単に訳の問題かもしれません)、そこを簡略化していくうちに、「M+1は素数だ」のような言い方になったのではないかと想像しています。

たぶん、下に挙げた説明が非常に簡潔。OKWaveの方は、「ここで,Qは素数と決め付けることはできない」というひとことがさらっと添えられているのがにくいですね。

 ▼「素数が無限にあることの証明」(OKWave)
 ▼「素数が無限にあることは、どうやって証明できるのでしょうか?」(Yahoo!知恵袋)





ともあれ、こういう「証明」を紹介したのは単に私の先生の趣味だと思っていたんですが、21世紀になった現代でもこれを教えている先生がいるあたり、どうやらそうではないんですかね。ちょっとグーグル検索かけてみると、やっぱりこの証明は有名みたいで、あちこちで見かけました。

 ▼「素数は無限にあることの証明
 ▼「ユークリッドの素数無限の証明」(リーマン予想の研究)
 ▼「もっと数学の世界 第15回・背理法」(教育開発ONLINE)

ただ、ここで怖いのは、「M+1」のように、一定の連続する素数の積に1を加えたものは、いついかなるときも必ず素数だ、という考え方になることです。これは端的に誤解なのですが、実際、「M+1は《必ず》素数」のような言い方になってしまっているものが見受けられます(たとえば、こちら)。

素数が無限個であることの背理法による証明でですね。


まず素数が無限個であることを否定、素数が有限個n個しかない

と仮定。


その素数をp1、p2、p3、p4・・・・pnとおく。これら全てを掛け合わせる。

さらに1加えた数を考え、それをAとおく、

A=p1×p2×・・・×pn+1


ここで質問です。

1ってどこから出てきた1です?そして何故1をたすのです?

そして何故p1×p2×・・・pnとかけるのですか?

対するベストアンサーが、これ。

1はp1からpnのすべての数と異なる数でそれらの数より小さいからです。
「aをbで割った商がq、余りがr」 ⇔ a=bq+r (0≦r<b)
と言う関係から
p1からpnのどの数で割っても余りが1になることをいえるからです

具体例
今、素数が2、3,5しかなかったとします。
2×3×5+1(=31になりますが)
これは2でわると1余ります
また3でわると1余ります。
また5でわると1余ります

(もし、+1でなく+2だったら2でわったとき余りが0になってしまいます。)
31は2でも3でも5でもわりきれない。すなわち、すべての素数で割れません。
つまり、割りきれる数がありません。合成数でないことになります。
合成数ではないつまり素数であり、31は2でも3でも5でもない新たな素数になります。
(なぜ、2と3と5をかけるのか。それは何でも良いから新しい素数を作りたいからです。5の次の素数は7だけど、順番に探したいのではないのです。作ることのできる新しい素数として31なのです)

すみません、専門的な言葉を使うので大学生と思ってしまいました。小学生としてはとてもよく勉強しているし、とても良い疑問の持ち方だと思います。これからもがんばってください。これだけのことを考えられるので計算問題をしっかり解くことをして土台を固めれば、いろんな理屈もわかるようになりますよ
 

この回答者の中
に私やjusogyoshiki_yakubunyozei さんの回答を真似ている人がいます。私や jusogyoshiki_yakubunyozei さんの補足をすると一言入れてほしいです。また、
質問者様、あるいは投票者様にはそのような人にBAを出さないでくださいますようお願いいたします。

この時点で結構きわどいかなと思いますが、下の方にあるjusogyosikiさんとやらの答えを見てみると……。

素数の定義は理解されておりますでしょうか?
1と自身でしか割り切ることができない数を素数と言います。
p1×p2×・・・×pn
という数は、
p1でも割り切れるし、p2でも割り切れるし、
p1×p2でも、p3×p103×p2×・・・でも割り切れるし、
p1~pnまでの素数の積で表される全ての数で割り切れます。
全然素数じゃありません。

これに、たった1を加えるだけで、
ほかのどんな数でも割り切れなくなるのですよ。

うーん、「ほかのどんな数でも」のように言ってしまっていますね。この書き方だとやはり、実際に「M+1は《必ず》素数」であるという誤解を招くように思います。そんな証明で大丈夫か? と言いたくなる私の気持ちをわかって頂けるでしょうか……。

さっきも言いましたが、B=30031になることがあり、それは素数ではありませんでした。「M+1」が素数になるというのは、あくまで最大素数Pをおいた場合の論理的帰結であり、現実にはPより大きな素数があるわけですから、「M+1」は素数であるとは限らない。それらしいことを言っているように見えるけど、やっぱりちゃんとした証明になってない、あるいは説明不足ように思われます。そこへもってきて、この上から目線のコメントが絶妙な侘び寂び感を醸しだしていてなんとも言えない微妙な気持ちになります。

知恵袋の名誉のためにことわっておくと、こういうアンサーをしているのも見かけました(こちら)。これは分かりやすくて良いですね。きちんと場合分けされていて。

仮に素数を有限個だと考えて、その最大の素数をNとします
すると素数は 2、3、5、7、11、・・・・・・・・・・・、N これで全てです

次にこの素数を全部掛け合わせた数をAとします
A=2×3×5×7×11×・・・・・・・・×N
この数Aは成り立ちから分かる通り、どの素数で割ってもキチンと割り切れます

次にAに1を足した数をBとします
B=(2×3×5×7×11×・・・・・・・・×N)+1

するとBは2からNまでのどの素数で割っても1余ります。言葉を変えると
最小の素数2から最大の素数Nまでのどの素数でも割り切れない数です

このことから考えられる事は2つ、これはB自体が素数であるか、BがN以上の未知の素数で
割り切れるかどちらかであることを示しています 



おそらく、このような背理法の説明を受けた人の中には、「M+1」は常に素数である、と勘違いしていた人が多いのではないでしょうか(実際、今回教えた私の親戚もそう考えていたようです)。

まあぶっちゃけ、「M+1は素数」っていうふうにさらっと言っちゃうのが悪いと思っています。「自然数は素数の積で表現される」という別の前提が入ってきていますから、ここはもっと力を入れて説明してほしいというか……。また、聞く側の問題というのもあって、こういう論理的な話って、「なんとなくわかったつもり」で済ませちゃうことが多いんですよね。頭がついていかなくなって。私なんかその典型。

しかし、そのところをちゃんと考えておかないと、中途半端なへっぽこ論理になってしまうし、下手をすると気づかず終わってしまう。それはとても怖いことだなぁと思う次第です。