查看“︁伯特蘭-切比雪夫定理”︁的源代码

{{Distinguish|伯特蘭定理}}
{{noteTA
|2=zh-hans:埃尔德什; zh-hant:艾狄胥;
}}
'''伯特蘭-切比雪夫定理'''說明：若[[整數]]<math>n>3</math>，則至少存在一個[[質數]]<math>p</math>，符合<math>n<p<2n-2</math>。另一個稍弱說法是：對於所有大於1的整數<math>n</math>，存在一個質數<math>p</math>，符合<math>n<p<2n</math>。

1845年[[約瑟·伯特蘭]]提出這個[[猜想]]。伯特蘭檢查了2至3&times;10<sup>6</sup>之間的所有數。1850年[[切比雪夫]]證明了這個猜想。[[拉馬努金]]給出較簡單的證明，而[[埃尔德什·帕尔|艾狄胥]]則借[[二項式係數]]給出了另一個簡單的證明。

==相關定理==
===西爾維斯特定理===
[[詹姆斯·約瑟夫·西爾維斯特]]證明：<math>k</math>個大於<math>k</math>的連續整數之積，是一個大於<math>k</math>的質數的倍數。
===艾狄胥定理===
艾狄胥證明：對於任意正整數<math>k</math>，存在正整數<math>N</math>使得對於所有<math>n>N</math>，<math>n</math>和<math>2n</math>之間有<math>k</math>個質數。

他又證明<math>k=2</math>、<math>N=6</math>時，而且有，其中两個質數分别是4的倍數加1，4的倍數減1。

根據質數定理，<math>n</math>和<math>2n</math>之間的質數數目大約是<math>n\over\ln(n)</math>。

==證明==
證明的方法是运用[[反證法]]，反設定理不成立，然后用两种方法估计<math>{2n \choose n}</math>的上下界，得出矛盾的不等式

註：下面的證明中，都假設<math>p</math>屬於質數集。

===不等式1===
這條不等式是關於<math>{2n \choose n}</math>的下界的。

* 對於正整數<math>n</math>，<math>{2n \choose n} \ge \frac{4^n}{2n}</math>

證明 ：
: 對於 <math>k \le 2n</math> ， <math>{2n \choose n} \ge {2n \choose k}</math>
:若<math>k \ne n</math>，<math>{2n \choose n} > {2n \choose k}</math>
: 因此<math> 2n {2n \choose n} \ge \sum_{i=1}^{2n} {2n \choose i} + 1 = 2^{2n} = 4^n</math>

===引理1===
* <math> \prod_{k+1 < p \le 2k+1 } p \ < 4^k</math>

证明：
注意到所有大于 k+1 而小于 2k+1 的质数都在(2k+1)! 中而不在(k+1)! 或 k！ 中，于是<math>\prod_{k+1 < p \le 2k+1} p</math> 是<math>{ {2k+1} \choose {k+1} }</math>的因子。
: <math>\prod_{k+1 < p \le 2k+1 } p \quad  \left \vert \  { {2k+1} \choose {k+1} }\right.  </math>
: 同时又有  <math> 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</math> 

:于是就有 <math> \prod_{k+1 < p \le 2k+1 } p\ \  \le { {2k+1} \choose {k+1} } < 4^k</math>

===定理1===
這個定理和<math>{2n \choose n}</math>的上界有關。

* 對於所有正整數<math>n</math>， <math>\prod_{p \le n } p < 4^n</math>

[[數學歸納法]]：

當<math>n=2</math>，2 < 16，成立。

假設對於所有少於<math>n</math>的整數，敘述都成立。

顯然，若n>2且n是偶數，<math>\prod_{p \le n } p = \prod_{p \le n-1 } p</math>。对于奇数的n，设''n=2k+1''。

從[[#引理1|引理1]]和歸納假設可得：

<math>\prod_{p \le n } p = \prod_{p \le 2k+1 } p = \prod_{p \le k+1 } p \cdot \prod_{k+1 < p \le 2k+1 } p < 4^{k+1} \cdot 4^k = 4^{2k+1} = 4^n</math>

===系理1===
首先的定理：

* 若<math>p</math>是質數，<math>n</math>是整數。設<math>s</math>是最大的整數使得<math>p^s|n!</math> ，則<math>s=\sum_{i=1}^{\infty} {\lbrack \frac{n}{p^i} \rbrack}</math>

下面這些系理和<math>{2n \choose n}</math>的上界有關。



若<math>p</math>為質數，設<math>s_p</math>是最大的整數使得 <math>p^{s_p}</math> 整除 <math>{2n \choose n}</math>，則：

:<math>s_p=\sum_{i \ge 1} {( \lbrack \frac{2n}{p^i} \rbrack - 2 \lbrack \frac{n}{p^i} \rbrack ) }</math>

對於所有<math>x>0</math>，<math> \lbrack 2x \rbrack - 2 \lbrack x \rbrack \le 1 </math>  ，所以

:<math>s_p=\sum_{i \ge 1} {( \lbrack \frac{2n}{p^i} \rbrack - 2 \lbrack \frac{n}{p^i} \rbrack ) } \le max \left\{ r | p^r \le 2n \right\}</math>

于是得到三个上界：

# <math>p^{s_p} \le 2n</math>
# 若 <math>\sqrt{2n} < p</math> ， <math>s_p \le 1</math>
# 若 <math>2n/3 < p \le n</math>，<math>s_p=0</math>（因为 ''2n!''  中只有两个 ''p''，在 ''n!'' 中恰有一个 ''p''）

===核心部分===
假設存在大於1的正整數<math>n</math>，使得沒有質數<math>p</math>符合<math>n<p<2n</math>。根據系理1.2和1.3：

<math>{2n \choose n} = \prod_{p \le 2n} p^{s_p} = \prod_{p \le 2n/3 } p^{s_p}  \le \prod_{  p \le \sqrt{2n} } p^{s_p -1} \cdot \prod_{ p \le 2n/3 } p</math>

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

結合之前關於<math>2n \choose n</math>的下界的[[#不等式1|不等式1]]：
: <math>(2n)^{-1} 4^n < {2n \choose n} < (2n)^{\sqrt{2n}/2-1} \cdot 4^{2n/3}</math>

: <math>4^n < (2n)^{\sqrt{2n}/2} \cdot 4^{2n/3}</math>
: <math>4^{2n/3} < (2n)^{\sqrt{2n}}</math>

兩邊取2的對數，并设<math>x = \sqrt{2n}</math>：

: <math>x \ln 2 - 3 \ln x <0 </math>。

顯然<math>x \ge 16</math>，即<math>n \ge 128</math>時，此式不成立，得出矛盾。
因此<math>n \ge 128</math>時，伯特蘭—切比雪夫定理成立。

再在<math>n<128</math>時驗證這個假設即可。

==參考==
* [https://web.archive.org/web/20060706171618/http://www.math.uga.edu/%7Elyall/REU/Bertrand.pdf A simple proof of Bertrand's Postulate, Neil Lyall]
* [https://web.archive.org/web/20040525015927/http://yll.loxa.edu.tw/jpg/a/03112009431684.pdf Number Theory. Tutorial 5: Bertrand's Postulate]

==外部連結==
* [http://www.cs.uwaterloo.ca/journals/JIS/green.html  Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate]{{Wayback|url=http://www.cs.uwaterloo.ca/journals/JIS/green.html |date=20060710050226 }}, Lawrence E. Greenfield


[[Category:数学定理|B]]
[[Category:素数|B]]