素数有无穷多个的17个证明（2）

9. Srinivasan的证明

由Goldbach和Schorn的证明可知，如果存在无穷多个两两互素的正整数，则可由此证明存在无穷多个素数．

引理 如果在数列{𝑥_(𝑛)}中，对于任意正整数𝑖，都有𝑥_(𝑖)|𝑥_(𝑖+1)且gcd(𝑥_(𝑖),(𝑥_(𝑖+1))/(𝑥_(𝑖)))=1．则容易知道数列{(𝑥_(𝑛+1))/(𝑥_(𝑛))}中任意两项均互素．

设𝑓(𝑥)=𝑥^(2)+𝑥+1．则𝑓(𝑛^(2))=𝑓(𝑛)𝑓(−𝑛)，且

公式：\begin{aligned} &\gcd(n^2+n+1,n^2-n+1)\\ =&\gcd(2n,n^2-n+1)\\ =&\gcd{n,n^2-n+1}\\ =&1 \text{．} \end{aligned}

于是数列𝑥_(𝑚)=𝑓(2^(2^(𝑚)))符合以上要求．

数列𝑥_(𝑚)=2^(𝑝^(𝑚))−1（𝑝为素数）同样也符合以上要求．

当 m≥1 时，xₘ/xₘ₋₁ 的任一素因子 q 都使 2 模 q 的乘法阶等于 pᵐ，故 q≡1 (mod pᵐ)。固定 r≥1，令 m≥r，利用这些商两两互素，即得有无穷多个模 pʳ 余 1 的素数。

公式：\begin{aligned} \dfrac{x_{m+1}}{x_m}=&\dfrac{(x_m+1)^p-1}{(x_m+1)-1}\\ =&1+(x_m+1)+\cdots+(x_m+1)^{p-1}\\ \equiv& p({\rm{mod}}\ q)\text{．} \end{aligned}

因此如果素数𝑞同时整除𝑥_(𝑚)和(𝑥_(𝑚+1))/(𝑥_(𝑚))，则必有𝑞=𝑝．

而由Fermat小定理，

当 m≥1 时，xₘ/xₘ₋₁ 的任一素因子 q 都使 2 模 q 的乘法阶等于 pᵐ，故 q≡1 (mod pᵐ)。固定 r≥1，令 m≥r，利用这些商两两互素，即得有无穷多个模 pʳ 余 1 的素数。

Srinivasan进一步证明了对于任意正整数𝑘≥1，存在无穷多个模𝑘余1的素数．这和Lucas的证明本质上是一样的，这里不再赘述．

10. Thue的证明

设正整数𝑛和𝑘满足(1+𝑛)^(𝑘)<2^(𝑛)，并设不超过2^(𝑛)的所有素数依次为𝑝_(1)=2，𝑝_(2)=3，⋯，𝑝_(𝑟)．对于任意的1≤𝑚≤2^(𝑛)，其可以被表示为

由𝑚≤2^(𝑛)可知𝑒_(𝑖)≤𝑛（1≤𝑖≤𝑟）．

于是𝑒_(1),𝑒_(2),⋯,𝑒_(𝑟)的取值不超过(𝑛+1)^(𝑟)种．于是有

即𝑟>𝑘．

对每个正整数𝑘，由1+2𝑘^(2)<2^(2𝑘)可知

取𝑛=2𝑘^(2)，这样的𝑛和𝑘是满足上述要求的．

于是对于任意正整数𝑘，存在至少𝑘+1个素数𝑝<2^(𝑛)=4^(𝑘^(2))，从而证明了素数有无穷多个．

11. Perott的证明

首先我们知道∑_(𝑛=1)^(+∞)(1)/(𝑛^(2))是收敛的，且其值恒小于2．
事实上，Euler证明了公式：\sum\limits_{n=1}^{+\infty}\dfrac{1}{n^2}=\dfrac{\pi^2}{6}．
我们可以用一个简单而初等的方法证明

证明

公式：\begin{aligned} \sum\limits_{n=1}^{+\infty}\dfrac{1}{n^2}=&1+\dfrac{1}{4}+\sum\limits_{n=3}^{\infty}\dfrac{1}{n^2}\\ <&\dfrac{5}{4}+\sum\limits_{n=3}^{+\infty}\dfrac{1}{n(n-1)}\\ =&\dfrac{5}{4}+\sum\limits_{n=3}^{+\infty}\left(\dfrac{1}{n-1}-\dfrac{1}{n}\right)\\ =&\dfrac{5}{4}+\dfrac{1}{2}\\ =&\dfrac{7}{4} \end{aligned}

设𝛿=2−∑_(𝑛=1)^(∞)(1)/(𝑛^(2))．由上面的证明可知𝛿>(1)/(4)．

将不超过𝑁的所有素数依次设为𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑟)．由Erdös的证明可知：在不超过𝑁的正整数中，无除1外的平方因子的正整数至多有2^(𝑟)个，能被𝑑^(2)所整除的正整数至多有(𝑁)/(𝑑^(2))个．于是有除1以外的平方因子的正整数个数不超过

