素数個数関数に関するGolombの定理を紹介します。
証明に使うのは –①のみです。これは素数定理から出ますが、素数定理を用いることなく初等的に導出できる点には注意しておきます*1。は番目の素数を表します。
定理 (Golomb, 1962) を以上の任意の整数とする。このとき、或る以上の整数が存在して、はの丁度倍になる。
証明. 以上の整数を固定して、の存在を示す。①より、が十分大きければ
となり、なので、
が成り立つような最大の整数が存在する。それをとしよう。このとき、が成り立つ。というのも、もしであったと仮定すると、
となっての最大性に反するからである。よって、であり、の取り方からなので
を得る。これはを意味し、
が成り立つ。すなわち、と取れる。 Q.E.D.
*1:記事を書きました: integers.hatenablog.com