1. 质数 Prime Numbers

可除性 Divisibility

定义

令 $n,d\in \mathbb Z$, 其中 $d\not = 0$ . 如果存在一个整数 $q$ 使得 $n = dq$, 则 $d$ 能整除 $n$ . 我们记作 $d|n$ . 如果 $d$ 不能整除 $n$ , 我们记作 $d\nmid n$ . 即

$d|n \Leftrightarrow (\exists q \in \mathbb Z)(n = dq)$

特殊情况

对于 $0|n$, 当且仅当 $n = 0$

质数定义

一个自然数 $p\ge 2$ 如果只能被 $1$ 和 $p$ 整除, 则称 $p$ 是质数.

其他定义法

自然数 $p\in \mathbb N$ 是质数当且仅当其有两个不同的因数（其实就是1和其本身），所有质数的集合是 $\mathbb N$

注

1. 1 不是质数

Mersenne 质数

形式满足 $2^n - 1$ 的质数形式
但是，不是所有的 n 都能形成质数，也不是多有的质数都可以表示为 这种形式
例： $2^{11} - 1 = 2047 = 23 \times 89$ 不是质数

Fermat 数（费马数）

形如 $F_n = 2 ^ {2^n} +1$ 的数

哥德巴赫猜想 Goldbach Conjecture

所有大于4的数字都可以表示为两个质数的和

质数无穷定理

质数有无穷个，证明有两个，分别为欧几里德证法和反证法，但是对于直觉逻辑学家来说，反证法并不是一个好的证明方法

欧几里德证明方法

对于一个有穷集合 $\{p_1,\cdots, p_r\} \subset \mathbb P$, 假设数字 $n = p_1 p_2\cdots p_r + 1$, 注意 $p_i \not | n $ 对于所有的 $i= 1\cdots , r$ 那么： 要么 n 是一个质数，要么n存在质因子 $p\not \in \{p_1\cdots,p_r\}$
在这两种情况中，都是向有限的质数集合添加了新的元素 从而达到扩大集合的目的，说明了对于任意质数集合，都是有更多元素的，所以集合元素是无穷的

欧几里德数

聪明的你一定会问 “为什么质数求积再加一一定与质数集合互质呢？”
或者说，你会想，如果集合是 从 2开始到某一个值的所有质数，那么他们的积加一是不是质数呢？答案是否定的，例如 $2\cdot 3\cdot 5\cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ 不是一个质数
所以我们称这个数为欧几里德数

$E_n = p_1 p_2 \cdots p_n + 1$

当然，你或许不知道欧几里德是谁，这就是古希腊《几何原本》的作者欧几里德

引理

对于 $p\in \mathbb P$, $n\in \mathbb N$, 如果 $p| n^2 + 1$ 那么 $p=2$ 或者 $p$ 的形式是 $4m+1$
这会在后面的讨论中被证明

狄利克雷定理 Dirichlet Theorem

对于 $n\in \mathbb N$ ,任意两个互质的正整数 $a,b$, 有无穷多个质数形如 $an+b$