数论基础

Enryh2024年10月9日大约 8 分钟唯一分解定理辗转相除法

整除

定义

设 $a, b \in Z$ ， $a \neq 0$ 。如果 $\exists q \in Z$ ，使得 $b = a q$ ，那么就说 $b$ 可被 $a$ 整除，记作 $a ∣ b$ ；

$b$ 不被 $a$ 整除记作 $a ∤ b$ 。

整除的性质：

$a ∣ b ⟺ - a ∣ b ⟺ a ∣ - b ⟺ | a | ∣ | b |$
$a ∣ b \land b ∣ c ⟹ a ∣ c$
$a ∣ b \land a ∣ c ⟺ \forall x, y \in Z, a ∣ (x b + y c)$
$a ∣ b \land b ∣ a ⟹ b = \pm a$
设 $m \neq 0$ ，那么 $a ∣ b ⟺ m a ∣ m b$ 。
设 $a \neq 0, b = q a + c$ ，那么 $a ∣ b ⟺ a ∣ c$ 。

约数

定义

若 $a ∣ b$ ，则称 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数。

$0$ 是所有非 $0$ 整数的倍数。对于整数 $b \neq 0$ ， $b$ 的约数只有有限个。

平凡约数（平凡因数）：对于整数 $b \neq 0$ ， $\pm 1$ 、 $\pm b$ 是 $b$ 的平凡约数。当 $b = \pm 1$ 时， $b$ 只有两个平凡约数。

对于整数 $b \neq 0$ ， $b$ 的其他约数称为真约数（真因数、非平凡约数、非平凡因数）。

约数的性质：

设整数 $b \neq 0$ 。当 $d$ 遍历 $b$ 的全体约数的时候， $\frac{b}{d}$ 也遍历 $b$ 的全体约数。
设整数 $b > 0$ ，则当 $d$ 遍历 $b$ 的全体正约数的时候， $\frac{b}{d}$ 也遍历 $b$ 的全体正约数。

解释

假设我们有整数 $b$ ，当我们遍历 $b$ 的每一个约数 $d$ 时， $\frac{b}{d}$ 也会是 $b$ 的一个约数。这是因为：

如果 $d$ 是 $b$ 的约数，那么存在一个整数 $k$ ，使得 $b = d \cdot k$ 。反过来， $\frac{b}{d} = k$ 也是一个整除 $b$ 的整数，因此也是 $b$ 的约数。
当我们让 $d$ 遍历 $b$ 的所有约数时， $\frac{b}{d}$ 也会遍历所有约数。

举例：设 $b = 12$ 。 $12$ 的约数有 $1, 2, 3, 4, 6, 12$ 。当我们让 $d$ 遍历这些约数时：

$d = 1$ ，则 $\frac{b}{d} = \frac{12}{1} = 12$ ；
$d = 2$ ，则 $\frac{b}{d} = \frac{12}{2} = 6$ ；
$d = 3$ ，则 $\frac{b}{d} = \frac{12}{3} = 4$ ；
$d = 4$ ，则 $\frac{b}{d} = \frac{12}{4} = 3$ ；
$d = 6$ ，则 $\frac{b}{d} = \frac{12}{6} = 2$ ；
$d = 12$ ，则 $\frac{b}{d} = \frac{12}{12} = 1$ 。

可以看出，当 $d$ 遍历 $12$ 的所有约数时， $\frac{b}{d}$ 也遍历了 $12$ 的所有约数。

当 $b$ 是正整数时，它的约数也是正数。如果我们让 $d$ 遍历 $b$ 的所有正约数， $\frac{b}{d}$ 也会是 $b$ 的一个正约数。这是因为：

如果 $d$ 是 $b$ 的一个正约数，那么 $\frac{b}{d}$ 也是 $b$ 的一个正约数。
当 $d$ 遍历 $b$ 的所有正约数时， $\frac{b}{d}$ 也会遍历所有正约数。

举例：同样设 $b = 12$ ，它的正约数是 $1, 2, 3, 4, 6, 12$ 。当 $d$ 遍历这些正约数时， $\frac{b}{d}$ 也遍历了相同的正约数，如前面的例子所示。

