伯特兰-切比雪夫定理

用手机看条目

出自 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/wiki/%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条)

导航

意见反馈