Sylvester 定理
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.