1. 质数

(1). 质数的定义

质数是指在大于1的自然数中, 除了1和它本身以外不再有其他因数的自然数.
摘自百度百科

(2). 质数有无穷多个的证明

法1. 构造法

假设质数只有有限个, 则这有限个质数是可列举的.
不妨设一共有$n$个质数, $P = \lbrace p_i | p_i为质数 \rbrace$, $p_1 < p_2 < p_3 < … < p_n$

考虑构造$X = p_1 p_2 p_3 … p_n + 1$, 显然, $X > p_n$, 所以$X$必然为

质数
进而必然存在$i$, 使得$p_i | X$
再由整除的性质, $p_i | 1$, 矛盾!

所以质数有无穷多个.

法2. 利用欧拉恒等式

引理1.
$(1 + \frac{1}{p_1} + \frac{1}{p_1^2} + …) (1+ \frac{1}{p_2} + \frac{1}{p_2^2} + …) … = 1 + \tfrac{1}{2} + \tfrac{1}{3} + …$
也就是$\prod\limits_{i=1}^\infty (\sum\limits_{j=1}^\infty \frac{1}{p_i^j}) = \sum\limits_{i=1}^\infty \tfrac{1}{i}$
[注]. $p_1, p_2, p_3, … 为互不相同的质数$

引理1的证明
将左边展开后, 根据唯一分解定理, 与右边一一对应

引理2.
式子$\sum\limits_{i=0}^\infty (\frac{1}{x^i})$在$x>1$的时候是收敛的

引理2的证明: 使用错位相减法
记$y = \sum\limits_{i=0}^\infty (\frac{1}{x^i})$, 则$y \div x = \sum\limits_{i=1}^\infty (\frac{1}{x^i})$
相减, 得$y(1-\tfrac{1}{x}) = 1$ => $y = \tfrac{x}{x-1}$, 它是收敛的
[注]. 只有当$x>1$的时候才成立!

引理3.
式子$\sum\limits_{i=1}^\infty \tfrac{1}{i}$是发散的

引理3的证明: 放缩通分
$原式 >= 1 + \tfrac{1}{2} + (\tfrac{1}{4} + \tfrac{1}{4}) + (\tfrac{1}{8} + \tfrac{1}{8} + \tfrac{1}{8} + \tfrac{1}{8}) + …$
$ = 1+\tfrac{1}{2} + \tfrac{1}{2} + \tfrac{1}{2} + …$显然是发散的

回到原问题

如果质数只有有限个, 则左边为有限个收敛的数的乘积, 是收敛的, 右边为调和级数, 是发散的
矛盾!

所以质数有无穷多个.

(3). 所有质数的倒数之和不是收敛的证明

令$p_1$, $p_2$, $\cdots$ 为升序排列的质数. 并假设$\sum\limits_{p \in P}^{} \frac{1}{p}$收敛. 那么一定存在$k \in N^+$使得$\sum\limits_{i >k}{} \frac{1}{p_i} < \frac{1}{2}$. 此时, 我们称$p_1$, $p_2$, $\cdots$, $p_k$为小质数, 称$p_{k+1}$, $p_{k+2}$, $\cdots$

则$\forall N \in N^+$, 都有
$$ \sum\limits_{i > k}{} \frac{N}{p_i} < \frac{N}{2} $$
令$N_b$表示满足$n <= N$且至少比一个大质数整除的正整数$n$的个数, $N_s$表示满足$n<=N$且因子都是小质数的正整数$n$的个数. 我们将证明
$$ N_b + N_s < N, $$
从而导出矛盾. 根据定义$N_b + N_s$ 应该是等于$N$的.

