数论基础

本文对于数论的开头部分做一个简介。

整除

定义

设 $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$ 。
设 $b \neq 0$ ，那么 $a ∣ b ⟹ | a | \leq | 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$ 的全体正约数。

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

带余数除法

余数

设 $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$ 整除。

最大公约数与最小公倍数

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

Warning

一些作者认为 $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$ 互素，但是任意两个都不互素。

互素的性质与最大公约数理论：裴蜀定理（Bézout's identity）。见裴蜀定理。

辗转相除法

辗转相除法是一种算法，也称 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$ 的形式²。

算术基本定理

算术基本引理

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

算术基本引理的逆命题稍加修改也可以得到素数的另一种定义。

素数的另一种定义

对整数 $p \neq 0, \pm 1$ ，若对任意满足 $p ∣ a_{1} a_{2}$ 的整数 $a_{1}, a_{2}$ 均有 $p ∣ a_{1}$ 或 $p ∣ a_{2}$ 成立，则称 $p$ 是素数。

Tip

这个定义的动机可以从素理想中找到。

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

设正整数 $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$ 的标准素因数分解式。

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

同余

定义

设整数 $m \neq 0$ 。若 $m ∣ (a - b)$ ，称 $m$ 为模数（模）， $a$ 同余于 $b$ 模 $m$ ， $b$ 是 $a$ 对模 $m$ 的剩余。记作 $a \equiv b (\mod m)$ 。

否则， $a$ 不同余于 $b$ 模 $m$ ， $b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a ≢ b (\mod m)$ 。

这样的等式，称为模 $m$ 的同余式，简称 同余式。

根据整除的性质，上述同余式也等价于 $a \equiv b (\mod (- m))$ 。

后文中，如果没有特别说明，模数总是 正整数。

式中的 $b$ 是 $a$ 对模 $m$ 的剩余，这个概念与余数完全一致。通过限定 $b$ 的范围，相应的有 $a$ 对模 $m$ 的最小非负剩余、绝对最小剩余、最小正剩余。

同余的性质：

同余是等价关系，即同余具有
- 自反性： $a \equiv a (\mod m)$ 。
- 对称性：若 $a \equiv b (\mod m)$ ，则 $b \equiv a (\mod m)$ 。
- 传递性：若 $a \equiv b (\mod m), b \equiv c (\mod m)$ ，则 $a \equiv c (\mod m)$ 。
线性运算：若 $a, b, c, d \in Z, m \in N^{*}, a \equiv b (\mod m), c \equiv d (\mod m)$ $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：
- $a \pm c \equiv b \pm d (\mod m)$ 。
- $a \times c \equiv b \times d (\mod m)$ 。
设 $f (x) = \sum_{i = 0}^{n} a_{i} x^{i}$ 和 $g (x) = \sum_{i = 0}^{n} b_{i} x^{i}$ 是两个整系数多项式， $m \in N^{*}$ ，且 $a_{i} \equiv b_{i} (\mod m), 0 \leq i \leq n$ ，则对任意整数 $x$ 均有 $f (x) \equiv g (x) (\mod m)$ 。进而若 $s \equiv t (\mod m)$ ，则 $f (s) \equiv g (t) (\mod m)$ 。
若 $a, b \in Z, k, m \in N^{*}, a \equiv b (\mod m)$ , 则 $a k \equiv b k (\mod m k)$ 。
若 $a, b \in Z, d, m \in N^{*}, d ∣ a, d ∣ b, d ∣ m$ ，则当 $a \equiv b (\mod m)$ 成立时，有 $\frac{a}{d} \equiv \frac{b}{d} (mod \frac{m}{d})$ 。
若 $a, b \in Z, d, m \in N^{*}, d ∣ m$ ，则当 $a \equiv b (\mod m)$ 成立时，有 $a \equiv b (\mod d)$ 。
若 $a, b \in Z, d, m \in N^{*}$ ，则当 $a \equiv b (\mod m)$ 成立时，有 $(a, m) = (b, m)$ 。若 $d$ 能整除 $m$ 及 $a, b$ 中的一个，则 $d$ 必定能整除 $a, b$ 中的另一个。

还有性质是乘法逆元。见乘法逆元。

同余类与剩余系

为方便讨论，对集合 $A, B$ 和元素 $r$ ，我们引入如下记号：

