素数は無限個存在することのサイダックによる証明

まず準備として、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) となって、矛盾である。なぜならば、上式の左辺は1で、右辺はaの倍数だからである。 いま、nを2以上の整数として、nの素因数(nを割り切る素数)pをとる。 次に準備として述べた性質から、nとn+1は互いに素なので、n+1の素因数qを考えると、qはnの素因数pとは異なる。 次に準備として述べた性質から、 n×(n+1)とn×(n+1)+1 は互いに素なので、n×(n+1)+1の素因数rはn×(n+1)の素因数p、qとは異なる。 次に準備として述べた性質から、 {n×(n+1)}×{n×(n+1)+1}と {n×(n+1)}×{n×(n+1)+1}+1 は互いに素なので、{n×(n+1)}×{n×(n+1)+1}+1の素因数sは {n×(n+1)}×{n×(n+1)+1}の素因数p、q、r、とは異なる。 以下、同様な議論を続けることによって、素数は無限個存在することが分かる。 (証明終わり)