总结：当我们遍历一个整数 $b$ 的所有约数（或正约数）时，约数的形式 $\frac{b}{d}$ 也会覆盖同样的约数。这表明约数在这两个集合中是成对出现的：一个约数 $d$ 和它对应的 $\frac{b}{d}$ 会互为约数。

在具体问题中，如果没有特别说明，约数总是指正约数。

带余数除法

余数定义

设 $a, b$ 为两个给定的整数， $a \neq 0$ 。设 $d$ 是一个给定的整数。那么，一定存在唯一的一对整数 $q$ 和 $r$ ，满足 $b = q a + r, d \leq r < | a | + d$ 。

无论整数 $d$ 取何值， $r$ 统称为余数。 $a ∣ b$ 等价于 $a ∣ r$ 。

一般情况下， $d$ 取 $0$ ，此时等式 $b = q a + r, 0 \leq r < | a |$ 称为带余数除法（带余除法）。这里的余数 $r$ 称为最小非负余数。

余数往往还有两种常见取法：

绝对最小余数： $d$ 取 $a$ 的绝对值的一半的相反数。即 $b = q a + r, - \frac{| a |}{2} \leq r < | a | - \frac{| a |}{2}$ 。
最小正余数： $d$ 取 $1$ 。即 $b = q a + r, 1 \leq r < | a | + 1$ 。

带余数除法的余数只有最小非负余数。如果没有特别说明，余数总是指最小非负余数。

余数的性质：

任一整数被正整数 $a$ 除后，余数一定是且仅是 $0$ 到 $(a - 1)$ 这 $a$ 个数中的一个。
相邻的 $a$ 个整数被正整数 $a$ 除后，恰好取到上述 $a$ 个余数。特别地，一定有且仅有一个数被 $a$ 整除。

最大公约数与最小公倍数

关于公约数、公倍数、最大公约数与最小公倍数，四个名词的定义，见最大公约数。

注意

一些作者认为 $0$ 和 $0$ 的最大公约数无定义，其余作者一般将其视为 $0$ 。C++ STL 的实现中采用后者，即认为 $0$ 和 $0$ 的最大公约数为 $0$ 。

最大公约数有如下性质：

$(a_{1}, \dots, a_{n}) = (| a_{1} |, \dots, | a_{n} |)$ ；
$(a, b) = (b, a)$ ；
若 $a \neq 0$ ，则 $(a, 0) = (a, a) = | a |$ ；
$(b q + r, b) = (r, b)$ ；
$(a_{1}, \dots, a_{n}) = ((a_{1}, a_{2}), a_{3}, \dots, a_{n})$ 。进而 $\forall 1 < k < n - 1, (a_{1}, \dots, a_{n}) = ((a_{1}, \dots, a_{k}), (a_{k + 1}, \dots, a_{n}))$ ；
对不全为 $0$ 的整数 $a_{1}, \dots, a_{n}$ 和非零整数 $m$ ， $(m a_{1}, \dots, m a_{n}) = | m | (a_{1}, \dots, a_{n})$ ；
对不全为 $0$ 的整数 $a_{1}, \dots, a_{n}$ ，若 $(a_{1}, \dots, a_{n}) = d$ ，则 $(a_{1} / d, \dots, a_{n} / d) = 1$ ；
$(a^{n}, b^{n}) = (a, b)^{n}$ 。

最大公约数还有如下与互素相关的性质：

若 $b | a c$ 且 $(a, b) = 1$ ，则 $b ∣ c$ ；
若 $b | c$ 、 $a | c$ 且 $(a, b) = 1$ ，则 $a b ∣ c$ ；
若 $(a, b) = 1$ ，则 $(a, b c) = (a, c)$ ；
若 $(a_{i}, b_{j}) = 1, \forall 1 \leq i \leq n, 1 \leq j \leq m$ ，则 $(\prod_{i} a_{i}, \prod_{j} b_{j}) = 1$ 。特别地，若 $(a, b) = 1$ ，则 $(a^{n}, b^{m}) = 1$ ；
对整数 $a_{1}, \dots, a_{n}$ ，若 $\exists v \in Z, \prod_{i} a_{i} = v^{m}$ ，且 $(a_{i}, a_{j}) = 1, \forall i \neq j$ ，则 $\forall 1 \leq i \leq n, \sqrt[m]{a_{i}} \in Z$ 。

