Erdős proved that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n. An equivalent statement had been proved earlier by Ramanujan (see Ramanujan prime).

Erdős [1] 对 Bertrand 假设给出了一个非常漂亮的初等证明.

Erdős 证明了对任意正整数 $k$, 存在 $N$, 使得对所有 $n>N$, 至少有 $k$ 个素数介于 $n$ 和 $2n$ 之间.

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

[1] P. Erdős, Beweis eines Satzes von Tschebyschef, Acta Sci. Math. (Szeged) 5 (1930–1932), 194–198.

[2] David Galvin, Erd˝os\'s proof of Bertrand\'s postulate. [PDF]

Bertrand 假设的提出是为了置换群的应用的. Sylvester (1814–1897) 将它推广如下:

Sylvester 定理: $k$ 个连续正整数(均大于 $k$)的乘积可被某个大于 $k$ 的素数整除.

换个说法, 设 $n>k$, 则 $n,n+1,\ldots,n+k-1$ 这 $k$ 个数中存在一个数含有大于 $k$ 的素因子.

当 $n=k+1$ 时, 便得到著名的 Chebyshev 定理.

这个定理首先是由 Sylvester 大概于1889年提出并证明的. J. Schur[] 在1929年重新证明了该定理. 后来 Erdos []发现了更初等、更漂亮的证明. 其证明并不需要 Chebyshev 定理的结论.

由于 $n-k+1,n-k+2,\ldots,n-1,n$ 中含有大于 $k$ 的素数因子等价于 $\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 2\cdot 1}$ 中含有大于 $k$ 的素因子. 因此可以把 Sylvester 定理改写为如下形式:

若 $n\geq 2k$, 则 $\binom{n}{k}$ 含有大于 $k$ 的素数因子.

为此, 我们先证明下面的引理.

引理. 若 $\binom{n}{k}$ 可被某个素数 $p$ 的幂 $p^\alpha$ 整除, 则 $p^\alpha\leq n$.

证明参见问题667

若 $\binom{n}{k}$ 不含有大于 $k$ 的素数因子, 则 $\binom{n}{k}\leq n^{\frac{1}{2}k}$. 这是因为可将 $\binom{n}{k}$ 写成素数的乘积形式, 由于其不含有大于 $k$ 的素数, 因此素数分解式至多含有 $\pi(k)$ 项. 形如

\[p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\pi(k)}^{\alpha_{\pi(k)}}\]

根据上面的引理, 诸 $p_i^{\alpha_i}\leq n$, 因此 $\binom{n}{k}\leq n^{\frac{1}{2}k}$. 这里用到了 $\pi(k)<\frac{1}{2}k$, 对 $k\geq 8$.

另一方面,

\[\binom{n}{k}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\frac{n-2}{k-2}\cdots\frac{n-k+1}{1}>\Bigl(\frac{n}{k}\Bigr)^k\]

从而 $\Bigl(\frac{n}{k}\Bigr)^k<n^{\frac{1}{2}k}$, 即 $n^{\frac{1}{2}k}<k^k$. 显然, 当 $k\leq\sqrt{n}$ 时, 这不会成立. 因此对于 $8\leq k\leq\sqrt{n}$ 证明了定理.

作为一个直接推论, 得到:

推论: 若 $n>2$, 则 $\sqrt{n}$ 和 $n$ 之间必存在一素数. (见问题669)

Pf. 上面已经对于 $8\leq k\leq\sqrt{n}$ 证明了 Sylvester 定理. 在此假设下, 注意到 $f(x)=x-\sqrt{x}$ 在 $(1,+\infty)$ 上是单调递增的, 因此 $n-\sqrt{n}\geq k^2-k>k$, 由 Sylvester 定理即得此推论. 对于 $n<64$ 的情形可以简单验证.

由于 Schur 指出当 $k>37$ 时, 有 $\pi(k)<\frac{1}{3}k$. 因此类似于上面的论述, 对于

\[37<k\leq n^{\frac{2}{3}}\]

Sylvester 定理也成立.

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

