初等数论#

整除#

带余除法

设 $a, b \in \mathbb Z$，$b \ne 0$，则存在唯一的 $q, r \in \mathbb Z$，满足 $a = qb + r$，$0 \le r < |b|$．

证明

考虑 $S = \{ a - qb : q \in \mathbb Z \} \cap \mathbb N_0$，显然 $S \neq \empty$ (Archimedes 公理)，由于 $(\mathbb N_0, \le)$ 是良序的，总可取 $r_0 = \min S$，设 $r_0 = a - q_0 b$．我们将证明 $r_0 < |b|$，且这样的 $r_0$ 是唯一的．(反证法) 假设 $r_0 \ge |b|$，则

$$0 \le r_0 - |b| = a - q_0 b - |b| \in S$$

这与 $r_0 = \min S$ 矛盾，故 $r_0 < |b|$，存在性得证．再设

$$a = q_1b + r_1 = q_2 b + r_2$$

其中 $q_1, r_1, q_2, r_2 \in \mathbb Z$，且 $r_1, r_2 \in [0, |b|)$，两式相减得

$$(q_1 - q_2)b = r_1 - r_2 \in (-|b|, |b|)$$

显然只有 $q_1 = q_2$，唯一性得证．

本质上，带余除法就是从数轴上的点 $a$ 出发，以 $b$ 为步进，移动至某个长度为 $|b|$ 半开半闭的目标区间内．

1. 因为步长和区间长一致，所以可达，区间内存在落点；
2. 因为区间半开半闭，区间内必然有且仅有一个落点．

推论

1. (零) 若 $a = 0$，则 $q = r = 0$．
2. (符号) 在数轴上，从点 $a$ 出发，到达 $[0, |b|)$ 内．当 $b > 0$ 时，$q > 0$ 表示左移，$q < 0$ 表示右移．

   $a$	$b$	$q$
   $+$	$+$	$\ge 0$
   $+$	$-$	$\le 0$
   $-$	$+$	$-$
   $-$	$-$	$+$

3. (折半) 若 $a \ge b > 0$，则 $r < a / 2$，即 $r < \min(|b|, a / 2)$．

推论 3 的证明

容易得知 $q > 0$，即 $q \ge 1$．(反证法) 假设 $r \ge a / 2$，则

$$0 < r < b \le qb = a - r \le a / 2$$

显然矛盾．

直观上讲，剃平后的 $a - r$ 是 $b$ 的倍数，故 $b \le a - r$，但又要 $b > r$，因此临界情况是折半．

C++

在 C/C++ 中，a / b 如何取整，取决于编译器的具体实现．
但从 C99 和 C++11 起，标准规定：商向零取整，即直接舍弃小数部分．
a % b 被定义为 a - a / b，因此取模结果的符号取决于 / 如何取整．以下断言保证为真：

1
assert(5 % 3 == 2);
2
assert(5 % -3 == 2);
3
assert(-5 % 3 == -2);
4
assert(-5 % -3 == -2);

形式化地，商向零取整的带余除法 $a = qb + r$ 中，$r$ 的目标区间不是 $[0, |b|)$，而是

$$r \in \begin{cases} [0, |b|), & a \ge 0, \\ (-|b|, 0], & a < 0. \end{cases}$$

整除

在带余除法 $a = qb + r$ 中，若 $r = 0$，称 $b$ 整除 $a$，$b$ 是 $a$ 的因数，$a$ 是 $b$ 的倍数，记作 $b \mid a$．

推论

1. (零) $n \mid 0$ 对 $n \ne 0$ 恒成立，即 $0$ 的因数是所有非零整数．
2. (幺) $n \mid 1$ 当且仅当 $n = \pm 1$，即 $1$ 的因数只有 $\pm 1$．
3. (凡因) $\pm 1 \mid n$ 和 $\pm n \mid n$ 都恒成立，即平凡因数．
4. (正负) $\pm a \mid \pm b$，$\pm a \mid \mp b$ 互相等价，即正负不影响因数组成．
5. (有界) 若 $a \mid b$ 且 $b \ne 0$，则 $|a| \le |b|$，即因数向 $0$ 靠拢．
6. (自反) 若 $a \mid b$ 且 $b \mid a$，则 $|a| = |b|$．
7. (传递) 若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$．
8. (消去) 若 $k \ne 0$，则 $ka \mid kb$ 等价于 $a \mid b$．
9. (分解) 若 $ab \mid m$，则 $a \mid m$ 且 $b \mid m$．
10. (组合) 若 $e \mid a$ 且 $e \mid b$，则 $e \mid (ka + lb)$，其中 $k, l \in \mathbb Z$．

