伯特蘭-切比雪夫定理

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是伯特蘭定理

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

1845年約瑟·伯特蘭提出這個猜想。伯特蘭檢查了2至3×106之間的所有數。1850年切比雪夫證明了這個猜想。拉馬努金給出較簡單的證明,而保羅·艾狄胥則借二項式係數給出了另一個簡單的證明。

相關定理[编辑]

西爾維斯特定理[编辑]

詹姆斯·約瑟夫·西爾維斯特證明:k個大於k的連續整數之積,是一個大於k的質數的倍數。

艾狄胥定理[编辑]

艾狄胥證明:對於任意正整數k,存在正整數N使得對於所有n>Nn2n之間有k個質數。

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

根據質數定理,n2n之間的質數數目是n\over\ln(n)

證明[编辑]

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

註:下面的證明中,都假設p屬於質數集。

不等式1[编辑]

這條不等式是關於{2n \choose n}的下界的。

  • 對於正整數n{2n \choose n} \ge \frac{4^n}{2n}

證明 :

對於 k \le 2n{2n \choose n} \ge {2n \choose k}
k \ne n{2n \choose n} > {2n \choose k}
因此 2n {2n \choose n} \ge \sum_{i=1}^{2n} {2n \choose i} + 1 = 2^{2n} = 4^n

引理1[编辑]

  •  \prod_{k+1 < p \le 2k+1 } p < 2^{n-1}

证明: 注意到所有大于 k+1 而小于 2k+1 的质数都在(2k+1)! 中而不在(k+1)! 或 k! 中,于是\prod_{k+1 < p \le 2k+1} { {2k+1} \choose {k+1} }的因子。

\prod_{k+1 < p \le 2k+1 } p | { {2k+1} \choose {k+1} }
同时又有  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 \le 2k+1 } p \le { {2k+1} \choose {k+1} } < 4^k

定理1[编辑]

這個定理和{2n \choose n}的上界有關。

  • 對於所有正整數n\prod_{p \le n } p < 4^n

數學歸納法

n=2,2 < 16,成立。

假設對於所有少於n的整數,敘述都成立。

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

引理1和歸納假設可得:

\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

系理1[编辑]

首先的定理:

  • p是質數,n是整數。設s是最大的整數使得p^s|n! ,則s=\sum_{i=1}^{\infty} {\lfloor \frac{n}{p^i} \rfloor}

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


p為質數,設s_p是最大的整數使得 p^{s_p} 整除 {2n \choose n},則:

s_p=\sum_{i \ge 1} {( \lfloor \frac{2n}{p^i} \rfloor - 2 \lfloor \frac{n}{p^i} \rfloor ) }
 \forall x>0, \lfloor 2x \rfloor - 2 \lfloor x \rfloor \le 1 ,所以
s_p=\sum_{i \ge 1} {( \lfloor \frac{2n}{p^i} \rfloor - 2 \lfloor \frac{n}{p^i} \rfloor ) } \le max \left\{ r | p^r \le 2n \right\}

于是得到三个上界:

  1. p^{s_p} \le 2n
  2. \sqrt{2n} < ps_p \le 1
  3. 2n/3 < p \le ns_p=0(因为 2n! 中只有两个 p,在 n! 中恰有一个 p

核心部分[编辑]

假設存在大於1的正整數n,使得沒有質數p符合n<p<2n。根據系理1.2和1.3:

{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

再根據系理1.1和定理1: {2n \choose n} \le 上式最右方  < (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 \ge 16,即n \ge 128時,此式不成立,得出矛盾。 因此n \ge 128時,伯特蘭—切比雪夫定理成立。

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

參考[编辑]

外部連結[编辑]