この記事は,この記事の著者であるナンブキトラのはてなブログ記事(参考文献XND)をMathlog用に書き直したものである.
この記事では素数の無限性を証明する.
本文
まず最初に合成数や素数の定義を確認しておく.
とする.となるが存在するときにはの約数という.が素数であるとはであり尚且つがと自分自身以外の正の約数を持たないときにいう.の素因数とは素数でありを割り切れる数のことである.そしてに対してを満たすが存在してを満たすならばを合成数と呼ぶ.
合成数の定義から次がわかる.証明は省略する.
が合成数であることとで尚且つが素数でないことは同値である.
次により大きい整数が必ず素因数を持つことを自然数の整列性から導こう.
まず集合を
と定義する.証明したい命題はと同値である.背理法によって証明する.今と仮定するとの最小元が存在する.そこでと置く.今なのでであり,なおかつは素数ではない.よって
命題1
よりは合成数である.ゆえに を満たすを用いてと書ける.数のにおける最小性からでなければならない.よっては素因数を持つ.するとなのでも素因数を持つことになり,に矛盾する.
最後にこの記事の主定理を証明する.
任意のに対してそれよりも大きい素数が存在することを言えば良い.
をからまでの間の自然数の積とする.つまり階乗のことである.このときは
命題2
より素因数を持つ.その素因数の一つをとする.なので,もしもがの約数だとするとはを割り切ることになりとなる.これはが素数であることに矛盾する.よってはの約数ではない.するとの定義からがわかり,より大きい素数の存在がわかった.
注釈
ここで与えた証明は練習用にはちょうど良い原稿量であるが,新規性のあるものではないだろう.実際,この記事の証明はSaidakSaidakによる証明とほぼ同じであると思われる.この記事での証明のポイントはとが互いに素であることとユークリッドの証明よろしく階乗を用いるところである.