推论 5 的证明

设 $b = ad \ne 0$，则 $d \ne 0$，即 $|d| \ge 1$，于是

$$|b| = |ad| = |a| |d| \ge |a|$$

GCD 和 LCM#

gcd 和 lcm

今有 $a, b \in \mathbb Z$，$a^2 + b^2 > 0$．记 $D$ 为 $a$ 和 $b$ 的正公因数集，$M$ 为 $a$ 和 $b$ 的正公倍数集．
我们称 $a$ 和 $b$ 的最大 (正) 公因数为 $\gcd(a, b) = \max D$，最小 (正) 公倍数 $\text{lcm}(a, b) = \min M$．

1. 由于 $1 \in D$，故 $D \ne \empty$，又因为 $d \le |a|$ 且 $d \le |b|$，因此 $D$ 是有限集，$\gcd(a, b)$ 必然存在；
2. 由于 $|ab| \in M$，故 $M \ne \empty$，又因为 $M \sub \mathbb N$，且 $(\mathbb N, \le)$ 是良序的，因此 $\text{lcm}(a, b)$ 必然存在．

gcd 的推论

1. (零) $\gcd(0, n) = n$，其中 $n \ne 0$．
2. (幺) $\gcd(1, n) = 1$．
3. (对称) $\gcd(a, b) = \gcd(b, a)$．
4. (正负) $\gcd(a, b) = \gcd(|a|, |b|)$．
5. (线性) 若 $k \in \mathbb Z$，$k \ne 0$，则 $\gcd(ka, kb) = |k|\gcd(a, b)$．
6. (幂性) 若 $k \in \mathbb Z$，则 $\gcd(a^k, b^k) = \gcd(a, b)^k$．
7. (最近公共祖先) $e \mid \gcd(a, b)$，当且仅当 $e \mid a$ 且 $e \mid b$．

推论 5 的证明

这里会使用到 Bézout 定理及其推论，详见下文．

一种证明方法是观察“张成空间”．

$$\gcd(ka, kb) \mathbb Z = \text{span}(ka, kb) = k \,\text{span}(a, b) = k \gcd(a, b) \mathbb Z$$

因此 $|\gcd(ka, kb)| = |k \gcd(a, b)|$，即 $\gcd(ka, kb) = |k| \gcd(a, b)$．

另一种证明方法是相互整除．

1. 先证 $k \gcd(a, b) \mid \gcd(ka, kb)$：由 Bézout 推论，只需证 $k\gcd(a, b) \mid ka$，消去 $k$ 后显然成立．
2. 再证 $\gcd(ka, kb) \mid k \gcd(a, b)$：欲将其转化为 $\gcd(ka, kb) / k \mid \gcd(a, b)$，需 $k \mid \gcd(ka, kb)$，而这是显然的，因为 $k \mid ka$，随后要证 $\gcd(ka, kb) / k \mid a$，两边同乘以 $k$ 显然成立． 因此 $|\gcd(ka, kb)| = |k \gcd(a, b)|$，即 $\gcd(ka, kb) = |k| \gcd(a, b)$．

推论 6 的证明

这里会使用到互素相关的结论，详见下文．
记 $d = \gcd(a, b)$，则 $\dfrac{a}{d} \perp \dfrac{b}{d}$，因此 $\Big(\dfrac{a}{d}\Big)^k \perp \Big(\dfrac{b}{d}\Big)^k$，

$$\gcd(a^k, b^k) = d^k \gcd\left(\Big(\dfrac{a}{d}\Big)^k, \Big(\dfrac{b}{d}\Big)^k\right) = d^k = \gcd(a, b)^k$$

推论 7 的证明

($\Rightarrow$) $e \mid \gcd(a, b) \mid a$，$e \mid \gcd(a, b) \mid b$．
($\Leftarrow$) 由 Bézout 定理，设 $\gcd(a, b) = ka + lb$，$k,l \in \mathbb Z$．由 $e \mid a$ 且 $e \mid b$ 得 $e \mid (ka + lb) = \gcd(a, b)$．