$r + A := {r + a : a \in A}$ ；
$r A := {r a : a \in A}$ ；
$A + B := {a + b : a \in A, b \in B}$ ；
$A B := {a b : a \in A, b \in B}$ 。

同余类

对非零整数 $m$ ，把全体整数分成 $| m |$ 个两两不交的集合，且同一个集合中的任意两个数模 $m$ 均同余，我们把这 $| m |$ 个集合均称为模 $m$ 的 同余类 或 剩余类。用 $r mod m$ 表示含有整数 $r$ 的模 $m$ 的同余类。

不难证明对任意非零整数 $m$ ，上述划分方案一定存在且唯一。

由同余类的定义可知：

$r mod m = {r + k m : k \in Z}$ ；
$r mod m = s mod m ⟺ r \equiv s (\mod m)$ ；
对任意 $r, s \in Z$ ，要么 $r mod m = s mod m$ ，要么 $(r mod m) \cap (s mod m) = \emptyset$ ；
若 $m_{1} ∣ m$ ，则对任意整数 $r$ 均有 $r + m Z \subseteq r + m_{1} Z$ 。

注意到同余是等价关系，所以同余类即为同余关系的等价类。

我们把模 $m$ 的同余类全体构成的集合记为 $Z_{m}$ ，即

Z_{m} := {r mod m : 0 \leq r < m}

不难发现：

对任意整数 $a$ ， $a + Z_{m} = Z_{m}$ ；
对任意与 $m$ 互质的整数 $b$ ， $b Z_{m} = Z_{m}$ 。

由商群的定义可知 $Z_{m} = Z / m Z$ ，所以有时我们也会用 $Z / m Z$ 表示 $Z_{m}$ 。

由抽屉原理可知：

任取 $m + 1$ 个整数，必有两个整数模 $m$ 同余。
存在 $m$ 个两两模 $m$ 不同余的整数。

由此我们给出完全剩余系的定义：

（完全）剩余系

对 $m$ 个整数 $a_{1}, a_{2}, \dots, a_{m}$ ，若对任意的数 $x$ ，有且仅有一个数 $a_{i}$ 使得 $x$ 与 $a_{i}$ 模 $m$ 同余，则称这 $m$ 个整数 $a_{1}, a_{2}, \dots, a_{m}$ 为模 $m$ 的 完全剩余系，简称 剩余系。

我们还可以定义模 $m$ 的：

最小非负（完全）剩余系： $0, \dots, m - 1$ ；
最小正（完全）剩余系： $1, \dots, m$ ；
绝对最小（完全）剩余系： $- ⌊ m / 2 ⌋, \dots, - ⌊ - m / 2 ⌋ - 1$ ；
最大非正（完全）剩余系： $- m + 1, \dots, 0$ ；
最大负（完全）剩余系： $- m, \dots, - 1$ 。

若无特殊说明，一般我们只用最小非负剩余系。

我们注意到如下命题成立：

在模 $m$ 的任意一个同余类中，任取两个整数 $a_{1}, a_{2}$ 均有 $(a_{1}, m) = (a_{2}, m)$ 。

考虑同余类 $r mod m$ ，若 $(r, m) = 1$ ，则该同余类的所有元素均与 $m$ 互质，这说明我们也许可以通过类似方式得知所有与 $m$ 互质的整数构成的集合的结构。

既约同余类

对同余类 $r mod m$ ，若 $(r, m) = 1$ ，则称该同余类为 既约同余类 或 既约剩余类。

我们把模 $m$ 既约剩余类的个数记作 $φ (m)$ ，称其为 Euler 函数。

我们把模 $m$ 的既约同余类全体构成的集合记为 $Z_{m}^{*}$ ，即

Z_{m}^{*} := {r mod m : 0 \leq r < m, (r, m) = 1}

Warning

对于任意的整数 $a$ 和与 $m$ 互质的整数 $b$ ， $b Z_{m}^{*} = Z_{m}^{*}$ ，但是 $a + Z_{m}^{*}$ 不一定为 $Z_{m}^{*}$ 。这一点与 $Z_{m}$ 不同。

由抽屉原理可知：

任取 $φ (m) + 1$ 个与 $m$ 互质的整数，必有两个整数模 $m$ 同余。
存在 $φ (m)$ 个与 $m$ 互质且两两模 $m$ 不同余的整数。

由此我们给出既约剩余系的定义：

既约剩余系

