素数无限的几个证明
毕达哥拉斯学派证明
公元前600～公元前500年古希腊时期，为了证明素数有无限个这个问题，毕达哥拉斯学派给出了一个证明：
素数是从2和3开始的，所以用2 * 3+1 = 7；
7是素数，所以用2 * 3 * 7+1 = 43；
43是素数，所以用2 * 3 * 7 * 43+1 = 1807；
1807不是素数，但是1807 = 13 * 139，这两个数都是素数，发现了两个新素数，我们用小的素数与那一堆相乘，所以用2 * 3 * 7 * 43 * 13 + 1 = 23479；
23479不是素数，但是23479 = 53 * 443，这两个都是素数，又发现了两个新素数；
继续往下，会一直发现新的素数，即证明素数有无限个。
毕达哥拉斯学派在当时能证明出来是非常了得，后200年又出现了这么一位神人——欧几里得！
欧几里得证明
欧几里得用的是反证法，证明如下：
先假设素数是有限个，即P1, P2, P3,…Pk；其中Pk是最大的素数；
我们用A = P1 * P2 * P3 * P4 * …* Pk + 1；即将所有素数相乘后加1；
一个自然数要么是素数要么是合数（除了1）；
1、A是素数，由于Pk是素数，所以不存在比Pk还大的素数A，即A不可能是素数；
2、A是合数，由于所有的合数都可以由素数相乘得到，即A % Pi = 0，所有的素数都是A的因子，而A = 所有素数相乘 + 1，即A不可能是合数；
那么A又不是素数也不是合数，得出原命题素数有限个是错误的，即证明了素数无限个。
欧拉证明
在这里，我们就要介绍欧拉乘积式了，因为这也是证明素数无限个的一个证明方法。
1735年，欧拉大神发表了一个极其重要的公式，即欧拉乘积式：
∑
n
=
1
∞
n
−
s
=
∏
p
(
1
−
1
p
s
)
−
1
\sum_{n =1 }^{\infty }n^{-s} = \prod_{p}(1 – \frac{1}{p^{s}})^{-1}
n
=
1
∑
∞
n
−
s
=
p
∏
(
1
−
p
s
1
)
−
1
证明之前我们先需要知道以下基本知识。
我们知道调和级数是发散的，即：
门戈利当时提出了一个问题，全体自然数的平方倒数之和是多少呢？当时也没有解决这个问题，后来被约翰伯努利的学生欧拉解决出来了，即上上期博客的巴塞尔问题，可以自行观看，答案是：
后来欧拉又把这样的式子进行了拓展，即将自然数上的幂变成s，即得到这样的一个式子：
ε
(
s
)
=
1
+
1
2
s
+
1
3
s
+
1
4
s
+
1
5
s
+
1
6
s
+
.
.
.
（
1
）
\varepsilon (s) = 1 + \frac{1}{2^{s}} + \frac{1}{3^{s}} + \frac{1}{4^{s}} +\frac{1}{5^{s}} + \frac{1}{6^{s}}+… \qquad （1）
ε
(
s
)
=
1
+
2
s
1
+
3
s
1
+
4
s
1
+
5
s
1
+
6
s
1
+
.
.
.
（
1
）
我们对左右两边同时乘以
1
2
s
\frac{1}{2^{s}}
2
s
1
，即得到：
1
2
s
ε
(
s
)
=
1
2
s
+
1
4
s
+
1
6
s
+
1
8
s
+
.
.
.
.
（
2
）
\frac{1}{2^{s}}\varepsilon (s) = \frac{1}{2^{s}} + \frac{1}{4^{s}} + \frac{1}{6^{s}} + \frac{1}{8^{s}} + …. \qquad（2）
2
s
1
ε
(
s
)
=
2
s
1
+
4
s
1
+
6
s
1
+
8
s
1
+
.
.
.
.
（
2
）
式(1) – 式(2) 得：
(
1
−
1
2
s
)
ε
(
s
)
=
1
+
1
3
s
+
1
5
s
+
1
7
s
+
1
9
s
+
.
.
.
（
3
)
(1 – \frac{1}{2^{s}})\varepsilon (s) = 1 + \frac{1}{3^{s}} + \frac{1}{5^{s}} + \frac{1}{7^{s}} +\frac{1}{9^{s}} +… \qquad （3)
(
1
−
2
s
1
)
ε
(
s
)
=
1
+
3
s
1
+
5
s
1
+
7
s
1
+
9
s
1
+
.
.
.
（
3
)
这样，所有的2的倍数的自然数都消去了。
我们在对左右两边同时乘以
1
3
s
\frac{1}{3^{s}}
3
s
1
，即得到：
1
3
s
(
1
−
1
2
s
)
ε
(
s
)
=
1
9
s
+
1
1
5
s
+
1
2
1
s
+
1
2
7
s
+
.
.
.
（
4
)
\frac{1}{3^{s} }(1 – \frac{1}{2^{s}})\varepsilon (s) = \frac{1}{9^{s}} + \frac{1}{15^{s}} + \frac{1}{21^{s}} +\frac{1}{27^{s}} +… \qquad （4)
3
s
1
(
1
−
2
s
1
)
ε
(
s
)
=
9
s
1
+
1
5
s
1
+
2
1
s
1
+
2
7
s
1
+
.
.
.
（
4
)
式(3) – 式(4)得：
(
1
−
1
3
s
)
(
1
−
1
2
s
)
ε
(
s
)
=
1
+
1
3
s
+
1
5
s
+
1
7
s
+
1
1
1
s
+
.
.
.
(
5
)
(1-\frac{1}{3^{s} })(1 – \frac{1}{2^{s}})\varepsilon (s) = 1 + \frac{1}{3^{s}} + \frac{1}{5^{s}} + \frac{1}{7^{s}} + \frac{1}{11^{s}} + … \qquad (5)
(
1
−
3
s
1
)
(
1
−
2
s
1
)
ε
(
s
)
=
1
+
3
s
1
+
5
s
1
+
7
s
1
+
1
1
s
1
+
.
.
.
(
5
)
有没有发现这样的一个问题，第一次相减，把所有的自然数的2倍都消去了，第二次相减，把所有的自然数的3倍都消去了，emmmm，埃拉托色尼筛法！！！
没错，理解到了这一步就已经很快了，类似的运算继续下去，我们每一步都减去
1
5
s
\frac{1}{5^{s}}
5
s
1
倍、
1
7
s
\frac{1}{7^{s}}
7
s
1
倍…也就把素数的倍数都消去。
最终得到这样一个公式：
.
.
.
(
1
−
1
1
3
s
)
(
1
−
1
1
1
s
)
(
1
−
1
7
s
)
(
1
−
1
5
s
)
(
1
−
1
3
s
)
(
1
−
1
2
s
)
ε
(
s
)
=
1
(
6
)
…(1 – \frac{1}{13^{s}})(1 – \frac{1}{11^{s}})(1 – \frac{1}{7^{s}})(1 – \frac{1}{5^{s}})(1-\frac{1}{3^{s} })(1 – \frac{1}{2^{s}})\varepsilon (s) = 1 \qquad (6)
.
.
.
(
1
−
1
3
s
1
)
(
1
−
1
1
s
1
)
(
1
−
7
s
1
)
(
1
−
5
s
1
)
(
1
−
3
s
1
)
(
1
−
2
s
1
)
ε
(
s
)
=
1
(
6
)
再将左边变过去，保留
ε
(
s
)
\varepsilon (s)
ε
(
s
)
，即：
ε
(
s
)
=
1
(
1
−
1
2
s
)
(
1
−
1
3
s
)
(
1
−
1
5
s
)
(
1
−
1
7
s
)
(
1
−
1
1
1
s
)
(
1
−
1
1
3
s
)
.
.
.
(
7
)
\varepsilon (s) = \frac{1}{(1 – \frac{1}{2^{s}})(1 – \frac{1}{3^{s}})(1 – \frac{1}{5^{s}})(1 – \frac{1}{7^{s}})(1-\frac{1}{11^{s} })(1 – \frac{1}{13^{s}})…} \qquad (7)
ε
(
s
)
=
(
1
−
2
s
1
)
(
1
−
3
s
1
)
(
1
−
5
s
1
)
(
1
−
7
s
1
)
(
1
−
1
1
s
1
)
(
1
−
1
3
s
1
)
.
.
.
1
(
7
)
让我们用连乘符号
∏
\prod
∏
简洁一下得：
∑
n
=
1
∞
n
−
s
=
∏
p
(
1
−
1
p
s
)
−
1
(
8
)
\sum_{n =1 }^{\infty }n^{-s} = \prod_{p}(1 – \frac{1}{p^{s}})^{-1} \qquad (8)
n
=
1
∑
∞
n
−
s
=
p
∏
(
1
−
p
s
1
)
−
1
(
8
)
当n = 1时，左边就是调和级数，是发散的，而右边的p是所有素数，若素数是有限个，即调和级数不发散，那怎么可能呢？？？所以得证素数是无限个。
欧拉大神NB！
注意：
s一定是大于1的，否则会出现一些好玩的东西，比如全体自然数之和竟然是
−
1
12
!
!
!
-\frac{1}{12}!!!
−
1
2
1
!
!
!
我们下期再聊。
参考:
https://www.bilibili.com/video/BV1dt4y1179j
https://www.bilibili.com/video/BV1eW411r7cp
https://www.bilibili.com/video/BV13W41167Bb