INTEGERS

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

Golombの定理

定理解説

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

証明に使うのは $\displaystyle \lim_{x \to \infty}\frac{\pi(x)}{x}=0$ –①のみです。これは素数定理から出ますが、素数定理を用いることなく初等的に導出できる点には注意しておきます*1。 $p_n$ は $n$ 番目の素数を表します。

定理 (Golomb, 1962) $m$ を $2$ 以上の任意の整数とする。このとき、或る $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.

*1:記事を書きました： integers.hatenablog.com