为估计$N_b$, 我们注意到$[\frac{N}{p_i}]$计数了所有满足$n <= N$的$p_i$的倍数, 于是
$$ N_b <= \sum\limits_{i>= k+1}{} [\frac{N}{p_i}] < \frac{N}{2} $$
再观察$N_s$, 把每个只有小质数因子的$n <= N$写成$n=a_n{b_n}^2$的形式, 这里$a_n$是没有平方因子的部分. 每个$a_n$也就是一些互异的小质数的成绩, 所以一共恰好有$2^k$个可供选择的没有平方因子的部分. 另一方面, 由于$b_n <= \sqrt{n} <= \sqrt{N}$, 最多有$\sqrt{N}$个不同的平方部分, 所以
$$ N_s <= 2^k\sqrt{N} $$
因为上式对于任意的$N$都成立, 只需找到一个满足$2^k\sqrt{N} <= \frac{N}{2}$的$N$就行了, 那么令$N = 2^{2k+2}$即可.

所以存在$k$使得$\sum\limits_{i >k}{} \frac{1}{p_i} < \frac{1}{2}$成立, 也即$\sum\limits_{p \in P}^{} \frac{1}{p}$收敛, 那么一定存在一个正整数$N$, 使得这个假设不成立, 所以$\sum\limits_{p \in P}^{} \frac{1}{p}$是发散的.

2. 完全数

(1). 完全数的定义

完全数是指恰好等于它的正因数之和的$\tfrac{1}{2}$的自然数
摘自百度百科

(2). 完全数的计算方式

正偶数$n$为完全数的充要条件为$n = 2^{p-1}(2^p - 1)$, 这里$p, 2^p-1$均为质数

引理: 记$\sigma(n)$为$n$的正因数个数
若$(a, b) = 1$, 则有$\sigma(a) \sigma(b) = \sigma(ab)$

引理的证明:
不妨设$ a = a_1^{\alpha_1} a_2^{\alpha_2} … a_n^{\alpha_n} $, $b = b_1^{\beta_1} b_2^{\beta_2} … b_m^{\beta_m}$
其中$a_1, a_2, …, a_n, b_1, b_2, …, b_m$互不相同, 且都为质数
则$ab = a_1^{\alpha_1} a_2^{\alpha_2} … a_n^{\alpha_n} b_1^{\beta_1} b_2^{\beta_2} … b_m^{\beta_m}$

$\sigma(a) \sigma(b) = [(1+a_1+a_1^2+…+a_1^{\alpha_1})…(1+a_n+a_n^2+…+a_n^{\alpha_n})][(1+b_1+b_1^2+…+b_1^{\beta_1})…(1+b_m+b_m^2+…+b_m^{\beta_m})] = \sigma(ab)$

充分性: 若$n = 2^{p-1}(2^p-1)$, 由引理, $\sigma(n) = \sigma(2^{p-1}) \sigma(2^p-1) = (2^p-1)2^p = 2n$.

必要性: 设$n = 2^{\alpha - 1}q, \alpha >= 2, q为奇数$
$\sigma(n) = 2n = 2^{\alpha}q = (2^{\alpha}-1)\sigma(q)............(1)$
显然, $(2^{\alpha}-1) | q$, 再证$q>2^{\alpha}-1$不成立
假设$q>2^{\alpha}-1$, 显然$q$至少有3个不同的因数$1 < \frac{q}{2^{\alpha}-1} < q$
于是$\sigma(q) >= 1+q+\frac{q}{2^{\alpha}-1}............(2)$
(2)带回(1), 得$2^{\alpha}q >= (2^{\alpha}-1)(1+q+\frac{q}{2^{\alpha}-1}) = 2^{\alpha}-1 + 2^{\alpha}q$
=> $2^{\alpha}-1 <= 0$与$\alpha >= 2$矛盾!

所以$q=2^{\alpha}-1$
于是$n = 2^{\alpha - 1}(2^{\alpha}-1)$
带入(1), 得: $\sigma(q) = 2^{\alpha} = 1+q$ => $q$为质数 => $\alpha$为质数
所以$n = 2^{p-1}(2^p-1)$, 其中$p$, $2^p-1$均为质数