被疑者A氏はその時間に犯行現場付近にいませんでした!?犯人捜査から素数の個数まで…矛盾を導くことで証明する「背理法」の簡単な考え方
次の話の嘘を見破れ！
50人参加したあるパーティーについて、ある人は次のように話した。 50人のうちの23人は「自分はちょうど20人と知り合いの関係がある」と言っている。また、残りの27人は「自分はちょうど15人と知り合いの関係がある」と言っている。 嘘がある理由を述べると、各人が知っている人数の全員ぶんの合計を計算すると、 20×23+15×27=460+405=865 となって、これは奇数である。よって、「性質」によって矛盾である。すなわち、ある人の話には嘘がある。 これも立派な背理法である。
「背理法の証明」に違和感を覚える人は
上で述べてきたことから想像できるかも知れないが、背理法は有限個の世界ではよく使われる証明法である。それゆえ「離散数学」という分野では本質的によく現れる。 しかし、数学者の中にも「背理法の証明は感じ悪い」と思う人がいるように、違和感をもつ人は少なくない。できることならば同じ定理でも、背理法でない証明法が期待されるだろう。 この一例として「2,3,5,7,11,…と続く素数(1とそれ自身でしか割り切れない2以上の整数)は無限個ある」という定理に関して述べよう。 紀元前300年ごろのギリシャの数学者ユークリッドは、素数は無限個存在することを証明した。 その証明法は、「素数は有限個しかない」として矛盾を導く背理法によるものであった。
素数は無限に存在することを証明する
その後、素数は無限個あることの証明はいくつか発見されたが、どれも簡単なものではなかった。ところが2006年に、サイダックという数学者が非常に分かり易い証明を発表し、以下、この証明法を紹介して本稿は終りとする(拙著『昔は解けたのに……大人のための算数力講義』に掲載)。 まず言葉の準備として、正の整数aとbの公約数とは、aとb両方の約数のことである。aとbの公約数となる正の整数が1しかないとき、aとbは互いに素という。たとえば、12と18の公約数となる自然数は1と2と3と6で、12と35は互いに素である。