对 $t = φ (m)$ 个整数 $a_{1}, a_{2}, \dots, a_{t}$ ，若 $(a_{i}, m) = 1, \forall 1 \leq i \leq t$ ，且对任意满足 $(x, m) = 1$ 的数 $x$ ，有且仅有一个数 $a_{i}$ 使得 $x$ 与 $a_{i}$ 模 $m$ 同余，则称这 $t$ 个整数 $a_{1}, a_{2}, \dots, a_{t}$ 为模 $m$ 的 既约剩余系、缩剩余系 或 简化剩余系。

类似地，我们也可以定义最小非负既约剩余系等概念。

若无特殊说明，一般我们只用最小非负既约剩余系。

剩余系的复合

对正整数 $m$ ，我们有如下定理：

若 $m = m_{1} m_{2}, 1 \leq m_{1}, m_{2}$ ，令 $Z_{m_{1}}, Z_{m_{2}}$ 分别为模 $m_{1}, m_{2}$ 的完全剩余系，则对任意与 $m_{1}$ 互质的 $a$ 均有：
$Z_{m} = a Z_{m_{1}} + m_{1} Z_{m_{2}} .$
为模 $m$ 的完全剩余系。进而，若 $m = \prod_{i = 1}^{k} m_{i}, 1 \leq m_{1}, m_{2}, \dots, m_{k}$ ，令 $Z_{m_{1}}, \dots, Z_{m_{k}}$ 分别为模 $m_{1}, \dots, m_{k}$ 的完全剩余系，则：
$Z_{m} = \sum_{i = 1}^{k} (\prod_{j = 1}^{i - 1} m_{j}) Z_{m_{i}} .$
为模 $m$ 的完全剩余系。

证明

只需证明对任意满足 $a x + m_{1} y \equiv a x^{'} + m_{1} y^{'} (\mod m_{1} m_{2})$ 的 $x, x^{'} \in Z_{m_{1}}$ ， $y, y^{'} \in Z_{m_{2}}$ ，都有：

a x + m_{1} y = a x^{'} + m_{1} y^{'} .

