Betrand-Chebyshev 定理 - Erdős Pál 初等证明
MatchaNeko_nya
·
·
学习·文化课
Betrand-Chebyshev 定理
\small \forall n\geq 1,\exist$ 质数 $\small p~~s.t.~n<p\le 2n
下面给出了一个由 Erdős Pál 提出的初等证明。
证明：
（1）对于 n<4000 的情况证明 Betrand-Chebyshev 定理，经检验：
2,3,5,7,13,23,43,83,163,317,631,1259,2503,4001
为一些质数且每一个均小于前一个的两倍，从而 n<4000 的情况得证。
（2）下证：
引理
\large\prod\limits_{ p\geq x,p\in \mathbb{P}}\normalsize p\le4^{x-1},x\geq2~~~~(*)
证明：
注意到，如果 q 是满足 q\le x 的最大质数，那么
\prod\limits_{p\geq x,p\in \mathbb{P}}p\le \prod\limits_{p\geq q,p\in \mathbb{P}}p,4^{q-1}\le 4^{x-1}
只需验证 (*) 式当 x=q 为质数时成立即可，易知 x=2 时成立。
考虑 q=2m+1，即 q 为奇质数，同时归纳证明 (*) 式对 2,3,...,2m 都成立。
\large\prod\limits_{p\le 2m+1,p\in\mathbb{P}}\normalsize p=\large\prod\limits_{p\le m+1,p\in\mathbb{P}}\normalsize p\cdot\large\prod\limits_{m+1<p\le 2m+1,p\in\mathbb{P}}\normalsize p\le 4^m\cdot\binom{2m+1}{m}\le 4^m\cdot 2^{2m}=4^{2m}
由数学归纳法，引理得证。
（3）
>
> **Legendre 定理**
>
> 设 $v_p(n)$ 为质数 $p$ 在 $n$ 中的最高指数，则 $v_p(n!)=\sum\limits_{k=1}^{+\infty}[\dfrac{n}{p^k}]
沿用上述的定义，同时易知
v_p(ab)=v_p(a)+v_p(b),v_p(\dfrac{a}{b})=v_p(a)-v_p(b)
故 \binom{2n}{n}=\dfrac{(2n)!}{(n!)^2},v_p(\binom{2n}{n})=\sum\limits_{k=1}^{+\infty}([\dfrac{2n}{p^k}]-2[\dfrac{n}{p^k}])
由高斯函数相关定义可知 [2a]-2[a]\in(0,1]
故 v_p(\binom{2n}{n})\le \max\{r|p^r<2n\}
同时不难证明，当 p\geq \sqrt{2n} 时，v_p(\binom{2n}{n})\le 1，当 \dfrac{2}{3}n<p\le n 时，v_p(\binom{2n}{n})=0.
（4）运用 引理 和（3）中的结论以及二项式展开可得：
\dfrac{4^n}{2n}\le\binom{2n}{n}\le\prod\limits_{p\le\sqrt{2n},p\in\mathbb{P}}(2n)\cdot\prod\limits_{\sqrt{2n}<p\le\tfrac{2}{3}n,p\in\mathbb{P}}p\cdot\prod\limits_{n<p\le 2n,p\in\mathbb{P}}p\le (2n)^{\sqrt{2n}}\cdot\prod\limits_{\sqrt{2n}<p\le\tfrac{2}{3}n,p\in\mathbb{P}}p\cdot\prod\limits_{n<p\le 2n,p\in\mathbb{P}}p
（5）假设有一 n 使得不存在质数 p 满足 n<p\le 2n 则 \prod\limits_{n<p\le 2n}p=1. 代入（4）中的式子得到：
4^n\le (2n)^{1+\sqrt{2n}}\cdot4^{\tfrac{2}{3}n}
进一步得到
4^{\tfrac{1}{3}n}\le (2n)^{1+\sqrt{2n}}
利用 Bernoulli 不等式，a\geq 2 时 a+1<2^a，有
2n=(\sqrt[6]{2n})^6<([\sqrt[6]{2n}]+1)^6<2^{6[\sqrt[6]{2n}]}\le2^{6\sqrt[6]{2n}}
所以对 n\geq 50，此时 18<2\sqrt{2n}，有：
2^{2n}\le (2n)^{3(1+\sqrt{2n})}<2^{\sqrt[6]{2n}(18+18\sqrt{2n})}<2^{20\sqrt[6]{2n}\cdot\sqrt{2n}}=2^{20(2n)^{\tfrac{2}{3}}}
则 (2n)^{\tfrac{1}{3}}<20，从而 n<4000.
由（1），矛盾。
故 Betrand-Chebyshev 定理 得证。
\square