伯特兰-切比雪夫定理

提示：此条目页的主题不是伯特兰定理。

伯特兰-切比雪夫定理说明：若整数$n>3$，则至少存在一个质数$p$，符合$n<p<2n-2$。另一个稍弱说法是：对于所有大于1的整数$n$，存在一个质数$p$，符合$n<p<2n$。

1845年约瑟·伯特兰提出这个猜想。伯特兰检查了2至3×10⁶之间的所有数。1850年切比雪夫证明了这个猜想。拉马努金给出较简单的证明，而埃尔德什则借二项式系数给出了另一个简单的证明。

相关定理

西尔维斯特定理

詹姆斯·约瑟夫·西尔维斯特证明：$k$个大于$k$的连续整数之积，是一个大于$k$的质数的倍数。

埃尔德什定理

埃尔德什证明：对于任意正整数$k$，存在正整数$N$使得对于所有$n>N$，$n$和$2n$之间有$k$个质数。

他又证明$k=2$、$N=6$时，而且有，其中两个质数分别是4的倍数加1，4的倍数减1。

根据质数定理，$n$和$2n$之间的质数数目大约是$n \over \ln(n)$。

证明

证明的方法是运用反证法，反设定理不成立，然后用两种方法估计${2n \choose n}$的上下界，得出矛盾的不等式

注：下面的证明中，都假设$p$属于质数集。

不等式1

这条不等式是关于${2n \choose n}$的下界的。

• 对于正整数$n$，${2n \choose n}\geq {\frac {4^{n}}{2n}}$

证明 ：

对于 $k\leq 2n$ ， ${2n \choose n}\geq {2n \choose k}$

若$k\neq n$，${2n \choose n}>{2n \choose k}$

因此$2n{2n \choose n}\geq \sum _{i=1}^{2n}{2n \choose i}+1=2^{2n}=4^{n}$

引理1

• $\prod _{k+1<p\leq 2k+1}p\ <4^{k}$

证明： 注意到所有大于 k+1 而小于 2k+1 的质数都在(2k+1)! 中而不在(k+1)! 或 k！ 中，于是$\prod _{k+1<p\leq 2k+1}p$ 是${{2k+1} \choose {k+1}}$的因子。

$\prod _{k+1<p\leq 2k+1}p\quad \left\vert \ {{2k+1} \choose {k+1}}\right.$

同时又有 $2{{2k+1} \choose {k+1}}={{2k+1} \choose {k+1}}+{{2k+1} \choose {k}}<\sum _{i=0}^{2k+1}{{2k+1} \choose {i}}=2\cdot 4^{k}$

于是就有 $\prod _{k+1<p\leq 2k+1}p\ \ \leq {{2k+1} \choose {k+1}}<4^{k}$

定理1

这个定理和${2n \choose n}$的上界有关。

• 对于所有正整数$n$， $\prod _{p\leq n}p<4^{n}$

数学归纳法：

当$n=2$，2 < 16，成立。

假设对于所有少于$n$的整数，叙述都成立。

显然，若n>2且n是偶数，$\prod _{p\leq n}p=\prod _{p\leq n-1}p$。对于奇数的n，设n=2k+1。

从引理1和归纳假设可得：

$\prod _{p\leq n}p=\prod _{p\leq 2k+1}p=\prod _{p\leq k+1}p\cdot \prod _{k+1<p\leq 2k+1}p<4^{k+1}\cdot 4^{k}=4^{2k+1}=4^{n}$

系理1

首先的定理：

• 若$p$是质数，$n$是整数。设$s$是最大的整数使得$p^{s}|n!$ ，则$s=\sum _{i=1}^{\infty }{\lbrack {\frac {n}{p^{i}}}\rbrack }$

下面这些系理和${2n \choose n}$的上界有关。

若$p$为质数，设$s_{p}$是最大的整数使得 $p^{s_{p}}$ 整除 ${2n \choose n}$，则：

$s_{p}=\sum _{i\geq 1}{(\lbrack {\frac {2n}{p^{i}}}\rbrack -2\lbrack {\frac {n}{p^{i}}}\rbrack )}$

对于所有$x>0$，$\lbrack 2x\rbrack -2\lbrack x\rbrack \leq 1$ ，所以

$s_{p}=\sum _{i\geq 1}{(\lbrack {\frac {2n}{p^{i}}}\rbrack -2\lbrack {\frac {n}{p^{i}}}\rbrack )}\leq max\left\{r|p^{r}\leq 2n\right\}$

于是得到三个上界：

1. $p^{s_{p}}\leq 2n$
2. 若 ${\sqrt {2n}}<p$ ， $s_{p}\leq 1$
3. 若 $2n/3<p\leq n$，$s_{p}=0$（因为 2n! 中只有两个 p，在 n! 中恰有一个 p）

核心部分

假设存在大于1的正整数$n$，使得没有质数$p$符合$n<p<2n$。根据系理1.2和1.3：

${2n \choose n}=\prod _{p\leq 2n}p^{s_{p}}=\prod _{p\leq 2n/3}p^{s_{p}}\leq \prod _{p\leq {\sqrt {2n}}}p^{s_{p}-1}\cdot \prod _{p\leq 2n/3}p$

再根据系理1.1和定理1： ${2n \choose n}\leq$ 上式最右方 $<(2n)^{{\sqrt {2n}}/2-1}\cdot 4^{2n/3}$

结合之前关于$2n \choose n$的下界的不等式1：

$(2n)^{-1}4^{n}<{2n \choose n}<(2n)^{{\sqrt {2n}}/2-1}\cdot 4^{2n/3}$

$4^{n}<(2n)^{{\sqrt {2n}}/2}\cdot 4^{2n/3}$

$4^{2n/3}<(2n)^{\sqrt {2n}}$

两边取2的对数，并设$x={\sqrt {2n}}$：

$x\ln 2-3\ln x<0$。

显然$x\geq 16$，即$n\geq 128$时，此式不成立，得出矛盾。 因此$n\geq 128$时，伯特兰—切比雪夫定理成立。

再在$n<128$时验证这个假设即可。

参考

• A simple proof of Bertrand's Postulate, Neil Lyall
• Number Theory. Tutorial 5: Bertrand's Postulate

外部链接

• Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate（页面存档备份，存于互联网档案馆）, Lawrence E. Greenfield