素数

设整数 $p\ne 0,\pm 1$. 如果 $p$ 除了平凡约数外没有其他约数，那么称 $p$ 为 素数（质数，不可约数）.

若整数 $a\ne 0,\pm 1$ 且 $a$ 不是素数，则称 $a$ 为 合数.

$p$ 和 $-p$ 总是同为素数或者同为合数. 如果没有特别说明，素数总是指正的素数.

整数的因数是素数，则该素数称为该整数的 素因数（素约数）.

素数与合数的简单性质

• 大于 $1$ 的整数 $a$ 是合数，等价于 $a$ 可以表示为整数 $d$ 和 $e$（$1<d,e<a$）的乘积.
• 如果素数 $p$ 有大于 $1$ 的约数 $d$，那么 $d=p$.
• 大于 $1$ 的整数 $a$ 一定可以表示为素数的乘积.
• 对于合数 $a$，一定存在素数 $p\le \sqrt{a}$ 使得 $p\mid a$.
• 素数有无穷多个.
• 所有大于 $3$ 的素数都可以表示为 $6k\pm 1$ 的形式.
• 有无数个形如 $4k+3$ 的素数.

证明素数有无穷多个

假设只有有限个素数 $p_1,\dots ,p_n$，令

$$Q_n=p_1{p}_2\dots p_n+1$$

$Q_n$ 一定有一个质因数，为 $q$.

若 $q$ 在 $p_1,\dots ,p_n$ 中 ，则 $q\mid Q_n$，$q\mid Q_n-p_1{p}_2...p_n=1$，$q\mid 1$，矛盾. 所以 $q$ 不在 $p_1,\dots ,p_n$ 中，所以有无限个素数.

证明有无数个形如 $4k+3$ 的素数

假设有有限个这样的素数 $p_1,\dots ,p_n$，令

$$m=4p_1\dots p_n-1=4(p_1\dots p_n-1)+3$$

由假设知 $m$ 是合数. 因为 $m$ 是奇数，所以 $2$ 不可以整除 $m$. 那么 $m$ 所有素因子 $p$ 都是奇数.

所以 $p$ 有两种情况，$4k＋1$ 型和 $4k＋3$ 型.

若所有的素因子都形如 $4k＋1$，则 $m$ 也是 $4k＋1$ 型，矛盾，所以一定有至少一个 $p$ 是 $4k＋3$ 型.

那么 $p$ 就一定在前面提到的有限个这样的素数 $p_1,\dots ,p_n$ 中，$p=p_i$，那么 $p\mid 4p_1\dots p_n-m=1$ 矛盾，所以有无限个形如 $4k＋3$ 的素数.

证明有无数个形如 $4k+1$ 的素数

假设有有限个这样的素数 $p_1,\dots ,p_n$，令

$$m=(2p_1\dots p_n{)}^2+1$$

由假设知 $m$ 是合数. 因为 $m$ 是奇数，所以 $2$ 不可以整除 $m$. 那么 $m$ 所有素因子 $p$ 都是奇数.

所以对于素因子 $p$ 有

$$\begin{gathered} m=(2p_1\dots p_n{)}^2+1\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p) \\ (2p_1\dots p_n{)}^2\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p) \end{gathered}$$

所以 $-1$ 是 $p$ 的二次剩余，所以 $p$ 是 $4k+1$ 型. （见二次剩余）

所以 $p$ 在 $p_1,\dots ,p_n$ 中. 那么 $p\mid m-(2p_1\dots p_n{)}^2=1$ 矛盾，所以有无限个形如 $4k＋1$ 的素数.