切比雪夫定理

**伯特蘭 - 切比雪夫定理**說明：若整數 $n>3$ ，則至少存在一個質數 $p$ ，符合 $n<p<2n-2$ 。另一個稍弱說法是：對於所有大於 1 的整數 $n$ ，存在一個質數 $p$ ，符合 $n<p<2n$ 。

1845 年約瑟・伯特蘭提出這個猜想。伯特蘭檢查了 2 至 3×106 之間的所有數。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