docs/math/number-theory/basic.md
本文对于数论的开头部分做一个简介．
???+ note "定义" 设 $a,b\in\mathbf{Z}$，$a\ne 0$．如果 $\exists q\in\mathbf{Z}$，使得 $b=aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$；$b$ 不被 $a$ 整除记作 $a\nmid b$．
整除的性质：
???+ note "定义" 若 $a\mid b$，则称 $b$ 是 $a$ 的 倍数，$a$ 是 $b$ 的 约数．
$0$ 是所有非 $0$ 整数的倍数．对于整数 $b\ne0$，$b$ 的约数只有有限个．
平凡约数（平凡因数）：对于整数 $b\ne0$，$\pm1$、$\pm b$ 是 $b$ 的平凡约数．当 $b=\pm1$ 时，$b$ 只有两个平凡约数．
对于整数 $b\ne 0$，$b$ 的其他约数称为真约数（真因数、非平凡约数、非平凡因数）．
约数的性质：
在具体问题中，如果没有特别说明，约数总是指正约数．
???+ note "余数" 设 $a,b$ 为两个给定的整数，$a\ne0$．设 $d$ 是一个给定的整数．那么，一定存在唯一的一对整数 $q$ 和 $r$，满足 $b=qa+r,d\le r<|a|+d$．
无论整数 $d$ 取何值，$r$ 统称为余数．$a\mid b$ 等价于 $a\mid r$．
一般情况下，$d$ 取 $0$，此时等式 $b=qa+r,0\le r<|a|$ 称为带余数除法（带余除法）．这里的余数 $r$ 称为最小非负余数．
余数往往还有两种常见取法：
带余数除法的余数只有最小非负余数．如果没有特别说明，余数总是指最小非负余数．
余数的性质：
关于公约数、公倍数、最大公约数与最小公倍数，四个名词的定义，见 最大公约数．
???+ warning "Warning" 一些作者认为 $0$ 和 $0$ 的最大公约数无定义，其余作者一般将其视为 $0$．C++ STL 的实现中采用后者，即认为 $0$ 和 $0$ 的最大公约数为 $0$1．
最大公约数有如下性质：
最大公约数还有如下与互素相关的性质：
最小公倍数有如下性质：
最大公约数和最小公倍数可以组合出很多奇妙的等式，如：
这些性质均可通过定义或 唯一分解定理 证明，其中使用唯一分解定理的证明更容易理解．
???+ note "定义" 若 $(a_1,a_2)=1$，则称 $a_1$ 和 $a_2$ 互素（既约）．
若 $(a_1,\ldots,a_k)=1$，则称 $a_1,\ldots,a_k$ **互素**（**既约**）．
多个整数互素，不一定两两互素．例如 $6$、$10$ 和 $15$ 互素，但是任意两个都不互素．
互素的性质与最大公约数理论：裴蜀定理（Bézout's identity）．见 裴蜀定理．
辗转相除法是一种算法，也称 Euclid 算法．见 最大公约数．
关于素数的算法见 素数．
???+ note "定义" 设整数 $p\ne0,\pm1$．如果 $p$ 除了平凡约数外没有其他约数，那么称 $p$ 为 素数（不可约数）．
若整数 $a\ne0,\pm 1$ 且 $a$ 不是素数，则称 $a$ 为 **合数**．
$p$ 和 $-p$ 总是同为素数或者同为合数．如果没有特别说明，素数总是指正的素数．
整数的因数是素数，则该素数称为该整数的素因数（素约数）．
素数与合数的简单性质：
???+ note "算术基本引理" 设 $p$ 是素数，$p\mid a_1a_2$，那么 $p\mid a_1$ 和 $p\mid a_2$ 至少有一个成立．
算术基本引理的逆命题稍加修改也可以得到素数的另一种定义．
???+ note "素数的另一种定义" 对整数 $p\ne 0,\pm 1$，若对任意满足 $p\mid a_1a_2$ 的整数 $a_1,a_2$ 均有 $p\mid a_1$ 或 $p\mid a_2$ 成立，则称 $p$ 是素数．
??? tip "Tip" 这个定义的动机可以从 素理想 中找到．
???+ note "算术基本定理（唯一分解定理）" 设正整数 $a$，那么必有表示：
$$
a=p_1p_2\cdots p_s
$$
其中 $p_j(1\le j\le s)$ 是素数．并且在不计次序的意义下，该表示唯一．
???+ note "标准素因数分解式" 将上述表示中，相同的素数合并，可得：
$$
a={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s},p_1<p_2<\cdots<p_s
$$
称为正整数 $a$ 的标准素因数分解式．
算术基本定理和算术基本引理，两个定理是等价的．
???+ note "定义" 设整数 $m\ne0$．若 $m\mid(a-b)$，称 $m$ 为 模数（模），$a$ 同余于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的 剩余．记作 $a\equiv b\pmod m$．
否则，$a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余．记作 $a\not\equiv b\pmod m$．
这样的等式，称为模 $m$ 的同余式，简称 **同余式**．
根据整除的性质，上述同余式也等价于 $a\equiv b\pmod{(-m)}$．
后文中，如果没有特别说明，模数总是 正整数．
式中的 $b$ 是 $a$ 对模 $m$ 的剩余，这个概念与余数完全一致．通过限定 $b$ 的范围，相应的有 $a$ 对模 $m$ 的最小非负剩余、绝对最小剩余、最小正剩余．
同余的性质：
还有性质是乘法逆元．见 乘法逆元．
为方便讨论，对集合 $A,B$ 和元素 $r$，我们引入如下记号：
???+ note "同余类" 对非零整数 $m$，把全体整数分成 $|m|$ 个两两不交的集合，且同一个集合中的任意两个数模 $m$ 均同余，我们把这 $|m|$ 个集合均称为模 $m$ 的 同余类 或 剩余类．用 $r\bmod m$ 表示含有整数 $r$ 的模 $m$ 的同余类．
不难证明对任意非零整数 $m$，上述划分方案一定存在且唯一．
由同余类的定义可知：
注意到同余是等价关系，所以同余类即为同余关系的等价类．
我们把模 $m$ 的同余类全体构成的集合记为 $\mathbf{Z}_m$，即
$$ \mathbf{Z}_m:={r\bmod m:0\leq r<m} $$
不难发现：
由 商群 的定义可知 $\mathbf{Z}_m=\mathbf{Z}/m\mathbf{Z}$，所以有时我们也会用 $\mathbf{Z}/m\mathbf{Z}$ 表示 $\mathbf{Z}_m$．
由 抽屉原理 可知：
由此我们给出完全剩余系的定义：
???+ note "（完全）剩余系" 对 $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$ 的：
若无特殊说明，一般我们只用最小非负剩余系．
我们注意到如下命题成立：
考虑同余类 $r\bmod m$，若 $(r,m)=1$，则该同余类的所有元素均与 $m$ 互质，这说明我们也许可以通过类似方式得知所有与 $m$ 互质的整数构成的集合的结构．
???+ note "既约同余类" 对同余类 $r\bmod m$，若 $(r,m)=1$，则称该同余类为 既约同余类 或 既约剩余类．
我们把模 $m$ 既约剩余类的个数记作 $\varphi(m)$，称其为 [Euler 函数](./euler-totient.md)．
我们把模 $m$ 的既约同余类全体构成的集合记为 $\mathbf{Z}_m^*$，即
$$ \mathbf{Z}_m^*:={r\bmod m:0\leq r<m,(r,m)=1} $$
???+ warning "Warning" 对于任意的整数 $a$ 和与 $m$ 互质的整数 $b$，$b\mathbf{Z}_m^=\mathbf{Z}_m^$，但是 $a+\mathbf{Z}_m^$ 不一定为 $\mathbf{Z}_m^$．这一点与 $\mathbf{Z}_m$ 不同．
由 抽屉原理 可知：
由此我们给出既约剩余系的定义：
???+ note "既约剩余系" 对 $t=\varphi(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_1m_2,~1\leq m_1,m_2$，令 $Z_{m_1},Z_{m_2}$ 分别为模 $m_1,m_2$ 的 完全 剩余系，则对任意与 $m_1$ 互质的 $a$ 均有：
$$ Z_m=aZ_{m_1}+m_1Z_{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\left(\prod_{j=1}^{i-1}m_j\right)Z_{m_i}. $$
为模 $m$ 的 完全 剩余系．
???+ note "证明" 只需证明对任意满足 $ax+m_1y\equiv ax'+m_1y'\pmod{m_1m_2}$ 的 $x,x'\in Z_{m_1}$，$y,y'\in Z_{m_2}$，都有：
$$
ax+m_1y=ax'+m_1y'.
$$
实际上，由 $m_1\mid m_1m_2$，我们有 $ax+m_1y\equiv ax'+m_1y'\pmod{m_1}$，进而 $ax\equiv ax'\pmod{m_1}$，由 $(a,m_1)=1$ 可知 $x\equiv x'\pmod{m_1}$，进而有 $x=x'$．
进一步，$m_1y\equiv m_1y'\pmod{m_1m_2}$，则 $y\equiv y'\pmod{m_2}$，即 $y=y'$．
因此，
$$
ax+m_1y=ax'+m_1y'.
$$
若 $m=m_1m_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_2Z_{m_1}^+m_1Z_{m_2}^*. $$
为模 $m$ 的 既约 剩余系．
???+ tip "Tip" 该定理等价于证明 Euler 函数为 积性函数．
???+ note "证明" 令 $Z_{m_1},Z_{m_2}$ 分别为模 $m_1,m_2$ 的完全剩余系，我们已经证明了
$$
Z_m=m_2Z_{m_1}+m_1Z_{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_2x+m_1y\in M$，其中 $x\in Z_{m_1}$ 且 $y\in Z_{m_2}$，有 $(m_2x+m_1y,m_1m_2)=1$，由 $(m_1,m_2)=1$ 可得
$$
1=(m_2x+m_1y,m_1)=(m_2x,m_1)=(x,m_1),
$$
$$
1=(m_2x+m_1y,m_2)=(m_1y,m_2)=(y,m_2).
$$
因此可得 $x\in Z_{m_1}^*$ 且 $y\in Z_{m_2}^*$，即 $M\subseteq Z_m^*$．
任取 $m_2x+m_1y\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_2x+m_1y,m_1)=(m_2x,m_1)=(x,m_1)=1,
$$
$$
(m_2x+m_1y,m_2)=(m_1y,m_2)=(x,m_2)=1,
$$
因此可得 $(m_2x+m_1y,m_1m_2)=1$，即 $Z_m^*\subseteq M$．
综上所述，
$$
Z_m^*=m_2Z_{m_1}^*+m_1Z_{m_2}^*.
$$
为模 $m$ 的 **既约** 剩余系．
数论函数（也称算术函数）指定义域为正整数的函数．数论函数也可以视作一个数列．
???+ note "定义" 在数论中，若函数 $f(n)$ 满足 $f(1)=1$，且 $f(xy)=f(x)f(y)$ 对任意互质的 $x, y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 积性函数．
在数论中，若函数 $f(n)$ 满足 $f(1)=1$ 且 $f(xy)=f(x)f(y)$ 对任意的 $x, y \in\mathbf{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\mid x}f(d)g\left(\dfrac{x}{d}\right) \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}$．
???+ note "定义" 在数论中，若函数 $f(n)$ 满足 $f(1)=0$ 且 $f(xy)=f(x)+f(y)$ 对任意互质的 $x, y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 加性函数．
在数论中，若函数 $f(n)$ 满足 $f(1)=0$ 且 $f(xy)=f(x)+f(y)$ 对任意的 $x, y \in\mathbf{N}^*$ 都成立，则 $f(n)$ 为 **完全加性函数**．
???+ warning "加性函数" 本节中的加性函数指数论上的加性函数 (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$．
为方便叙述，令所有质数组成的集合为 $\mathbf P$.
对于实数 $x$，定义 下取整函数（floor function）和 上取整函数（ceiling function）分别为
$$ \lfloor x\rfloor = \max{k\in\mathbf Z:k\le x},~\lceil x\rceil = \min{k\in\mathbf Z:k\ge x}. $$
利用下取整函数，一个实数可以分解为整数部分和小数部分：$x = \lfloor x\rfloor + {x}$．其中，${x}$ 表示 $x$ 的小数部分．
取整函数有如下基本性质：（$x\in\mathbf R,~n\in\mathbf Z$）
证明关于下（上）取整函数的等式经常用到如下等价形式：（$x\in\mathbf R,~n\in\mathbf Z$）
证明关于下（上）取整函数的不等式经常用到如下等价形式：（$x\in\mathbf R,~n\in\mathbf Z$）
涉及和、差的性质如下：（$x,y\in\mathbf R$）
涉及商的性质如下：（$x\in\mathbf R,~n\in\mathbf Z,~m\in\mathbf Z_+$）
其中，第二条和第三条性质都可以看作是如下结论的直接推论：
设 $f$ 为连续单增函数，且只要 $f(x)\in\mathbf Z$，就有 $x\in\mathbf Z$，那么
$$ \lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor,~ \lceil f(x)\rceil = \lceil f(\lceil x\rceil)\rceil. $$
??? note "证明" 由对称性，只需要证明第一个等式．如果 $x$ 是整数，那么命题显然．否则，$\lfloor x\rfloor < x$．由 $f$ 和下取整函数的单调性可知，$\lfloor f(x)\rfloor \ge \lfloor f(\lfloor x\rfloor)\rfloor$．如果等号不成立，那么设 $y = \lfloor f(x)\rfloor$，它满足 $\lfloor f(\lfloor x\rfloor)\rfloor < y \le \lfloor f(x)\rfloor$，这等价于 $f(\lfloor x\rfloor) < y \le f(x)$．由 $f$ 的连续性可知，存在 $\lfloor x\rfloor < x_0 \le x$ 使得 $f(x_0)=y$．因为 $y\in\mathbf Z$，所以 $x_0\in\mathbf Z$，这与 $\lfloor x\rfloor$ 的定义矛盾．故而，等号成立，即 $\lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor$．
最后是一组关于带有取整函数的求和式的结论：（$x\in\mathbf R,~n\in\mathbf Z,~m\in\mathbf Z_+$）
这些乃至更一般的类似形式求和式的推导可以参考 类欧几里得算法 页面．
取整函数的更多性质以及应用可以参考如下页面：