互素

若 $\gcd(a, b) = 1$，则称 $a$ 与 $b$ 互素，记作 $a \perp b$．

推论

1. (零) 与 $0$ 互素的整数只有 $\pm 1$．
2. (幺) $\pm 1$ 与所有整数互素．
3. (互素化) 记 $d = \gcd(a, b)$，则 $\dfrac{a}{d} \perp \dfrac{b}{d}$．
4. (排除异己) 若 $a \perp b$，则 $a \mid bc$ 蕴含 $a \mid c$．
5. (排除异己) 若 $a \perp b$，则 $\gcd(a, bc) = \gcd(a, c)$．
6. (Euclid 互素定理) $a \perp m$ 且 $b \perp m$，当且仅当 $ab \perp m$．
7. (互素组对) 若 $\forall\, i, j$ 有 $a_i \perp b_j$，则 $\prod_i a_i \perp \prod_j b_j$．
8. (互素乘积) 若 $a \perp b$，则 $a \mid m$ 且 $b \mid m$ 蕴含 $ab \mid m$．
9. (一般乘积) 记 $d = \gcd(a, b)$，则 $a \mid m$ 且 $b \mid m$ 蕴含 $\left. \dfrac{ab}{d} \,\middle|\, m \right.$，即 $\text{lcm}(a, b) \mid m$．
10. (互素空间的交) 若 $a \perp b$，则 $a \mathbb Z \cap b \mathbb Z = ab \mathbb Z$．
11. (一般空间的交) 记 $d = \gcd(a, b)$，则 $a \mathbb Z \cap b \mathbb Z = \dfrac{ab}{d} \, \mathbb Z = \text{lcm}(a, b) \,\mathbb Z$．

推论 3 的证明

记 $d = \gcd(a, b)$，则 $d \mid a$ 且 $d \mid b$，于是

$$d = \gcd(a, b) = d \gcd\Big(\dfrac{a}{d}, \dfrac{b}{d}\Big)$$

可得 $\gcd\Big(\dfrac{a}{d}, \dfrac{b}{d}\Big) = 1$，因此 $\dfrac{a}{d} \perp \dfrac{b}{d}$．

推论 4 的证明

$\gcd(a, b) = 1$，由 Bézout 定理，设

$$ka + lb = 1$$

由 $a \mid bc$，设 $ad = bc$．欲证 $a \mid c$，为消去 $b$，上式两边同乘以 $c$，代入得

$$kac + lbc = kac + lad = a(kc + ld) = c$$

因此 $a \mid c$．

推论 5 的证明

设 $d = \gcd(a, bc)$，$e = \gcd(a, c)$．
由 $a \perp b$ 得 $d \perp b$，又 $d \mid bc$，故 $d \mid c$，结合 $d \mid a$ 可得 $d \mid e$．
由 $e \mid a$ 且 $e \mid c \mid bc$ 得 $e \mid d$．
故 $|d| = |e|$，即 $d = e$．

推论 6 的证明

下面使用 Bézout 定理进行证明：

($\Rightarrow$) 存在 $k_1, l_1, k_2, l_2 \in \mathbb Z$，使得

$$\begin{aligned} k_1a + l_1m &= 1 \\ k_2b + l_2m &= 1 \end{aligned}$$

两式相乘，整理得

$$(k_1k_2)ab + (k_1l_2a + k_2l_1b + l_1l_2m)m = 1$$

于是 $\gcd(ab, m) = 1$，因此 $ab \perp m$．

($\Leftarrow$) 存在 $k, l \in \mathbb Z$，使得

$$kab + lm = 1$$

我们有

$$\begin{aligned} (kb)a + lm &= 1 \\ (ka)b + lm &= 1 \end{aligned}$$

于是 $\gcd(a, m) = 1$ 且 $\gcd(b, m) = 1$，因此 $a \perp m$ 且 $b \perp m$．

从算术基本定理的角度来看，这个定理是显然的．

推论 8 的证明

由于 $a \mid m$，$b \mid m$，不妨设 $m = ak$，则 $b \mid ak$，又因为 $b \perp a$，所以 $b \mid k$，从而 $ab \mid ak = m$．

