インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

Golombの定理

素数個数関数\pi (x)に関するGolombの定理を紹介します。

証明に使うのは\displaystyle \lim_{x \to \infty}\frac{\pi(x)}{x}=0 –①のみです。これは素数定理から出ますが、素数定理を用いることなく初等的に導出できる点には注意しておきます。Golomb曰く、Eulerが既に示していたとのことです。Euler先生は何でもやってます。p_nn番目の素数を表します。

定理 (Golomb, 1962) m2以上の任意の整数とする。このとき、或る2以上の整数nが存在して、n\pi(n)の丁度m倍になる。

証明. 2以上の整数mを固定して、nの存在を示す。①より、kが十分大きければ

\displaystyle \frac{\pi(p_k)}{p_k} < \frac{1}{m}

となり、\displaystyle \frac{\pi (2)}{2} = \frac{1}{2} \geq \frac{1}{m}なので、

\displaystyle \frac{\pi(p_k)}{p_k} \geq \frac{1}{m}

が成り立つような最大の整数kが存在する。それをKとしよう。このとき、mK < p_{K+1}が成り立つ。というのも、もしmK \geq p_{K+1}であったと仮定すると、

\displaystyle \frac{\pi(p_{K+1})}{p_{K+1}} = \frac{K+1}{p_{K+1}} > \frac{K}{mK}=\frac{1}{m}

となってKの最大性に反するからである。よって、mK < p_{K+1}であり、Kの取り方からp_K \leq mKなので

\pi(p_K) \leq \pi (mK) < \pi(p_{K+1})

を得る。これは\pi(mK)=Kを意味し、

\displaystyle \frac{mK}{\pi(mK)} = m

が成り立つ。すなわち、n=mKと取れる。 Q.E.D.