最小公倍数有如下性质：

$[a_{1}, \dots, a_{n}] = [| a_{1} |, \dots, | a_{n} |]$ ；
$[a, b] = [b, a]$ ；
若 $a \neq 0$ ，则 $[a, 1] = [a, a] = | a |$ ；
若 $a ∣ b$ ，则 $[a, b] = | b |$ ；
$[a_{1}, \dots, a_{n}] = [[a_{1}, a_{2}], a_{3}, \dots, a_{n}]$ 。进而 $\forall 1 < k < n - 1, [a_{1}, \dots, a_{n}] = [[a_{1}, \dots, a_{k}], [a_{k + 1}, \dots, a_{n}]]$ ；
若 $a_{i} ∣ m, \forall 1 \leq i \leq n$ ，则 $[a_{1}, \dots, a_{n}] ∣ m$ ；
$[m a_{1}, \dots, m a_{n}] = | m | [a_{1}, \dots, a_{n}]$ ；
$[a, b, c] [a b, b c, c a] = [a, b] [b, c] [c, a]$ ；
$[a^{n}, b^{n}] = [a, b]^{n}$ 。

最大公约数和最小公倍数可以组合出很多奇妙的等式，如：

$(a, b) [a, b] = | a b |$ ；
$(a b, b c, c a) [a, b, c] = | a b c |$ ；
$\frac{(a, b, c)^{2}}{(a, b) (b, c) (a, c)} = \frac{[a, b, c]^{2}}{[a, b] [b, c] [a, c]}$ 。

这些性质均可通过定义或唯一分解定理证明，其中使用唯一分解定理的证明更容易理解。

互素

定义

若 $(a_{1}, a_{2}) = 1$ ，则称 $a_{1}$ 和 $a_{2}$ 互素（既约）。若 $(a_{1}, \dots, a_{k}) = 1$ ，则称 $a_{1}, \dots, a_{k}$ 互素（既约）。

多个整数互素，不一定两两互素。例如 $6$ 、 $10$ 和 $15$ 互素，但是任意两个都不互素。

辗转相除法

辗转相除法是一种算法，也称 Euclid 算法。见最大公约数。

素数与合数

关于素数的算法见素数。

定义

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

若整数 $a \neq 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 \leq \sqrt{a}$ 使得 $p ∣ a$ 。
素数有无穷多个。
所有大于 $3$ 的素数都可以表示为 $6 n \pm 1$ 的形式[^ref1]。

算术基本定理

算术基本引理

设 $p$ 是素数， $p ∣ a_{1} a_{2}$ ，那么 $p ∣ a_{1}$ 和 $p ∣ a_{2}$ 至少有一个成立。

算术基本引理是素数的本质属性，也是素数的真正定义。

算术基本定理（唯一分解定理）

设正整数 $a$ ，那么必有表示：

a = p_{1} p_{2} \dots p_{s}

其中 $p_{j} (1 \leq j \leq s)$ 是素数。并且在不计次序的意义下，该表示唯一。

标准素因数分解式

将上述表示中，相同的素数合并，可得：

a = {p_{1}}^{α_{1}} {p_{2}}^{α_{2}} \dots {p_{s}}^{α_{s}}, p_{1} < p_{2} < \dots < p_{s}

称为正整数 $a$ 的标准素因数分解式。

算术基本定理和算术基本引理，两个定理是等价的。

C/C++ 的整数除法和取模运算

在 C/C++ 中，整数除法和取模运算，与数学上习惯的取模和除法不一致。

对于所有标准版本的 C/C++，规定在整数除法中：

当除数为 0 时，行为未定义；
否则 (a / b) * b + a % b 的运算结果与 a 相等。

也就是说，取模运算的符号取决于除法如何取整；而除法如何取整，这是实现定义的（由编译器决定）。

从 C99 和 C++11 标准版本起，规定 商向零取整（舍弃小数部分）；取模的符号即与被除数相同。从此以下运算结果保证为真：

5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;