公式：\sum\limits_{d=2}^{+\infty}\dfrac{N}{d^2}=N\left(\sum\limits_{d=1}^{+\infty}\dfrac{1}{d^2}-1\right)=N(1-\delta)

于是𝑁≤2^(𝑟)+𝑁(1−𝛿)，即2^(𝑟)≥𝛿𝑁≥(𝑁)/(4)，也即𝑟>log_(2)𝑁−2．从而证明了素数有无穷多个．

Perott的证明将不超过𝑁的所有正整数按照是否含有除1外的平方因子分成两类．此方法是筛法的基础，而筛法本质上是用来估计满足某些特定条件的整数数量的．

12. Auric的证明

反证法．若只有有限个素数，将其从小到大排列成𝑝_(1)<𝑝_(2)<⋯<𝑝_(𝑟)．设𝑡为任意正整数，𝑁=𝑝𝑡𝑟．

每个不超过𝑁的正整数𝑚可以被表示为

设𝐸=(ln𝑝_(𝑟))/(ln𝑝_(1))，由𝑝𝑓_(𝑖)1≤𝑝𝑓_(𝑖)𝑖≤𝑁=𝑝𝑡𝑟可知𝑓_(𝑖)≤𝑡𝐸对任意𝑖均成立．于是

公式：p_r^t=N\leq (tE+1)^r\leq t^r(E+1)^r

当𝑡足够大时，上式不成立．于是素数有无穷多个．

13. Boije和Gennäs的证明

设𝑁为任意正整数，2,3,⋯,𝑝_(𝑛)为不超过𝑁的所有素数．取𝑃=2^(𝑒_(1))3^(𝑒_(2))⋯𝑝𝑒_(𝑛)𝑛，其中𝑒_(𝑖)≥1．设正整数𝐴，𝐵满足gcd(𝐴,𝐵)=1，𝑃=𝐴𝐵，且𝑄=𝐵−𝐴>1．于是𝑄不被任何不超过𝑁的素数所整除，从而至少存在一个大于𝑁的素数． 于是素数有无穷多个．

注 本方法在本质上与Stieltjes的证明相同．

14.Barnes的证明

Barnes的证明用到了周期连分数和Pell方程的相关理论．

反证法．若只有有限个素数，设它们为𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑡)．令𝑃=∏_(𝑖=1)^(𝑡)𝑝_(𝑖)，𝑄=∏_(𝑖=2)^(𝑡)𝑝_(𝑖)．考虑连分数𝑥=[𝑃,𝑃,⋯]．有

注意到𝑄^(2)+1不被除2外的任意素数整除，故必为2的幂．又𝑄^(2)+1不可能为完全平方数，可设𝑄^(2)+1=2^(2𝑙+1)即

注 由𝑄^(2)+1>2以及𝑄^(2)+1不能被4整除，可以很快知道𝑄^(2)+1不为2的幂．

15. Braun的证明

反证法．若只有有限个素数，设它们为𝑝_(1)=2，𝑝_(2)=3，⋯，𝑝_(𝑡)．考虑

注意道(1)/(2)+(1)/(3)+(1)/(5)>1，于是(𝑚)/(𝑛)>1即𝑚>𝑛≥1．

于是𝑚必含有某个素因子𝑝_(𝑖)．然而，

公式：m=\sum\limits_{j=1}^{t}\prod\limits_{k\neq j}p_k\equiv\prod_{k\neq i}p_k\not\equiv 0({\rm{mod}}\ p_i)\text{．}

矛盾．因此存在无穷多个素数．

16. Harris的证明

设𝐴_(0)，𝐴_(1)，𝐴_(2)为两两互素的正整数，对于𝑛≥3，

公式：A_n=\prod_{k=0}^{n-3}A_k\cdot A_{n-1}+A_{n-2}\text{．}

证明 由递推关系容易证明以下两个结论：

（1）若𝑝|gcd(𝐴_(𝑛),𝐴_(𝑛−2))，则存在𝑖≥1，且𝑖≠2，使得𝑝|gcd(𝐴_(𝑛−𝑖),𝐴_(𝑛−2))．

（2）若𝑝|gcd(𝐴_(𝑛),𝐴_(𝑛−𝑗))，（𝑗≥1，且𝑗≠2），则𝑝|gcd(𝐴_(𝑛−𝑗),𝐴_(𝑛−2))．

由数学归纳法及𝐴_(0)，𝐴_(1)，𝐴_(2)两两互素即证．

17. Chernoff的证明

反证法．若只有有限个素数，设它们为𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑘)．对于任意正整数𝑁，恰好存在自然数组(𝑒_(1),𝑒_(2),⋯,𝑒_(𝑘))的𝑁种排列方式，使得

公式：e_1\ln p_1+e_2\ln p_2+\cdots+e_k\ln p_k\leq \ln N

公式：\dfrac{(\ln N)^k}{k!\ln p_1\ln p_2\cdots\ln p_n}