推论 9 的证明

记 $d = \gcd(a, b)$，由于 $a \mid m$ 且 $b \mid m$，不妨设 $m = ak$．
则 $b \mid ak$，$\left. \dfrac{b}{d} \,\middle|\, \dfrac{a}{d}k \right.$，而 $\dfrac{b}{d} \perp \dfrac{a}{d}$，故 $\left. \dfrac{b}{d} \,\middle|\, k \right.$，因此 $\left. \dfrac{ab}{d} \,\middle|\, ak \right. = m$．

推论 10 的证明

记 $M_1 = a \mathbb Z \cap b \mathbb Z$，$M_2 = ab \mathbb Z$．
任取 $m \in M_1$，则 $a \mid m$ 且 $b \mid m$，又因 $a \perp b$，故 $ab \mid m$，即 $m \in M_2$，于是 $M_1 \sub M_2$．
任取 $m \in M_2$，则 $ab \mid m$，得 $a \mid m$ 且 $b \mid m$，即 $m \in M_1$，于是 $M_2 \sub M_1$．
故 $M_1 = M_2$．

推论 11 的证明

记 $d = \gcd(a, b)$，$M_1 = a \mathbb Z \cap b \mathbb Z$，$M_2 = \dfrac{ab}{d} \, \mathbb Z$．
任取 $m \in M_1$，则 $a \mid m$ 且 $b \mid m$，于是 $\left. \dfrac{ab}{d} \,\middle|\, m \in M_2 \right.$，因此 $M_1 \sub M_2$．
任取 $m \in M_2$，则 $\left. \dfrac{ab}{d} \,\middle|\, m \right.$，得 $a \mid m$ 且 $b \mid m$，于是 $m \in M_1$，因此 $M_2 \sub M_1$．
综上，$M_1 = M_2$．

lcm 的推论

1. 若 $\gcd(a, b) = 1$，则 $\text{lcm}(a, b) = |ab|$．
2. $\gcd(a, b) \,\text{lcm}(a, b) = |ab|$．

推论 1 的证明

任取 $a$ 和 $b$ 的 (正) 公倍数 $m$，则 $a \mid m$ 且 $b \mid m$，又因 $\gcd(a, b) = 1$，于是 $ab \mid m$．得 $|ab| \le m$，而 $|ab|$ 也是 $a$ 和 $b$ 的 (正) 公倍数，因此等号可以成立，$\text{lcm}(a, b) = |ab|$．

更直接的证法是：因为 $a \perp b$，所以公倍数集

$$a \mathbb Z \cap b \mathbb Z = ab \mathbb Z$$

于是 $\text{lcm}(a, b) = |ab|$．

推论 2 的证明

可以通过相互整除证明，下面使用更直接的证明方法：

$$a \mathbb Z \cap b \mathbb Z = \dfrac{ab}{\gcd(a, b)} \mathbb Z$$

于是 $\text{lcm}(a, b) = \left|\dfrac{ab}{\gcd(a, b)}\right|$，即 $\gcd(a, b) \,\text{lcm}(a, b) = |ab|$．

Bézout 定理#

辗转相除法

设 $a, b \in \mathbb Z$，且 $a^2 + b^2 > 0$，带余除法 $a = qb + r$，只要 $|a - qb| < |b|$，算法

$$\gcd(a, b) = \gcd(b, a - qb) = \cdots$$

将终止于 $\gcd(d, 0)$，此时 $|d|$ 即为 $\gcd(a, b)$．

正确性证明

记 $D_{ab}$ 为 $a$ 和 $b$ 的公因数集，$D_{br}$ 为 $b$ 和 $r$ 的公因数集，我们将证明 $D_{ab} = D_{br}$．
任取 $d \in D_{ab}$，则 $d \mid (a - qb) = r$，故 $d \in D_{br}$，即 $D_{ab} \sub D_{br}$．
又任取 $d \in D_{br}$，则 $d \mid (qb + r) = a$，故 $d \in D_{ab}$，即 $D_{br} \sub D_{ab}$．
因此 $D_{ab} = D_{br}$，从而 $\gcd(a, b) = \gcd(b, r)$，即 $\gcd(a, b) = \gcd(b, a - qb)$．

