伯特蘭-切比雪夫定理

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

伯特蘭-切比雪夫定理(Bertrand Chebyshev theorem)

什麼是伯特蘭-切比雪夫定理

　　伯特蘭-切比雪夫定理是指1845年約瑟•伯特蘭提出的猜想。伯特蘭檢查了2至3×10⁶之間的所有數。1850年切比雪夫證明瞭這個猜想。拉馬努金給出較簡單的證明，而保羅•艾狄胥則借二項式繫數給出了另一個簡單的證明。

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

[編輯]

伯特蘭-切比雪夫定理的相關定理

[編輯]

西爾維斯特定理

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

[編輯]

艾狄胥定理

　　艾狄胥證明：對於任意正整數 $k$ ，存在正整數 $N$ 使得對於所有 $n > N$ ， $n$ 和 $2 n$ 之間有 $k$ 個質數。

　　他又證明 $k = 2$ 、 $N = 6$ 時，而且有，其中兩個質數分別是4的倍數加1，4的倍數減1。

　　根據質數定理， $n$ 和 $2 n$ 之間的質數數目是 $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\}$

　　於是得到三個上界：

　　 $p^{s_p} \le 2n$

　　若 $\sqrt{2n} < p$ ， $s_p \le 1$

　　若 $2n/3 < p \le n$ ， $s p = 0$ （因為 2n! 中只有兩個 p，在 n! 中恰有一個 p）

[編輯]

核心部分

　　假設存在大於1的正整數 $n$ ，使得沒有質數 $p$ 符合 $n < p < 2 n$ 。根據系理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 ln2 - 3ln x < 0$ 。

　　顯然 $x \ge 16$ ，即 $n \ge 128$ 時，此式不成立，得出矛盾。

　　因此 $n \ge 128$ 時，伯特蘭—切比雪夫定理成立。

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

取自"https://wiki.mbalib.com/zh-tw/%E4%BC%AF%E7%89%B9%E5%85%B0-%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E5%AE%9A%E7%90%86"

打开MBA智库App, 阅读完整内容打开App

如果您認為本條目還有待完善，需要補充新內容或修改錯誤內容，請編輯條目或投訴舉報。

本条目由以下用户参与贡献

Tracy,Mis铭.

頁面分類: 數學定理

評論(共0條)

提示:評論內容為網友針對條目"伯特蘭-切比雪夫定理"展開的討論，與本站觀點立場無關。

發表評論請文明上網，理性發言並遵守有關規定。

查看

工具▼

伯特蘭-切比雪夫定理

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

什麼是伯特蘭-切比雪夫定理

伯特蘭-切比雪夫定理的相關定理

西爾維斯特定理

艾狄胥定理

伯特蘭-切比雪夫定理的證明

不等式1

引理1

定理1

系理1

核心部分

温馨提示

本条目相关课程

本条目由以下用户参与贡献

評論(共0條)

導航

意见反馈

查看

工具▼

伯特蘭-切比雪夫定理

出自 MBA智库百科(https://wiki.mbalib.com/)

目錄

什麼是伯特蘭-切比雪夫定理

伯特蘭-切比雪夫定理的相關定理

西爾維斯特定理

艾狄胥定理

伯特蘭-切比雪夫定理的證明

不等式1

引理1

定理1

系理1

核心部分

温馨提示

本條目相關文檔

本条目相关课程

本条目由以下用户参与贡献

評論(共0條)

導航

意见反馈