こんにちは。鶴崎です。
今日のテーマは「証明問題」です。
みなさんも中学や高校の数学の時間で、証明問題を経験しているはずですが、覚えてますか？
ざっくり言えば「理由を説明する問題」のことですね。
今回は特に数学が苦手だった方向けに、簡単な証明問題を通して、数学ができる感触を味わってもらいたいと思っています。
さて、今回の問題は
「素数が無限個存在することを証明せよ。」
です。
これは、古代ギリシアの時代、数学者ユークリッドの著書『原論』ですでに証明されている、伝統ある問題です。
『原論』での証明を少し改良したものがよく知られているので、それにのっとって証明していきます。
まずは問題を整理します。
今回の主役、「素数」ですが、これは「1とその数自身以外に約数をもたない自然数」のことです。（約数は正のものしか考えないことにします。）
例えば7は、1と7以外の整数で割り切れないので、素数です。9は3で割り切れるので、素数ではありません。例外として、1は素数には入れません。
これが無限個あるというのが、今回の主張です。「無限個」というのは、「何個素数を集めてもまだ別の素数がある」という意味に考えるとスッキリするかもしれません。
証明の考え方としては大きく2通り。
一つ目は、「無限個の素数の作り方を直接説明する」です。一見無理そうですが、実際に作るわけではなく、作り方を説明するだけなので、普通にできます。
「無限個の団子を作れ」と言われたら無理ですが、「無限個の団子の作り方を説明しろ」と言われたら、団子の作り方を説明したあと、「これをずっと繰り返せばいいです」といえばいいわけですね。
こういう方法を使った簡潔な証明もいくつかあるのですが、少し進んだ知識を使うので、今回はやめておきます。
無限個のお団子を作る？二つ目は、「素数が有限個しかなかったらおかしいことを説明する」です。今回はこちらを採用します。
このような証明の方法を「背理法」といいます。
背理法は、推理ドラマのアリバイ探しに似ています。
AさんとBさんのどちらかが事件の犯人だとして、Aさんは犯行時刻にバイトをしていたというアリバイが見つかります。
Aさんが犯人なら、バイト先と現場に同時に存在することになっておかしい！ だからBさんが犯人だ！ という寸法ですね。
このとき、Bさんが犯人だという証拠を何も出さずとも、Bさんが犯人であることがわかりました。
Bさん、あなたが犯人です！実際の事件の捜査ではあまり好ましくないですが、数学では強力なツールとして使えます。
というわけで、「素数が有限個しかない」としておかしなことが起こることを示します。
まずは、有限個の素数を全部集めて、名前をつけることにします。
a,b,c,……だとzまで行って足りなくなるかもしれないので、p1,p2,p3,……（pは素数を表す英語prime numberのpです）と数字で名前をつけます。
素数が全部でn個だとして、pnまで名前をつけ終わりました。
さて、ここから矛盾を導くためには、あるものを探せばいいのですが、それは何でしょうか？ ちょっと考えてみてください。
次ページ：2~3分考えて分からなかったら答えを見ちゃいましょう(1/2)。