容易归纳证明 (固定步数后，寻找最小的一组 $a$ 和 $b$ 作为最差情况)，当 $a$ 和 $b$ 为 Fibonacci 数列邻项时，算法达到最差计算复杂度 $O(\log \min (a, b))$．由于每次带余除法都将余数折半，因此该算法十分高效．

向零取整

我们看到，辗转相除法的正确性仅依赖于 $a$ 和 $r$ 互相被线性组合表示，不过可终止性依赖于 $|a - qb| < |b|$，因此可以让带余除法的商向零取整，即 C/C++ 的整数除法．

1
void gcd(i64 a, i64 b, i64 &d) {
2
    assert(a != 0 || b != 0);
3
    i64 *cur, *pre;
4
    for (cur = &a, pre = &b; *pre; std::swap(cur, pre)) {
5
        if (std::abs(*cur) >= std::abs(*pre)) {
6
            i64 q = (*cur) / (*pre);
7
            (*cur) -= q * (*pre);
8
        }
9
    }
10
    d = *cur;
11
    if (d < 0) d = -d;
12
}

Bézout 定理

总存在 $k,l \in \mathbb Z$，使得 $\gcd(a, b) = ka + lb$，即最大公因数总能用线性组合表示．

证明

考虑辗转相除法

$$\begin{aligned} a &= q_1 b + r_1 \\ &\hspace{0.525em}\vdots \\ r_{N-2} &= q_N r_{N-1} + r_N \\ r_{N-1} &= q_{N+1} r_{N} \end{aligned}$$

$r_1$ 和 $r_2$ 都可以表示成 $a$ 和 $b$ 的线性组合，归纳得知 $r_N$ 也可以，$\gcd(a, b) = |r_N|$ 也可以．

推论

记 $\text{span}(a, b) = \{ka + lb : k,l \in \mathbb Z\}$，则 $\text{span}(a, b) = \gcd(a, b) \mathbb Z$．

证明

记 $S_{ab} = \text{span}(a, b)$，$d = \gcd(a, b)$．由 Bézout 定理知 $d \in S_{ab}$，容易得到 $d \mathbb Z \sub S_{ab}$．另一方面，任取 $ka + lb \in S_{ab}$，有 $ka + lb = (ka / d + lb / d) d \in d \mathbb Z$，于是 $S_{ab} \sub d \mathbb Z$．因此 $S_{ab} = d \mathbb Z$．

可以说 $\gcd$ 是“张成空间”的基，它告诉了我们有关该线性组合的全部信息．只要我们得到了 $\gcd$，就能有序地获取所有线性组合．我们也可以通过观察“张成空间”来反推 $\gcd$ 的一些性质．

循环群的子群

循环群 $G = \langle g \rangle$ 的子群 $H$ 必为循环群．设 $I = \{k \in \mathbb Z : g^k \in H\}$，则 $H = \{g^k \in G : k \in I\}$．

1. 若 $H$ 是平凡群，显然也是循环群；
2. 否则取 $d = \gcd\,I$，由 Bézout 定理可知，$d$ 可被 $I$ 中所有数的线性组合表示．
   因为 $H$ 的封闭性，所以 $d \in I$．我们将证明 $H = \langle g^d \rangle$：一方面 $\forall\, k \in I$，$d \mid k$，故 $I \sub d \mathbb Z$；
   另一方面 $H$ 是群，容易得知 $I$ 是 $\mathbb Z$ 的加法子群，又因为 $d \in I$，故 $d \mathbb Z \sub I$．
   所以 $I = d \mathbb Z$，$H = \{g^{dk} \in G : {dk} \in d \mathbb Z\} = \{(g^d)^k \in G : k \in \mathbb Z\} = \langle g^d \rangle$．

扩展 Euclid 算法

设 $a, b \in \mathbb Z$，且 $a^2 + b^2 > 0$，欲寻找 $\gcd(a, b)$ 其中一种线性组合表示．考虑从

$$\begin{cases} 1 \cdot a + 0 \cdot b = a \\ 0 \cdot a + 1 \cdot b = b \end{cases}$$

开始，对其增广矩阵

$$\begin{pmatrix} 1 & 0 & a \\ 0 & 1 & b \end{pmatrix}$$

进行有限次初等行变换，最终得到行

$$\begin{pmatrix} k & l & \gcd(a, b) \end{pmatrix}$$