Paul Erdos, A theorem of Sylvester and Schur. Journal of the London Mathematical Society, Vol.9, Part 4.

J. Schur, Einige Sätze über Primzahlen mit Anwendung auf Irreduzibilitätsfragen. Sitzungsberichte der preussischen Akademie der Wissenschaften, Phys. Math. Klasse, 23 (1929), 1-24.

Bertrand 假设实际上是一个定理.

设整数 $n>3$, 则在开区间 $(n,2n-2)$ 之间至少存在一个素数 $p$.

一个弱一点但更好用的公式是: 对每个 $n>1$, 总存在(至少)一个素数 $p$, 使得介于 $n$ 和 $2n$ 之间, $n<p<2n$.

References:

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

若记 $a_n(k)=1^n+2^n+3^n+\cdots+k^n$, 则熟知有

\[a_1(k)=1+2+3+\cdots+k=\frac{1}{2}k(k+1)\]

• $F_{n-1}\subset F_n$
• $|F_n|=|F_{n-1}|+\varphi(n)$
• 设 $\frac{p}{q},\frac{p'}{q'},\frac{p''}{q''}$ 是 $F_n$ 中连续的三个分数. 则有 \[ p''=\lfloor\frac{q+n}{q'}\rfloor p'-p,\quad q''=\lfloor\frac{q+n}{q'}\rfloor q'-q. \]

$n$ 阶的 Farey 序列是指下述集合

\[ \biggl\{\frac{p}{q}\mid (p,q)=1,1\leqslant p,q\leqslant n\biggr\}\cup\biggr\{\frac{0}{1}\biggr\} \]

按大小排列成的一个序列. 如

\[ F_6=\biggl\{\frac{0}{1},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{1}{1}\biggr\}\]

\[ F_7=\biggl\{\frac{0}{1},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{1}{1}\biggr\} \]

\[ F_{8}=\biggl\{\frac{0}{8},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{1}{1}\biggr\} \]

\[ F_{9}=\biggl\{\frac{0}{9},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{1}{1}\biggr\} \]

\[ F_{10}=\biggl\{\frac{0}{10},\frac{1}{10},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{2}{7},\frac{3}{10},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{7}{10},\frac{5}{7},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{9}{10},\frac{1}{1}\biggr\} \]

\[ F_{11}=\biggl\{\frac{0}{11},\frac{1}{11},\frac{1}{10},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{2}{11},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{3}{11},\frac{2}{7},\frac{3}{10},\frac{1}{3},\frac{4}{11},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{5}{11},\frac{1}{2},\frac{6}{11},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{7}{11},\frac{2}{3},\frac{7}{10},\frac{5}{7},\frac{8}{11},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{9}{11},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{9}{10},\frac{10}{11},\frac{1}{1}\biggr\} \]

\[ n!=\prod_{\text{prime}\ p\leqslant n}p^{\sum_{r=1}^{+\infty}[\frac{n}{p^r}]} \]

于是

\[
v_p(n!)=\sum_{k\geqslant 1}\lfloor\frac{n}{p^k}\rfloor,\quad n\geqslant 1.
\]

这里 $v_p(m)$ 指正整数 $m$ 作素因子分解后, 其中素因子 $p$ 的幂次. 称之为 $p$ 进赋值.

推论: 对任意素数 $p$, 有

\[
\frac{n}{p}-1 < v_p(n!)\leqslant\frac{n}{p}+\frac{n}{p(p-1)}\quad (n\geqslant 1).
\]

References:

G. 特伦鲍姆(Gérald Tenenbaum) 著, 《解析与概率数论导引》,  陈华一  译.

Remark: 

这个公式可以应用于 $n!$ 的快速计算.

算法:

1. 将 $n$ 分解质因数.  $n=p_{1}^{i_1}p_{2}^{i_2}\cdots p_{m}^{i_m}$.

2. 对于 $p_k$, 计算 $d_r:=\lfloor\frac{n}{p_k^r}\rfloor$, 直到 $n < p_k^r$.

3. 求和 $s_k:=d_1+d_2+\cdots+d_r+\cdots$ .  注意这是一个有限和. 当 $n < p_k^r$ 时, $d_r=0$.

4. 最后得到 $n!$

\[
n!=p_1^{s_1}p_2^{s_2}\cdots p_m^{s_m}
\]

PNT(Prime Number Theorem)

\[ \lim_{x\rightarrow\infty}\frac{\pi(x)}{\frac{x}{\log x}}=1. \]

Remark: 这个定理是由勒让得(Legendre)与高斯(Gauss)作为猜测提出的. 直到1896年, 才由法国数学家哈达马(Hadamard)及得拉魏力泊桑(de la Vallée Poussin)同时互相独立地证明. 但是他们的证明中用到复变函数论的深邃理论, 远比契比雪夫（也译为切贝谢夫, 俄文是Чебышёв, [Remark 1] )不等式的证明曲折深奥. 这就推动人们去寻求素数定理的初等的或较简单的证明. 直到1949年, Selberg 及 Erdös 才分别给出了素数定理的初等证明.

素数定理有很多的初等证明, 但是其价值可能没有现代证明来得优美和深刻.

http://www.cnblogs.com/misaka01034/p/WeakPrimeThm.html

Euler (1740) 观察到

\[
\sum_{n=1}^{+\infty}n^{-\sigma}=\prod_{p}(1+p^{-\sigma}+p^{-2\sigma}+\cdots)=\prod_{p}(1-p^{-\sigma})^{-1}
\]

第二个等号是显然的. 第一个等号可以这样理解, 对于每个正整数 $n$, 根据算术基本定理(the Fundamental Theorem of Arithmetic)可表示为 $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, 于是

\[
n^{-\sigma}=(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k})^{-\sigma}=p_1^{-a_1\sigma}p_2^{-a_2\sigma}\cdots p_k^{-a_k\sigma}.
\]

