サイダックが証明した「無限個の素数の存在」
紀元前300年頃のギリシャの数学者ユークリッドは、素数は無限個存在することを証明した。その証明法は、「素数は有限個しかない」として矛盾を導く背理法によるものであった。
その後、素数は無限個あることの証明はいくつか発見されたが、どれも簡単なものではなかった。
ところが2006年に、サイダックという数学者が非常に分かりやすい証明を発表した。次に、この証明法を紹介しよう。
言葉の準備として、自然数aとbの公約数とは、aとb両方の約数のことである。aとbの公約数となる自然数が1しかないとき、aとbは互いに素という。たとえば、12と18の公約数となる自然数は1と2と3と6で、12と35は互いに素である。
サイダックによる証明
まず、2以上の任意の自然数mに対し、mとm+1は互いに素、すなわちmとm+1は1以外の公約数はないことを示す。なぜならば、もしmとm+1が2以上の公約数aをもつならば、
m=a×b, m+1=a×c
となる自然数bとcがある(b<c)。
よって
(m+1)ーm=a×c-a×b=a×(c-b)
1=a×(c-b)≧a
aは2以上なので、 これは矛盾である。