对应的方程正是

$$ka + lb = \gcd(a, b)$$

而这只需让每次初等行变换对应于增广列的辗转相除法的每一步即可：

$$\cdots \rightarrow \begin{pmatrix} s & t & g \\ m & n & h \end{pmatrix} \rightarrow \begin{pmatrix} m & n & h \\ s-qm & t-qn & g-qh \end{pmatrix} \rightarrow \cdots \rightarrow \begin{pmatrix} k & l & \gcd(a, b) \\ K & L & 0 \end{pmatrix}$$

1
void exgcd(i64 a, i64 b, i64 &x, i64 &y, i64 &d) {
2
    assert(a != 0 || b != 0);
3
    i64 M[2][3] = {{1, 0, a}, {0, 1, b}};
4
    i64 *cur, *pre;
5
    for (cur = M[0], pre = M[1]; pre[2]; std::swap(cur, pre)) {
6
        if (std::abs(cur[2]) >= std::abs(pre[2])) {
7
            i64 q = cur[2] / pre[2];
8
            cur[0] -= q * pre[0];
9
            cur[1] -= q * pre[1];
10
            cur[2] -= q * pre[2];
11
        }
12
    }
13
    x = cur[0], y = cur[1], d = cur[2];
14
    if (d < 0) x = -x, y = -y, d = -d;
15
}

线性不定方程的特解

线性不定方程 $ax + by = m$ 有解，当且仅当 $\gcd(a, b) \mid m$．
此时设 $m = e \gcd(a, b)$，取 $\gcd(a, b) = ka + lb$，则

$$m = e(ka + lb) = a \cdot ek + b \cdot el$$

得到特解 $(x_0, y_0) = (ek, el)$．

线性不定方程的通解

若线性不定方程 $ax + by = m$ 有特解 $(x_0, y_0)$，则通解 ($k \in \mathbb Z$) 为

$$\begin{cases} x = x_0 + k \cdot \dfrac{b}{\gcd(a, b)} \\[1em] y = y_0 - k \cdot \dfrac{a}{\gcd(a, b)} \end{cases}$$

通解的证明

已有 $ax_0 + by_0 = m$，再设通解 $(x, y)$ 满足 ，则

$$a(x - x_0) = b(y_0 - y)$$

对 $a$ 和 $b$ 互素化，得

$$\dfrac{a}{\gcd(a, b)}(x - x_0) = \dfrac{b}{\gcd(a, b)}(y_0 - y)$$

于是

$$\left. \dfrac{a}{\gcd(a, b)} \,\middle|\, \dfrac{b}{\gcd(a, b)}(y_0 - y) \right.$$

又因为 $\dfrac{a}{\gcd(a, b)} \perp \dfrac{b}{\gcd(a, b)}$，故

$$\left. \dfrac{a}{\gcd(a, b)} \,\middle|\, (y_0 - y) \right.$$

可设 $\dfrac{a}{\gcd(a, b)} \cdot k = y_0 - y$，$k \in \mathbb Z$，代回 $a(x - x_0) = b(y_0 - y)$ 得证．

素数#

素数

设 $n \in \mathbb N$ 且 $n > 1$，若 $n$ 因数只有 $1$ 和 $n$，则称 $n$ 是素数，否则是合数．

负素数？

在整环 $(R, +, \cdot)$ 中，若元素 $p \in R$ 满足

1. 非零元：$p \ne 0$；
2. 非单位：$\nexists\, q$，$pq = 1$，即 $p$ 不是可逆元；
3. 素性：$\forall a, b \in R$，若 $p \mid ab$ (即 $\exists\, k \in R$，$ab = pk$)，则 $p \mid a$ 或 $p \mid b$．

则称 $p$ 为素元．

由于正负不影响整除关系，我们可以在 $\mathbb Z$ 上定义负素数：$p$ 和 $-p$ 总是同为素数或同为合数．但这会让各种描述变得拗口，因此若无特殊说明，以下内容的论域均为 $\mathbb N$：素数一般指正素数，因数一般指正因数．

推论

1. $\mathbb N$ 被分为三类：$1$，素数，合数．
2. 合数的最小非平凡因数是素数．
3. 素数有无穷多个．
4. (素性，Euclid 整除定理) 设 $a, b \in \mathbb Z$，$p$ 是素数，若 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$．