这是由 $(1+p_1^{-\sigma}+p_1^{-2\sigma}+\cdots)$, $(1+p_2^{-\sigma}+p_2^{-2\sigma}+\cdots)$, $\ldots$, $(1+p_k^{-\sigma}+p_k^{-2\sigma}+\cdots)$ 中的项相乘得到的. 反之, $\prod_{p}(1+p^{-\sigma}+p^{-2\sigma}+\cdots)$ 展开后, 成为一系列项的和, 除 1 之外, 每个项形如 $p_1^{-a_1\sigma}p_2^{-a_2\sigma}\cdots p_k^{-a_k\sigma}$. 因此第一个等号成立.

利用这个等式, Euler 给出了素数个数是无穷的新证明. 假设素数个数是有限的, 则

\[
\zeta(\sigma)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma}}=\prod_{p}\frac{1}{1-p^{-\sigma}}
\]

在 $\sigma\rightarrow 1^+$ 时仍是有界的, 但此时 $\sum_{n=1}^{\infty}\frac{1}{n^{\sigma}}$ 趋于无穷大.

粗略地说, $\zeta(\sigma)$ 的行为代表了素数的行为.

1790's, Gauss 和 Legendre 独立猜测下面的 PNT

\[
\pi(x)=\sum_{p\leqslant x}1\sim\frac{x}{\log x},\quad(x\rightarrow\infty)
\]

若记

\[
\Lambda(n)=\begin{cases}
\log p, & n=p^k,\\
0, & \text{其他}
\end{cases}
\]

则 PNT 等价地可以叙述为

\[
\psi(x):=\sum_{n\leqslant x}\Lambda(n)\sim x
\]

这里我们可以这样思考

\[
\psi(x)=\sum_{n\leqslant x}\Lambda(n)=\sum_{n=p^k\leqslant x}\log p=(\log x)\sum_{n=p^k\leqslant x}\frac{\log p}{\log x}=(\log x)\sum_{p\leqslant x}\frac{k\log p}{\log x}\sim(\log x)\sum_{p\leqslant x}1.
\]

Reference:

闵嗣鹤、严士健编《初等数论》（第二版），高等教育出版社.

Remark:

[1] 据张影老师介绍，Чебышёв 应该译为切比绍夫比较合适.