实际上，由 $m_{1} ∣ m_{1} m_{2}$ ，我们有 $a x + m_{1} y \equiv a x^{'} + m_{1} y^{'} (\mod m_{1})$ ，进而 $a x \equiv a x^{'} (\mod m_{1})$ ，由 $(a, m_{1}) = 1$ 可知 $x \equiv x^{'} (\mod m_{1})$ ，进而有 $x = x^{'}$ 。

进一步， $m_{1} y \equiv m_{1} y^{'} (\mod m_{1} m_{2})$ ，则 $y \equiv y^{'} (\mod m_{2})$ ，即 $y = y^{'}$ 。

因此，

a x + m_{1} y = a x^{'} + m_{1} y^{'} .

若 $m = m_{1} m_{2}, 1 \leq m_{1}, m_{2}, (m_{1}, m_{2}) = 1$ ，令 $Z_{m_{1}}^{*}, Z_{m_{2}}^{*}$ 分别为模 $m_{1}, m_{2}$ 的既约剩余系，则：
$Z_{m}^{*} = m_{2} Z_{m_{1}}^{*} + m_{1} Z_{m_{2}}^{*} .$
为模 $m$ 的既约剩余系。

Tip

该定理等价于证明 Euler 函数为积性函数。

证明

令 $Z_{m_{1}}, Z_{m_{2}}$ 分别为模 $m_{1}, m_{2}$ 的完全剩余系，我们已经证明了

Z_{m} = m_{2} Z_{m_{1}} + m_{1} Z_{m_{2}}

为模 $m$ 的完全剩余系。令 $M = {a \in Z_{m} : (a, m) = 1} \subseteq Z_{m}$ ，显然 $M$ 为模 $m$ 的既约剩余系，所以我们只需证明 $M = Z_{m}^{*}$ 即可。

显然 $Z_{m}^{*} \subseteq Z_{m}$ 。

任取 $m_{2} x + m_{1} y \in M$ ，其中 $x \in Z_{m_{1}}$ 且 $y \in Z_{m_{2}}$ ，有 $(m_{2} x + m_{1} y, m_{1} m_{2}) = 1$ ，由 $(m_{1}, m_{2}) = 1$ 可得

1 = (m_{2} x + m_{1} y, m_{1}) = (m_{2} x, m_{1}) = (x, m_{1}),

1 = (m_{2} x + m_{1} y, m_{2}) = (m_{1} y, m_{2}) = (y, m_{2}) .

因此可得 $x \in Z_{m_{1}}^{*}$ 且 $y \in Z_{m_{2}}^{*}$ ，即 $M \subseteq Z_{m}^{*}$ 。

任取 $m_{2} x + m_{1} y \in Z_{m}^{*}$ ，其中 $x \in Z_{m_{1}}^{*}$ 且 $y \in Z_{m_{2}}^{*}$ ，有 $(x, m_{1}) = 1$ 且 $(y, m_{2}) = 1$ ，由 $(m_{1}, m_{2}) = 1$ 可得

(m_{2} x + m_{1} y, m_{1}) = (m_{2} x, m_{1}) = (x, m_{1}) = 1,

(m_{2} x + m_{1} y, m_{2}) = (m_{1} y, m_{2}) = (x, m_{2}) = 1,

因此可得 $(m_{2} x + m_{1} y, m_{1} m_{2}) = 1$ ，即 $Z_{m}^{*} \subseteq M$ 。

综上所述，

Z_{m}^{*} = m_{2} Z_{m_{1}}^{*} + m_{1} Z_{m_{2}}^{*} .

为模 $m$ 的既约剩余系。

数论函数

数论函数（也称算术函数）指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

定义

在数论中，若函数 $f (n)$ 满足 $f (1) = 1$ ，且 $f (x y) = f (x) f (y)$ 对任意互质的 $x, y \in N^{*}$ 都成立，则 $f (n)$ 为 积性函数。

在数论中，若函数 $f (n)$ 满足 $f (1) = 1$ 且 $f (x y) = f (x) f (y)$ 对任意的 $x, y \in N^{*}$ 都成立，则 $f (n)$ 为 完全积性函数。

性质

若 $f (x)$ 和 $g (x)$ 均为积性函数，则以下函数也为积性函数：

\begin{aligned} h (x) & = f (x^{p}) \\ h (x) & = f^{p} (x) \\ h (x) & = f (x) g (x) \\ h (x) & = \sum_{d ∣ x} f (d) g (\frac{x}{d}) \end{aligned}

对正整数 $x$ ，设其唯一质因数分解为 $x = \prod p_{i}^{k_{i}}$ ，其中 $p_{i}$ 为质数。

若 $F (x)$ 为积性函数，则有 $F (x) = \prod F (p_{i}^{k_{i}})$ 。

若 $F (x)$ 为完全积性函数，则有 $F (x) = \prod F (p_{i}^{k_{i}}) = \prod F (p_{i})^{k_{i}}$ 。

例子

单位函数： $ε (n) = [n = 1]$ 。（完全积性）
恒等函数： ${id}_{k} (n) = n^{k}$ ， ${id}_{1} (n)$ 通常简记作 $id (n)$ 。（完全积性）
常数函数： $1 (n) = 1$ 。（完全积性）
除数函数： $σ_{k} (n) = \sum_{d ∣ n} d^{k}$ 。 $σ_{0} (n)$ 通常简记作 $d (n)$ 或 $τ (n)$ ， $σ_{1} (n)$ 通常简记作 $σ (n)$ 。
欧拉函数： $φ (n) = \sum_{i = 1}^{n} [(i, n) = 1]$ 。
莫比乌斯函数： $μ (n) = {\begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d^{2} ∣ n \\ (- 1)^{ω (n)} & otherwise \end{cases}$ ，其中 $ω (n)$ 表示 $n$ 的本质不同质因子个数。

加性函数

定义

在数论中，若函数 $f (n)$ 满足 $f (1) = 0$ 且 $f (x y) = f (x) + f (y)$ 对任意互质的 $x, y \in N^{*}$ 都成立，则 $f (n)$ 为 加性函数。

在数论中，若函数 $f (n)$ 满足 $f (1) = 0$ 且 $f (x y) = f (x) + f (y)$ 对任意的 $x, y \in N^{*}$ 都成立，则 $f (n)$ 为 完全加性函数。

加性函数

本节中的加性函数指数论上的加性函数 (Additive function)，应与代数中的 Additive map 做区分。

性质

对正整数 $x$ ，设其唯一质因数分解为 $x = \prod p_{i}^{k_{i}}$ ，其中 $p_{i}$ 为质数。

若 $F (x)$ 为加性函数，则有 $F (x) = \sum F (p_{i}^{k_{i}})$ 。

若 $F (x)$ 为完全加性函数，则有 $F (x) = \sum F (p_{i}^{k_{i}}) = \sum F (p_{i}) \cdot k_{i}$ 。

例子

为方便叙述，令所有质数组成的集合为 $P$ .

素因数分解中 $p$ 的重数： $ν_{p} (n) = max {k \in N : p^{k} ∣ n}$ ，其中， $p \in P$ 。（完全加性）
所有质因子数目： $Ω (n) = \sum_{p \in P} ν_{p} (n)$ 。（完全加性）
相异质因子数目： $ω (n) = \sum_{p \in P} [p ∣ n]$ 。
所有质因子之和： $a_{0} (n) = \sum_{p \in P} ν_{p} (n) \cdot p$ 。（完全加性）
相异质因子之和： $a_{1} (n) = \sum_{p \in P} [p ∣ n] \cdot p$ 。

取整函数

对于实数 $x$ ，定义 下取整函数（floor function）和 上取整函数（ceiling function）分别为

⌊ x ⌋ = max {k \in Z : k \leq x}, ⌈ x ⌉ = min {k \in Z : k \geq x} .

利用下取整函数，一个实数可以分解为整数部分和小数部分： $x = ⌊ x ⌋ + {x}$ 。其中， ${x}$ 表示 $x$ 的小数部分。

取整函数有如下基本性质：（ $x \in R, n \in Z$ ）

$x \in Z ⟺ x = ⌊ x ⌋ = ⌈ x ⌉$ 。
$⌈ x ⌉ - ⌊ x ⌋ = [x \notin Z]$ 。
$x - 1 < ⌊ x ⌋ \leq x \leq ⌈ x ⌉ < x + 1$ 。
$⌊ - x ⌋ = - ⌈ x ⌉, ⌈ - x ⌉ = - ⌊ x ⌋$ 。
$⌊ x + n ⌋ = ⌊ x ⌋ + n, ⌈ x + n ⌉ = ⌈ x ⌉ + n$ 。
$⌊ x ⌋$ 和 $⌈ x ⌉$ 都是关于 $x$ 的单调弱增函数。

证明关于下（上）取整函数的等式经常用到如下等价形式：（ $x \in R, n \in Z$ ）

$⌊ x ⌋ = n ⟺ n \leq x < n + 1 ⟺ x - 1 < n \leq x$ 。
$⌈ x ⌉ = n ⟺ n - 1 < x \leq n ⟺ x \leq n < x + 1$ 。

证明关于下（上）取整函数的不等式经常用到如下等价形式：（ $x \in R, n \in Z$ ）

$x < n ⟺ ⌊ x ⌋ < n$ 。
$n < x ⟺ n < ⌈ x ⌉$ 。
$x \leq n ⟺ ⌈ x ⌉ \leq n$ 。
$n \leq x ⟺ n \leq ⌊ x ⌋$ 。

涉及和、差的性质如下：（ $x, y \in R$ ）

$⌊ x ⌋ + ⌊ y ⌋ \leq ⌊ x + y ⌋ \leq ⌊ x ⌋ + ⌊ y ⌋ + 1$ ，且恰有一个等号成立。
$⌈ x ⌉ + ⌈ y ⌉ - 1 \leq ⌈ x + y ⌉ \leq ⌈ x ⌉ + ⌈ y ⌉$ ，且恰有一个等号成立。
$⌊ | x - y | ⌋ \leq | ⌊ x ⌋ - ⌊ y ⌋ | \leq ⌈ | x - y | ⌉$ 。
$⌊ | x - y | ⌋ \leq | ⌈ x ⌉ - ⌈ y ⌉ | \leq ⌈ | x - y | ⌉$ 。

涉及商的性质如下：（ $x \in R, n \in Z, m \in Z_{+}$ ）

$⌈ \frac{n}{m} ⌉ = ⌊ \frac{n + m - 1}{m} ⌋, ⌊ \frac{n}{m} ⌋ = ⌈ \frac{n - m + 1}{m} ⌉$ 。
$⌊ \frac{x + n}{m} ⌋ = ⌊ \frac{⌊ x ⌋ + n}{m} ⌋, ⌈ \frac{x + n}{m} ⌉ = ⌈ \frac{⌈ x ⌉ + n}{m} ⌉$ 。
$⌊ \frac{⌊ x / n ⌋}{m} ⌋ = ⌊ \frac{x}{n m} ⌋, ⌈ \frac{⌈ x / n ⌉}{m} ⌉ = ⌈ \frac{x}{n m} ⌉$ 。
对于 $x > 0$ ，有 $⌊ \frac{x}{m} ⌋ = \sum_{k = 1}^{⌊ x ⌋} [m ∣ k]$ 。

其中，第二条和第三条性质都可以看作是如下结论的直接推论：

设 $f$ 为连续单增函数，且只要 $f (x) \in Z$ ，就有 $x \in Z$ ，那么
$⌊ f (x) ⌋ = ⌊ f (⌊ x ⌋) ⌋, ⌈ f (x) ⌉ = ⌈ f (⌈ x ⌉) ⌉ .$
证明

由对称性，只需要证明第一个等式。如果 $x$ 是整数，那么命题显然。否则， $⌊ x ⌋ < x$ 。由 $f$ 和下取整函数的单调性可知， $⌊ f (x) ⌋ \geq ⌊ f (⌊ x ⌋) ⌋$ 。如果等号不成立，那么设 $y = ⌊ f (x) ⌋$ ，它满足 $⌊ f (⌊ x ⌋) ⌋ < y \leq ⌊ f (x) ⌋$ ，这等价于 $f (⌊ x ⌋) < y \leq f (x)$ 。由 $f$ 的连续性可知，存在 $⌊ x ⌋ < x_{0} \leq x$ 使得 $f (x_{0}) = y$ 。因为 $y \in Z$ ，所以 $x_{0} \in Z$ ，这与 $⌊ x ⌋$ 的定义矛盾。故而，等号成立，即 $⌊ f (x) ⌋ = ⌊ f (⌊ x ⌋) ⌋$ 。

最后是一组关于带有取整函数的求和式的结论：（ $x \in R, n \in Z, m \in Z_{+}$ ）

$n = ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{2} ⌉$ 。
$n = ⌊ \frac{n}{m} ⌋ + ⌊ \frac{n + 1}{m} ⌋ + \dots + ⌊ \frac{n + m - 1}{m} ⌋$ 。
$n = ⌈ \frac{n}{m} ⌉ + ⌈ \frac{n - 1}{m} ⌉ + \dots + ⌈ \frac{n - m + 1}{m} ⌉$ 。
$⌊ m x ⌋ = ⌊ x ⌋ + ⌊ x + \frac{1}{m} ⌋ + \dots + ⌊ x + \frac{m - 1}{m} ⌋$ 。
$⌈ m x ⌉ = ⌈ x ⌉ + ⌈ x - \frac{1}{m} ⌉ + \dots + ⌈ x - \frac{m - 1}{m} ⌉$ 。
当 $m ⟂ n$ 时， $\sum_{k = 1}^{m - 1} ⌊ \frac{k n}{m} ⌋ = \frac{1}{2} (n - 1) (m - 1)$ 。
当 $m ⟂ n$ 时， $\sum_{k = 1}^{m - 1} ⌈ \frac{k n}{m} ⌉ = \frac{1}{2} (n + 1) (m - 1)$ 。

这些乃至更一般的类似形式求和式的推导可以参考类欧几里得算法页面。

取整函数的更多性质以及应用可以参考如下页面：

取模运算： $n mod m = n - ⌊ \frac{n}{m} ⌋ m$ 。它可以用于优化整数取模运算。
利用 Gauss 引理证明二次互反律。
数论分块，尤其是它的性质证明部分。
计算阶乘中素数因子幂次的 Legendre 公式。
Beatty 数列、Rayleigh 定理以及 Wythoff 博弈。

参考资料与注释

潘承洞，潘承彪。初等数论。北京大学出版社。
Floor and ceiling functions - Wikipedia
Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. "Concrete mathematics: a foundation for computer science." (1989).

本页面最近更新：2025/10/31 16:20:06，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：c-forrest, Tiphereth-A, Enter-tainer, Great-designer, HeRaNO, ksyx, 383494, buuzzing, cr4c1an, Emp7iness, jifbt, Kaiser-Yang, Koishilll, Marcythm, Qiu-Quanzhi, Saisyc, sshwy, StarryReverie, StudyingFather, Xeonacid, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用