推论 2 的证明

设 $N$ 是合数，其最小非平凡因数 $p$ 满足 $1 < p < N$ 且 $p \mid N$．
假设 $p$ 是合数，任取其非平凡因数 $q$ 满足 $1 < q < p$ 且 $q \mid p$．
于是 $q \mid N$，这与 $p$ 是 $N$ 的最小非平凡因数矛盾．
因此 $p$ 是素数．

推论 3 的证明

(反证法) 假设仅有的 $k$ 个素数为 $\{p_k\}_{i=1}^k$．
令 $N = \prod_{i=1}^k p_i + 1$，显然 $1 < p_i < N$，$i = 1, \cdots, k$，因此 $N$ 是合数．
取 $N$ 的最小非平凡因数 $p$，则 $p \mid N$ 且 $p$ 是素数．设 $p = p_i$，那么 $p \mid \prod_{i=1}^k p_i$．
故 $p \mid (N - \prod_{i=1}^k p_i) = 1$，即 $p = 1$，这与 $p$ 是素数矛盾．
因此素数有无穷多个．

推论 4 的证明

若 $p \mid a$ 则证明完毕，于是设 $p \nmid a$，考虑是否有 $p \perp a$ 从而有 $p \mid b$．
由于素数 $p$ 只有因数 $1$ 和 $p$，所以 $\gcd(p, a)$ 只可能是 $1$ 或 $p$，而 $p \nmid a$，所以 $\gcd(p, a) = 1$．
因为 $p \mid ab$，且 $p \perp a$，所以 $p \mid b$．

素性意味着不可分解，是素数的本质，等价于算数基本定理中分解的唯一性．

算术基本定理

对于所有的 $n \in \mathbb N$ 且 $n > 1$，都存在唯一的素因数分解

$$n = \prod_{i=1}^k p_i^{\alpha_i}$$

其中 $p_i$ 是素数且互异，$\alpha_i \in \mathbb N$，$i = 1, \cdots, k$．

证明

若 $n$ 是素数，则分解完成．若 $n$ 是合数，取其最小非平凡因数 $1 < p < n$，则 $p$ 是素数．
$p$ 的唯一性是显然的，因此下面对 $n$ 的分解也是唯一的．

$$n = p \cdot \dfrac{n}{p}$$

对 $\dfrac{n}{p}$ 重复上述分解操作．由于 $\dfrac{n}{p} < n$，分解将终止，便得到 $n$ 唯一的素因数分解．

虽然有更严谨的归纳证明，但比较麻烦，个人更喜欢简洁的程序证明．

同余#

同余

若 $m \mid (a - b)$，则称 $a$ 与 $b$ 模 $m$ 同余，记作

$$a \equiv b \pmod m$$

容易证明，这等价于在带余除法 $a = q_1m + r_1$ 和 $b = q_2m + r_2$ 中，$r_1 = r_2$．

负模数？

由于正负不影响整除关系，$a \equiv b \pmod m$ 等价于 $a \equiv b \pmod{(-m)}$．

因此若无特殊说明，模数 $m$ 总是正整数．

推论

1. 同余是等价关系：
   • 自反性：$a \equiv a \pmod m$；
   • 对称性：若 $a \equiv b \pmod m$，则 $b \equiv a \pmod m$；
   • 传递性：若 $a \equiv b \pmod m$，$b \equiv c \pmod m$，则 $a \equiv c \pmod m$．
2. 线性运算：若 $a \equiv b \pmod m$，$c \equiv d \pmod m$，则
   • 同余式的和：$a + c \equiv b + d \pmod m$；
   • 同余式的积：$ac \equiv bd \pmod m$．
3. 一般缩放：若 $k \in \mathbb Z$，且 $k \ne 0$，则 $ka \equiv kb \pmod{km}$ 等价于 $a \equiv b \pmod m$．
4. 模数因数：若 $a \equiv b \pmod {km}$，则 $a \equiv b \pmod m$．
5. 互素消去：若 $ka \equiv kb \pmod m$，且 $k \perp m$，则 $a \equiv b \pmod m$．
6. 一般消去：若 $ka \equiv kb \pmod m$，则 $a \equiv b \pmod{\dfrac{m}{\gcd(k, m)}}$．