整数

关于整数的严格定义，参见 皮亚诺公理体系

良序性质：每个非空的正整数集合都有一个最小元

定义：如果存在整数 $p$ 和 $q \neq 0$，使得 $r = p/q$，则称实数 $r$ 是 有理数，如果 $r$ 不是有理数，则称 $r$ 为 无理数；

定理 1.1：$\sqrt{2}$ 是无理数；

证法一：用反证法

假设 $\sqrt{2}$ 是有理数，那么存在互素的正整数 $a, b$ 使得 $\displaystyle {a \over b} = \sqrt{2}$；

因此 $a^2 = 2 b^2$；所以 $a^2$ 是偶数，于是 $a$ 是偶数，所以 $a$ 可以表示成 $a = 2k, k \in \mathbb{N^+}$；

因此 $(2k)^2 = 2b^2$，有 $2k^2 = b^2$，于是 $b^2$ 是偶数，于是 $b$ 也是偶数；

因 $a,b$ 都是偶数，于是 $a, b$ 有公因子 $2$，这与 $a, b$ 互素矛盾；

于是，$\sqrt{2}$ 是无理数，证毕；

证法二：用反证法

假设 $\sqrt{2}$ 是有理数，那么存在正整数 $a, b$ 使得 $\displaystyle {a \over b} = \sqrt{2}$；

因此，$S = \{ k\sqrt{2} | k, k\sqrt{2} \in \mathbb{N^+}\} \neq \varnothing$，非空是因为 $a = b\sqrt{2}$ 是 $S$ 的一个元素，因此，由良序性质，$S$ 有最小元，记为 $s = t\sqrt{2}$；

记 $s_r = s\sqrt{2} - s = s\sqrt{2} - t\sqrt{2} = (s - t)\sqrt{2}$，由于 $s\sqrt{2} = 2t$ 和 $s$ 都是整数，于是 $s_r \in \mathbb{Z}$；

进一步，$s_r = s\sqrt{2} - s = s(\sqrt{2} - 1)$. 而 $0 < \sqrt{2} < 2$，于是 $0 < s_r < s$, 这与 $s$ 是 $S$ 中的最小元矛盾；

于是 $\sqrt{2}$ 是无理数，证毕；

显然，此方法亦可以用于证明 $\sqrt{3}$ 是无理数，而法一虽然简单，却不能了；

定义：若数 $\alpha$ 是整系数多项式的跟，则称 $\alpha$ 为 代数数；也就是说，如果存在整数 $a_0, \cdots, a_n$ 使得 $a_n\alpha^n + a_{n-1}\alpha^{n-1} + \cdots + a_0 = 0$，则 $\alpha$ 是代数数，否则，称之为 超越数；

定义：小于或等于 $x$ 的最大整数，记为 $[x]$，即 $[x]$ 是满足

$$[x] \leqslant x < [x] + 1$$

的整数；

定义：实数 $x$ 的分数部分，记为 $\{x\}$，是 $x$ 与 $[x]$ 的差，即 $\{x\} = x - [x]$

丢番图逼近

定理 1.2： 鸽笼原理（抽屉原理）

如果把 $k + 1$ 或更多的物体放入 $k$ 个盒子中，那么至少有一个盒子中有两个或更多的物体；

证明：反证法，如果 $k$ 个盒子中的任何一个中都没有多于一个物体，那么所有物体的总数至多为 $k$ 个，与原命题矛盾，故有一个盒子中至少有两个或以上的物体；

证毕

定理 1.3： 狄利克雷逼近定理(1834)

如果 $\alpha$ 是一个实数，$n$ 是一个正整数，则存在整数 $a, b, 1 \leqslant a \leqslant n$ 使得 $\displaystyle |a\alpha - b| < {1 \over n}$

证明：考虑 $n + 1$ 个数 $0, \{\alpha\},\{2\alpha\}, \cdots, \{n\alpha\}$，这 $n + 1$ 个数是 $j\alpha, j = 0, 1, \cdots, n$ 的分数部分，所以 $0 \leqslant \{j\alpha \} < 1, j = 0, 1 \cdots, n$，这 $n + 1$ 个数中的每一个都位于 $n$ 个互不相交的区间 $0 \leqslant x < {1 \over n}$, ${1 \over n} \leqslant x < {2 \over n}$, $\cdots$, ${j - 1 \over n} \leqslant x < {j \over n}$, $\cdots$, ${n - 1 \over n} \leqslant x < 1$ 中的一个；

由于我们考虑的是 $n + 1$ 个数，但是仅有 $n$ 个区间，由鸽笼原理可知，至少有两个数位于同一个区间中；

由于这些区间长度都等于 ${1 \over n}$，并且不包含右端点，所以，位于同一区间中的两个数的距离小于 ${1 \over n}$，从而存在整数 $j, k, 0 \leqslant j < k \leqslant n$，使得 $|\{k\alpha\} - \{j\alpha\}| < {1 \over n}$，现在设 $a = k - j, b = [k\alpha] - [j\alpha]$, 由于 $0 \leqslant j < k \leqslant n$，可见 $1 \leqslant \alpha \leqslant n$，而且：

这样我们就找到了想要的整数 $a,b, 1 \leqslant a \leqslant n$，使得 $|a\alpha - b| < {1 \over n}$

证毕；

序列

序列 $\{a_n \}$ 是一列数 $a_1, a_2, \cdots$，序列中的项可以用映射 $f(i) = a_i$，跟正整数集合建立起一一映射（双射，既是单射，又是满射）

等比数列定义：等比数列 是形式为 $a, ar, ar^2, \cdots$ 的序列，其中初始项 $a$ 和公比 $r$ 都是实数；

可数定义：一个集合 可数，如果它是有限的，或者是无穷的，但是与正整数集合之间存在一个双射，如果一个集合是不可数的，则称为 不可数；

定理 1.4：有理数集合是可数的

数学归纳法

定理 1.5： 数学归纳法原理

一个包含 $1$ 的正整数集合如果具有如下性质，即若包含整数 $k$，则其包含整数 $k + 1$，那么这个集合一定是所有正整数的集合；

证明：使用良序性质

设 $S$ 是包含 $1$ 的正整数集合，并且如果它包含整数 $n$, 则一定包含 $n + 1$；

假定（为了推出矛盾）$S$ 不是所有正整数的集合，因此存在 $k \in \mathbb{N^+}$ 使得 $k \notin S$，记所有 $k$ 的集合为 $T=\{k| k \notin S, k \in \mathbb{N^+}\} \neq \varnothing$，故由良序性质，$T$ 中存在一个最小元，记为 $t$. 注意由于 $1$ 在 $S$ 中，故 $t \neq 1$

现在，由于 $t > 1$, 故 $t - 1 \in \mathbb{N^+}$，由于 $t$ 是 $T$ 中的最小元，故 $t - 1 \in S$，从而一定包含 $(t - 1) + 1 = t \in S$, 这与假定 $t \notin S$ 矛盾；

故 $S$ 一定是所有正整数的集合；

注：数学归纳法为皮亚诺公理体系的第五公理，无需证明，我们认为是自明的；因为，整数的定义用到了数学归纳法，如果再使用整数来证明数学归纳法，就引起了循环论证，显然不对；

数学归纳法的起源：已知的数学归纳法的使用最早出现在 16 世纪的数学家 Francesco Maurolico(1494 - 1575) 的工作中，在他的著作 《Arithmeticorum Libri Duo》 中，Maurolico 给出了整数的各种性质以及证明，为了完成一些证明，他发明了数学归纳法。在他的书中，数学归纳法首次出现在证明前 $n$ 个正奇数的和是 $n^2$ 中；

定理 1.6：强归纳法原理 / 第二数学归纳法

包含 $1$ 的正整数集合，并且具有下述性质：对于每一个正整数 $n$，如果他包含全体正整数 $1,2,\cdots,n$，则它也包含正整数 $n + 1$，那么这个集合一定是所有正整数构成的集合；

证明：

设 $T$ 是一个包含 $1$ 的整数集合，并且满足对于任意正整数 $n$，如果它包含 $1, 2, \cdots, n$，则它也包含 $n + 1$；

设 $S$ 是所有使得小于等于 $n$ 的正整数都在 $T$ 中的正整数 $n$ 的集合，则 $1$ 在 $S$ 中；

并且，根据假设，我们看到如果 $n$ 在 $S$ 中，则 $n + 1$ 在 $S$ 中，因此，由数学归纳法原理，$S$ 必为所有正整数的集合，故显然 $T$ 也是所有正整数的集合，因为 $S$ 是 $T$ 的一个子集；

递归定义：我们说函数 $f$ 是 递归定义的，如果指定了 $f$ 在 $1$ 处的值，而且对于任意正整数 $n$，都提供了一个规则来根据 $f(n)$ 确定 $f(n + 1)$

斐波那契数

斐波那契序列定义：$f_1 = 1$，$f_2 = 1$，且对 $n \geqslant 3$，$f_n = f_{n - 1} + f_{n - 2}$，这个序列中的项被称为 斐波那契数；

斐波那契和：

$$S(n) = \sum_{i = 1}^n f_i = f_{n + 2} - 1$$

证明：用数学归纳法

• 当 $n = 1$ 时，$S(1) = 1 = 2 - 1 = f_3 - 1$，成立

• 设，当 $n = k$ 时， $\displaystyle S(k) = \sum_{i = 1}^k f_i = f_{k + 2} - 1$，成立

• 则，当 $n = k + 1$ 时：

证毕；

定理 1.7：设 $n$ 是 正整数，$\displaystyle \alpha = {1 + \sqrt{5} \over 2}$, $\displaystyle \beta = {1 - \sqrt{5} \over 2}$，则第 $n$ 个斐波那契数 $f_n$ 由下式给出：

整除性

一个整数可以被另一个整数整除的概念，在数论中处于中心地位。

整除的定义：如果 $a$ 和 $b$ 为整数且 $a\neq 0$，若存在整数 $c$ 使得 $b = ac$，则 $a$ 整除 $b$；若 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个 因子，则称 $b$ 是 $a$ 的 倍数；

如果 $a$ 整除 $b$，记为 $a\mid b$，如果 $a$ 不能整除 $b$，记为 $a \nmid b$；

定理 1.8：整除传递定理

如果 $a, b, c$ 是整数，且 $a \mid b$, $b \mid c$，则 $a \mid c$

证明 因为 $a \mid b$, $b \mid c$，存在整数 $e$ 和 $f$，使得 $ae = b$，$bf = c$，因此 $c = bf = (ae)f = a(ef)$，从而 $a \mid c$；

定理 1.9：如果 $a, b$，$m$ 和 $n$ 为整数，且 $c \mid a$，$c \mid b$，则 $c \mid (ma + nb)$

证明：因为 $a \mid b$, $b \mid c$，存在整数 $e$ 和 $f$，使得 $a = ec$，$b = fc$, 则 $ma + nb = mec + ncf = c(me + nf)$，于是，$c \mid (ma + nb)$；

定理 1.10：带余除法定理

如果 $a$ 和 $b$ 是整数且 $b > 0$，则存在唯一的整数 $q$ 和 $r$，使得 $a = bq + r, 0 \leqslant r < b$；

带余除法中，我们称 $q$ 为 商 (quotient)，$r$ 为 余数 (remainder)

证明：考虑形式为 $a - bk$ 的所有整数集合 $S$，其中 $k$ 为整数，即 $S = \{a - bk \mid k\in \mathbb{Z} \}$，设 $T$ 是 $S$ 中的所有非负整数构成的集合，$T$ 是非空的，因为当 $k$ 是满足 $k < {a \over b}$ 的整数时，$a - bk$ 是正的；

由良序性质，$T$ 中有最小元 $r = a - bq$，根据 $r$ 的构造我们知道 $r \geqslant 0$，且容易证明 $r < b$，如果 $r \geqslant b$，则 $r > r - b = a - bq - b = a - b(q + 1) \geqslant 0$，这与我们选择 $r = a - bq$ 为形如 $a - bk$ 的整数中的最小元矛盾，因此 $0 \leqslant r < b$；

为了证明 $q$ 和 $r$ 是唯一的，我们假定有两个方程 $a = bq_1 + r_1$ 和 $a = bq_2 + r_2$，满足 $0 \leqslant r_1 < b$，$0 \leqslant r_2 < b$，把第二个方程从第一个方程中减去，得：

于是

于是 $(r_2 - r_1) \mid b$，因为 $0 \leqslant r_1 < b$，$0 \leqslant r_2 < b$，我们有 $-b < r_2 - r_1 < b$，因此 $b$ 可以整除 $r_2 - r_1$，只有当 $r_2 - r_1 = 0$，或者说，当 $r_1 = r_2$ 时，因为 $bq_1 + r_1 = bq_2 + r_2$，且 $r_1 = r_2$，我们还得到 $q_1 = q_2$，这说明商 $q$ 与余数 $r$ 是唯一的；

奇偶定义：如果 $n$ 被 $2$ 除的余数为 $0$，则对某个整数 $k$，$n = 2k$，我们称 $n$ 为 偶数，而如果 $n$ 被 $2$ 的余数为 $1$，则对某个整数 $k$，有 $n = 2k + 1$，我们称 $n$ 为 奇数；

整数的表示和运算

算法定义：算法是为了实现一个计算或解决一个问题的精确指令的有限集合

素数和最大公因子

素数

素数定义：素数是大于 $1$ 的正整数，并且除了 $1$ 和它本身不能被其他正整数所整除；

合数定义：大于 $1$ 的不是素数的正整数称为合数；

引理 3.1：每一个大于 $1$ 的正整数都有一个素因子；

证明：用反证法

假设存在一个大于 $1$ 的正整数没有素因子，那么大于 $1$ 且没有素因子的正整数构成的集合非空，由良序性知集合存在一个最小的整数 $n$；

由于 $n$ 能被 $n$ 整除且 $n$ 没有素因子，那么 $n$ 不是素数，于是 $n$ 可以写成 $n =ab$, 其中 $1 < a < n$, $1 < b < n$；

因为 $a<n$，所以 $a$ 一定有素因子，由 定理 1.8, $a$ 的任何因子一定是 $n$ 的因子，那么 $n$ 就有素因子，与假设 $n$ 没有素因子矛盾；

于是，$n$ 一定有素因子，证毕；

定理 3.1： 存在无穷多个素数；

证明：用反证法

假设只有有限多个素数为 $p_1, p_2,\cdots,p_n$, 其中 $n \in \mathbb{N^+}$，考虑整数 $Q_n$, 由这些素数的乘积加 $1$ 得到，即：

由 引理 3.1，$Q_n$ 至少有一个素因子，设为 $q$；

如果 $q = p_j$, $1 \leqslant j \leqslant n$，由于 $Q_n - p_1p_2 \cdots p_n =1$, 且 $q$ 可以整除上面等式的左端两项，那么由 定理 1.9 可得 $q \mid 1$，这显然是不可能的，因为 $1$ 不能被任何素数整除，于是 $q$ 不是 $p_j$ 的任何一个那么就与假设矛盾；

证毕

定理 3.2： 如果 $n$ 是一个合数，那么 $n$ 一定有一个不超过 $\sqrt{n}$ 的素因子；

证明：

既然 $n$ 是合数，那么 $n$ 可以写为 $n = ab$，不妨设 $1 < a \leqslant b < n$. 我们一定有 $a \leqslant n$；

否则 $b \geqslant a > \sqrt{n}$，那么有 $ab > \sqrt{n} \cdot \sqrt{n} = n$，与题设矛盾；

由 引理 3.1, $a$ 至少有一个素因子，再由 定理 1.8 可得，$a$ 的因子一定也是 $n$ 的因子，显然这个素因子小于等于 $\sqrt{n}$；

埃拉托色尼斯筛法：给定一个正整数 $n$, 我们使用 定理3.2 可以找到所有小于等于 $n$ 的素数；

定义：函数 $\pi(x)$ 表示不超过 $x$ 的素数的个数，其中 $x$ 是正实数；

定理 3.3：狄利克雷等差数列素数定理

假设 $a, b$ 是不能被同一个素数整除的正整数，那么等差数列 $an + b,\ n \in \mathbb{N^+}$，包含了无穷多的素数；

目前为止狄利克雷定理没有简单证法，狄利克雷的原始证明 (1837) 使用了复变量，后来塞尔伯格(Selberg) 在 1949 年给出了一个初等但较复杂的证明；^[1]

当前 (2021-10-01) 已知最大的素数是 $2^{82,589,933} − 1$ ^[2]

米尔斯(Mills) 证明了存在一个常数 $\Theta$ 使得函数 $f(n) = [\Theta^{3n}]$ 只生成
素数，我们只知道 $\Theta$ 的近似值 $\Theta \approx 1.3064$，用这个公式产生素数是不实用的，不仅因为 $\Theta$ 的确切值未知，也因为要计算出 $\Theta$, 必须知道函数 $f(n)$ 所生成素数的值

关键词

• 素性验证算法：检验一个数 $n$ 是否为素数的算法
• 广义黎曼猜想
• 米勒(G. L. Miller)
• M. Agrawal
• 索菲·热尔曼(Sophie Germain) 素数密度

参考引用

1. https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions
2. https://en.wikipedia.org/wiki/Largest_known_prime_number

素数的分布

黎曼 $\zeta$ 函数：复平面上的函数

$$\zeta(s) = \sum_{n = 1}^\infty {1 \over n^s} = \prod_{p}\left(1 - {1 \over p^s}\right)^{-1}$$

其中 $\displaystyle \prod_{p}$ 表示乘积取遍所有的素数；后面的部分不属于 $\zeta$ 函数，但是与素数有关系；

定理 3.4：素数定理

$$\lim_{x \to \infty} {\pi(x) \over {x / \log x}} = 1$$

注：一个简单的方法来表述素数定理是写成 $\pi(x) \sim x/\log x$，这里 $\sim$ 符号表示 渐进于；

推论 3.4.1： 令 $p_n$ 是第 $n$ 个素数，那么 $p_n \sim n \log n$.

定理 3.5： 对于任意的正整数 $n$, 存在至少 $n$ 个连续的正合数；

证明：

考虑如下 $n$ 个连续的正整数

$(n + 1)! + 2, (n + 1)! + 3, ···, (n + 1)! + n + 1$

当 $2 \leqslant j \leqslant n + 1$ 时，我们知道 $j \mid (n + 1)!$，由 定理 1.9 有 $j \mid (n + 1)! + j$，因此，这 $n$ 个连续的整数都是合数；

关于素数的猜想

伯特兰猜想：1845 年，法国数学家伯特兰猜想对于任意给定的正整数 $n$, $n > 1$, 存在一个素数 $p$, 使得 $n<p<2n$；

该猜想已被证明，于是又叫做 伯特兰公设

挛生素数猜想：存在无穷多的形如 $p$ 和 $p + 2$ 的素数对；

1966 年，中国数学家陈景润用复杂的筛法证明了存在无穷多个素数 $p$, 使得 $p + 2$ 至多有两个素数因子；

哥德巴赫猜想：每个大于 $2$ 的正偶数可以写成两个素数的和

这个猜想是 1742 年在哥德巴赫写给欧拉的信中提出的；

对于这个猜想的证明至今还没有人给出，至今为止最好的进展是陈景润在 1966 年给出的，他用强大的筛法证明了每个足够大的偶数可以写为一个素数和一个 至多由两个素数的乘积 得到的数的和；

$n^2 + 1$ 猜想：存在无穷多个形如 $n^2 + 1$ 的素数，其中 $n$ 是正整数；

对于这个猜想至今为止得到的最好的结果是，存在无穷多个 $n$ 使得$n^2 + 1$ 是素数或者是两个素数的乘积；这个证明是 Henryk Iwaniec 在 1973 年给出的；

关键词

• 黎曼猜想
• 伯特兰
• 哥德巴赫
• 陈景润
• 华罗庚
• Henryk Iwaniec

最大公因子

最大公因子定义：两个不同时为零的整数 $a, b$ 的 最大公因子 就是指能同时整除 $a, b$ 的最大的整数；

$a, b$ 的最大公因子记为 $(a, b)$，在数论之外，记号 $\gcd(a, b)$ 也同样被使用；gcd 为 greatest common divisor 的首字母缩写；

定义：$(0, 0) = 0$，这么做是为了保证我们证明的关于最大公因子的结论对所有的情况都成立；

互素定义：定义如果两个整数 $a, b$ 的最大公因子 $(a, b) = 1$, 那么这两个数就被称为互素的；

定理 3.6：$a, b$ 是整数，且 $(a, b) =d$，那么 $(a/d, b/d) = 1$；

证明：

已知 $a, b \in \mathbb{Z}$，且 $(a, b) = d$，我们将证明 $a/d, b/d$ 除了 $1$ 之外没有其他的公因子；

假设还有正整数 $e$ 使得 $e \mid (a/d)$ 且 $e \mid (b/d)$，那么存在整数 $k$ 和 $l$ 使得 $a/d= ke$，$b/d =le$；

于是 $a = dek$，$b = del$，因此 $de$ 是 $a, b$ 的公因子，因为 $d$ 是 $a, b$ 的最大公因子，则有 $de \leqslant 1$, 于是 $e = 1$. 因此 $(a / d, b / d)= 1$

定理 3.7： 令 $a, b, c$ 是整数，那么 $(a + cb, b) = (a, b)$

证明：

$a, b, c \in \mathbb{Z}$，我们将证明 $a, b$ 的公因子与 $a+cb, b$ 的公因子相同，这就证明了 $(a + cb, b) = (a, b)$；

令 $e$ 是 $a, b$ 的公因子，由 定理 1.9 我们有 $e \mid (a+cb)$ ，所以 $e$ 是 $a+cb$ 和 $b$ 的公因子；

如果 $f$ 是 $a+ cb$ 和 $b$ 的公因子，那么由 定理 1.9 我们有 $f$ 整除 $(a + cb) - cb = a$，
所以 $f$ 是 $a, b$ 的公因子；

因此 $(a + cb, b) = (a, b)$，证毕；

线性组合定义：如果 $a, b$ 是整数，那么它们的线性组合具有形式 $ma +nb$, 其中 $m, n$ 都是整数；

定理 3.8：两个不全为零的整数 $a, b$ 的最大公因子是 $a, b$ 线性组合中最小的正整数；

证明：

因为当 $a\neq 0$ 时，两个线性组合 $1 \cdot a + 0 \cdot b$ 和 $(-1) \cdot a+ 0 \cdot b$ 中必有一个为正，那么由良序性质，存在正整数 $d$ 是 $a, b$ 线性组合中最小的正整数，我们有：

其中 $m, n \in \mathbb{Z}$，我们将证明 $d \mid a, d \mid b$；

由带余除法，得到：

由这个方程和 $(1)$ ，我们可以得到：

这就证明了整数 $r$ 是 $a, b$ 的线性组合，因为 $0 \leqslant r <d$, $d$ 是 $a, b$ 线性组合中最小的正整数，于是我们得到 $r = 0$, 因此 $d \mid a$. 同理可得，$d \mid b$；

我们证明了 $a, b$ 线性组合中最小的正整数 $d$ 是 $a, b$ 的公因子，那么剩下要证的是它是最大的公因子；

我们只需证明 $a, b$ 所有的公因子 $c$, 都能整除 $d$；

由于所有 $d$ 的正的因子都要小于 $d$，且 $d =ma+ nb$, 如果 $c \mid a$ 且 $c \mid b$，那么由 定理 1.9 有 $c \mid d$, 因此我们有 $d \geqslant c$. 这就得到了结论；

定理 3.8 可以用于求得两个数的最大公因子；

推论 3.8.1：如果整数 $a, b$ 互素，那么存在整数 $m, n$ 使得 $ma+ nb=1$

证明：

我们注意到如果 $a, b$ 互素，那么 $(a, b)=1$. 因此由 定理 3.8.1 是 $a$ 和 $b$ 线性组合的最小正整数；

于是存在整数 $m, n$ 使得 $ma+ nb = 1$；

定理 3.9：如果 $a, b$ 是正整数，那么所有 $a, b$ 线性组合与所有 $(a, b)$ 倍数构成的集合相同；

证明：

假设 $d = (a, b)$，我们首先证明每个 $a, b$ 的线性组合是 $d$ 的倍数；

注意到最大公因子的定义，我们有 $d \mid a$ 且 $d \mid b$，那么每个 $a, b$ 的线性组合具有形式 $ma+ nb$, 其中 $m, n$ 是整数；

由 定理 1.9 只要 $m, n$ 是整数，我们就有 $d$ 整除 $ma + nb$，因此，$ma +nb$ 是 $d$ 的倍数；

我们现在证明每一个 $d$ 的倍数也是 $a, b$ 的线性组合；

由 定理 3.8，存在整数 $r, s$ 使得 $ra + sb = d$，而 $d$ 的倍数具有形式 $jd$, 其中 $j$ 是整数，于是 $jd = (jr) a + (js) b$；

因此，每个 $d$ 的倍数是 $a, b$ 的线性组合，这就完成了证明；

定理 3.10：如果 $a, b$ 是不全为零的整数，那么正整数 $d$ 是 $a, b$ 的最大公因子当且仅当:
1. $d \mid a$ 且 $d \mid b$
2. 如果 $c$ 是整数且 $c \mid a$, $c \mid b$

那么 $c \mid d$

证明：

我们首先证明 $a, b$ 的最大公因子具有这两个性质；

设 $d=(a, b)$，有 $d \mid a$ 且 $d \mid b$，由 定理 3.8 有 $d =ma+ nb$, 其中 $m, n$ 是整数；

因此，如果 $c \mid a$ 且 $c \mid b$，那么由 定理 1.9 就有 $c \mid d= ma+ nb$；

于是，证明了如果 $d=(a, b)$，那么性质 $(1)$ 和 $(2)$ 成立；

现假设 $d$ 具有性质 $(1)$ 和 $(2)$，由性质 $(1)$ 可得 $d$ 是$a, b$ 的公因子，进一步由性质 $(2)$ 我们知道，如果 $e$ 是 $a, b$ 的公因子，那么 $c \mid d$；

所以就有整数 $k$ 使得 $d = ck$，因此，$c=d/k \leqslant d$，这就证明了满足性质 $(1)$ 和 $(2)$ 的正整数一定是 a, b 的最大公因子；

定义：令 $a_1, a_2,\cdots, a_n$ 是不全为零的整数，这些整数的公因子中最大的整数就是 最大公因子；记为 $(a_1, a_2,\cdots, a_n)$（注意 $a_i$ 顺序无关）

互素定义：

如果 $(a_1, a_2,\cdots, a_n) = 1$, 那么我们说 $(a_1, a_2,\cdots, a_n)$ 互素；

如果整数集合 $S$ 中每对 $a_i, a_j, i \neq j$，有 $(a_i, a_j) = 1$, 即 $S$ 中的任意一对整数都互素，那么我们就说这些整数 两两互素；

欧几里得算法

我们将建立一套系统的算法来求两个正整数的最大公因子，这个方法被称为 欧几里得算法

定理 3.11：欧几里得算法

整数 $a \geqslant b>0$，令 $r_0＝ a$, $r_1 = b$，如果我们做带余除法得到 $r_j = r_{j+1} q_{j+1} + r_{j+2}$，且 $0<r_{j+2}<r_{j + 1}$，$j=0, 1, 2, \cdots, n-2$ 且有 $r_{n+1} = 0$，那么 $(a, b)=r_n$，即最后一个非零余数；

从定理中我们看到通过带余数的除法，在每一步中被除数和除数被更小的数代替，这些更小的数实际上是每一步中的除数和余数，运算知道余数为零时终止；这一系列的运算产生了一系列的等数，而最大公约数就是最后一个非零的余数。

引理 3.3：如果 $e$ 和 $d$ 是整数且 $e = dq + r$，其中 $q,r$ 是整数，那么 $(e, d) = (d, r)$

证明：在 定理 3.7 中，将 $a, b, c$ 用 $r, d, q$ 代替，即可证明；

现在，我们开始证明欧几里得算法的结果是两个数的最大公因子；

$a, b$ 是正整数，其中 $a \geqslant b$，令 $r_0 = a, r_1 = b$，那么通过带余数的除法，我们得到

假设最终一定会有一个余数为零，正是因为余数组成的序列为 $a = r_0 \geqslant r_1 > r_2 > \cdots \geqslant 0$，序列包含的向的个数不会大于 $a$，由 引理 3.3，我们得到 $(a, b)=(r_0, r_1)=\cdots=(r_n, 0) = r_n$

因此 $(a, b) = r_n$，即最后一个非零余数，证毕；

下面给出欧几里得算法求最大公因子的 Python 程序，可能有用：

递归实现：

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a

    r = a % b
    return gcd(b, r)

非递归实现，一般情况下，非递归实现效率更高

def gcd(a: int, b: int) -> int:

    while b != 0:
        r = a % b
        a = b
        b = r

    return a

定理 3.12 令 $f_{n+1}$ 和 $f_{n+2}\quad(n>1)$ 是斐波那契序列中连续两项．那么用欧几里得算法证明 $(f_{n+1}, f_{n+1}) = 1$,一共需要 $n$ 步除法；

证明：

应用欧几里得算法，从斐波那契序列的定义出发，我们在每一步都有

那么

因此，用欧几里得算法证明 $(f_{n+1}, f_{n+1}) = 1$，一共需要 $n$ 步除法；

引理：斐波那契数 比 公比为 $\alpha = (1 + \sqrt{5}) /2$ 的等比数列增长的快；

证明：我们用第二数学归纳法

对于 $n \geqslant 3$，$f_n > \alpha^{n - 2}$，其中 $\alpha = (1 + \sqrt{5}) /2$；

基础步骤包括对 $n = 3$ 和 $n = 4$ 验证这个不等式；

我们有 $\alpha < 2 =f_3$, 所以定理对 $n = 3$ 成立

由于 $a^2 = (3 + \sqrt{5}) / 2 < 3 = f_4$，故定理对 $n = 4$ 成立；

归纳假设，假定对满足 $k \leqslant n$ 的所有整数 $k$, 都有 $\alpha^{k-2}<f_k$；

由于 $a= (1 + \sqrt{5})/2$ 是 $x^2 - x -1 =0$ 的一个解，我们有 $\alpha^2 = \alpha + 1$，因此：

由归纳假设，我们得到不等式：

把这两个不等式加起来，得到：

这就完成了证明；

定理 3.13：拉梅定理

用欧几里得算法计算两个正整数的最大公因子时，所需的除法次数，不会超过两个整数中较小的那个十进制数的位数的 $5$ 倍；

证明：

当我们用欧几里得算法计算两个整数 $a = r_0$, $b = r_1$ $(a > b)$ 的最大公因子的时候，我们会得到下面的一系列等式：

我们用了 $n$ 次除法，注意到每个商 $q_1, q_2, \cdots, q_{n - 1} \geqslant 1$, $q_n \geqslant 2$ ，因为 $r_n < r_{n - 1}$，因此：

故如果在欧儿里得算法中用了 $n$ 次除法，那么必有 $b \geqslant f_{n + 1}$，

由上面的引理, 我们知道当 $n>2$ 时 $f_{n + 1} > \alpha^{n - 1}$，其中 $a= (1 + \sqrt{5})/2$，因此有 $b>\alpha^{n-1}$；

又由于 $\log_{10} \alpha > 1/5$, 那么我们就得

因此，

令 $b$ 的十进制位数是 $k$，那么 $b < 10k$，即 $\log_{10}b < k$，因此我们得 $n-1<5k$，因为 $k$ 是整数，
那么就得到了结论 $n \leqslant 5k$，这就证明了拉梅定理；

推论 3.13.1：求两个正整数 $a, b, a>b$ 的最大公因子需要 $O[(\log_2 a)^3]$ 次的位运算；

定理 3.14：扩展欧几里得算法

如果 $a, b \in \mathbb{N^+}$，那么 $(a, b) = s_na + t_n b$

其中，$s_n, t_n$ 是下面定义的递归序列的第 $n$ 项

$$\begin{aligned} s_0 = 1, t_0 = 0, \\ s_1 = 0, t_1 = 1, \end{aligned}$$

且

$$s_j = s_{j-2} - q_{j-1}s_{j-1}, t_j = t_{j-2} - q_{j-1}t_{j-1}$$

其中 $j=2, 3, \cdots, n$，$q_j$ 是欧几里得算法中的每一步的商；

证明：我们将证明

因为 $(a, b) = r_n$，一旦上式成立，我们就有

我们用 第二数学归纳法 来证明

对于 $j = 0$，有 $a = r_0 = 1 \cdot a + 0 \cdot b = s_0 a + t_0 b$，成立；

对于 $j = 1$， $b = r_1 = 0 \cdot a + 1 \cdot b = s_1 a + t_1 b$，成立；

现在假设

对于 $j = 1, 2, \cdots, k-1$ 成立，那么，由欧几里得算法的第 $k$ 步，我们有：

那么由归纳假设，得到：

证毕；

这个算法可以将 $(a, b)$ 表示成 $a, b$ 的线性组合，这在密码学中有很大用处；

注意到两个整数的最大公因子的线性组合的表示方法有无穷多种，因为，令 $d=(a, b)$ 且 $d =sa + tb$ 就是 $d$ 的一种线性表示方法，它的存在性在前面已经讨论过了；那么对于所有的整数 $k$ 有

下面给出，扩展欧几里得算法的 Python 实现，返回值为，$\gcd(a, b)$，$s_n$, $t_n$，尽管，样子有点丑陋，主要还是和证明过程一致：

def ext_euclid(a: int, b: int):
    s = [1, 0, 0]
    t = [0, 1, 0]
    q = [0, 0, 0]

    j = 0

    while b != 0:
        q[(j + 1) % 3], r = divmod(a, b)

        if j > 1:
            s[j % 3] = s[(j - 2) % 3] - q[(j - 1) % 3] * s[(j - 1) % 3]
            t[j % 3] = t[(j - 2) % 3] - q[(j - 1) % 3] * t[(j - 1) % 3]

        a = b
        b = r
        j += 1

    s[j % 3] = s[(j - 2) % 3] - q[(j - 1) % 3] * s[(j - 1) % 3]
    t[j % 3] = t[(j - 2) % 3] - q[(j - 1) % 3] * t[(j - 1) % 3]
    return a, s[j % 3], t[j % 3]

这个算法实现可以与欧几里得算法的非递归实现对比一下，就可以体验到前缀扩展的具体内容；

关键词

• 阿耶波多 Aryabhata
• 拉梅定理

算术基本定理

定理 3.15：算术基本定理

每个大于 $1$ 的正整数都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列；

整数分解中把素因子组合成幂的形式被称为 素幂分解

引理 3.4：如果 $a, b$ 和 $c$ 是正整数，满足 $(a, b)=1$ 且 $a \mid bc$, 则 $a \mid c$；

引理 3.5：如果 $p$ 整除 $a_1, a_2, \cdots, a_n$，其中 $p$ 为素数，且 $a_1,a_2, \cdots, a_n$ 是正整数，则存在整数 $i$，$1 \leqslant i \leqslant n$，使得 $p$ 整除 $a_i$；

最小公倍数定义：两个非零整数 $a$ 和 $b$ 的最小公倍数(the least common multiple) 是能够被 $a$ 和 $b$ 整除的最小正整数；

$a$ 和 $b$ 的最小公倍数记为 $[a, b]$；记号 $\textrm{lcm}(a, b)$ 也常常被用来表示 $a$ 和 $b$ 的最小公倍数；

引理 3.6：如果 $x$ 和 $y$ 为实数，则 $\max(x, y) + \min(x, y) =x +y$;

定理 3.16：如果 $a$ 和 $b$ 是正整数，则 $[a, b] =ab / (a, b)$，其中 $[a, b]$ 和 $(a, b)$ 分别是 $a$ 和 $b$ 的最小公倍数和最大公因子；

引理 3.7：设 $m$ 和 $n$ 是互素的正整数，那么如果 $d$ 是 $mn$ 的一个正因子，则存在唯一的一对 $m$ 的正因子 $d_1$ 和 $n$ 的正因子 $d_2$ 使得 $d=d_1d_2$；反之，如果 $d_1$ 和 $d_2$ 分别是 $m$ 和 $n$ 的正因子，则 $d = d_1d_2$ 是 $mn$ 的正因子；

引理 3. 8：如果 $a$ 和 $b$ 都是形如 $4n + 1$ 的整数，则乘积 $ab$ 也是这种形式的；

定理 3.17：存在无穷多个形如 $4n +3$ 的素数，其中 $n$ 为正整数；

定理 3.18：设 $a$ 为多项式 $x^n + c_{n - 1} x^{n - 1} + \cdots + c_nx + c_0$ 的根，其中系数 $c_0, c_1, \cdots, c_{n - 1}$ 为整数，则 $a$ 或者是整数，或者是无理数；

定理 3.19：如果 $s$ 是实数且 $s>1$，则：

$$\zeta(s) = \sum_{n = 1}^\infty {1 \over n^s} = \prod_{p}\left(1 - {1 \over p^s}\right)^{-1}$$

因子分解法和费马数

引理 3.9：如果 $n$ 是一个正的奇数，那么 $n$ 分解为两个正整数的积和表示成两个平方数的差是一一对应的；

费马数：整数 $F_n = 2^{2^n} + 1$ 被称为费马数，费马猜想这些整数都是素数；

但是很不幸，$F_5 = 2^{2^5} + 1$ 是合数；

定理 3.20：费马数 $F_n = 2^{2^n} + 1$ 的每个素因子都形如 $2^{n+2}k+1$；

引理 3.10：设 $F_k = 2^{2^k} + 1$ 表示笫 $k$ 个费马数，这里 $k$ 为非负整数，那么对于所有正整数 $n$，我们有：

$$F_0F_1F_2 \cdots F_{n - 1} = F_{n - 2}$$

定理 3.21：设 $m$ 和 $n$ 为互异的非负整数，则费马数 $F_m$ 和 $F_n$ 是互素的；

定理 3.22：一个正规 $n$ 边形可用尺规来画出，当且仅当 $n$ 是一个 $2$ 的非负幂次与非负个不同费马素数的乘积；

线性丢番图方程

定理 3.23：设 $a, b$ 是整数且 $d = (a, b)$

如果 $d \nmid c$，那么方程 $ax+ by= c$ 没有整数解；

如果 $d \mid c$, 那么存在无穷多个整数解；

另外，如果 $x =x_0, y = y_0$ 是方程的一个特解，那么所有的解可以表示为：

$$\begin{aligned} x =& x_0 + (b / d)n, \\ y =& y_0 - (a / d)n, \end{aligned}$$

其中 $n$ 是整数；

定理 3.24： 如果 $a_1, a_2, \cdots, a_n$ 是正整数，那么方程：

$$a_1x_1 + a_2x_2 + \cdots + a_nx_n = c$$

有整数解，当且仅当 $d = (a_1, a_2, \cdots, a_n)$ 能整除 $c$；

另外当存在一个解的时候，那么方程有无穷多个解；

同余

同余是高斯于 19 世纪初提出的；

定义：设 $m$ 时正整数，若 $a$ 和 $b$ 是整数，且 $m \mid (a-b)$，则称 $a$ 和 $b$ 模 $m$ 同余;

若 $a$ 和 $b$ 模 $m$ 同余，则记 $a \equiv b \pmod m$，若 $m \nmid (a-b)$，则记 $a \not\equiv b \pmod m$ ，并称 $a$ 模 $m$ 不同余于 $b$，整数 $m$ 称为同余的模；

另一个同余的记号是 $a \bmod m = r$，它表示 $r$ 是 $a$ 被 $m$ 除所得的余数；

定理：若 $a$ 和 $b$ 是整数，则 $a \equiv b \pmod m$ 当且仅当存在整数 $k$, 使得 $a= b + km$

证明：

若 $a \equiv b \pmod m$，则 $m \mid (a - b)$，这说明存在 $k \in \mathbb{Z}$，使得 $km = a - b$，所以 $a = b + km$；

反过来，若存在整数 $k$ 使得 $a=b +km$, 则 $km =a - b$，于是，$m \mid (a - b)$，$a \equiv b \pmod m$；

定理：设 $m$ 是正整数，模 $m$ 的同余满足下面的性质：
1. 自反性：若 $a$ 是整数，则 $a \equiv a \pmod m$；
2. 对称性：若 $a$ 和 $b$ 是整数，且 $a \equiv b \pmod m$ ，则 $b \equiv a \pmod m$；
3. 传递性：若 $a, b$ 和 $c$ 是整数，且 $a \equiv b \pmod m$ 和 $b \equiv c \pmod m$ ，则 $a \equiv c \pmod m$；

证明：

1. 因为 $m \mid (a - a) = 0$，所以 $a \equiv a \pmod m$；
2. 若 $a\equiv b \pmod m$，则 $m \mid (a - b)$，从而存在整数 $k$，使得 $km = a - b$，$-km = b - a$，即 $m \mid (b - a)$，故 $b \equiv a \pmod m$；
3. 若 $a \equiv b \pmod m$，且 $b \equiv c \pmod m$，则有 $m \mid (a - b)$ 和 $m \mid (b - c)$，从而存在 $k, l$，使得 $km = a - b$, $lm = b - c$，于是 $a - c = (a - b) + (b - c) = km + lm = (k + l)m$，因此 $m \mid (a - c)$，$a\equiv c \pmod m$；

定义：一个模 $m$ 完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模 $m$ 同余；

由带余除法可知，整数 $0, 1, \cdots ,m-1$ 的集合是模 $m$ 完全剩余系，称为模 $m$ 最小非负剩余的集合；

我们将经常作同余的算术运算，这种算术称为 模算术；

定理 4.3：若 $a, b, c$ 和 $m$ 是整数，$m > 0$, $a \equiv b \pmod m$，则：
1. $a + c \equiv b + c \pmod m$,
2. $a - c \equiv b - c \pmod m$,
3. $ac \equiv bc \pmod m$

证明：

因为 $a \equiv b \pmod m$，所以 $m \mid (a - b)$：

1. 由等式 $(a + c) - (b + c) = a - b$ 可得，$m \mid (a + c) - (b + c)$，得证；
2. 由等式 $(a - c) - (b - c) = a - b$ 可得，$m \mid (a - c) - (b - c)$，得证；
3. 由 $ac - bc = c(a - b)$，所以 $m \mid c(a - b)$，从而 $ac \equiv bc \pmod m$；

定理 4.4：若 $a, b, c$ 和 $m$ 是整数，$m>0$, $d=(c, m)$，且有 $ac \equiv bc \pmod m$，则 $a \equiv b \pmod {m/d}$

证明：

若 $ac \equiv bc \pmod m$，则 $m \mid (ac - bc) = c(a - b)$，所以，存在整数 $k$, 使得 $c(a -b) =km$

两边同时除以 $d$, 得到 $(c / d) (a - b) = k(m / d)$，因为 $(m/d, c/d) = 1$, 有 $m/d \mid (a -b)$，因此， $a \equiv b \pmod {m/d}$；

推论 4.4.1：若 $a, b, c$ 和 $m$ 是整数，$m > 0$, $(c, m) =1$, 且有 $ac \equiv bc \pmod m$，则 $a \equiv b \pmod m$

定理 4.5：若 $a, b, c, d$ 和 $m$ 是整数，$m>0$, $a \equiv b \pmod m$，且 $c \equiv d \pmod m$，则：

1. $a + c \equiv b + d \pmod m$
2. $a - c \equiv b - d \pmod m$
3. $ac \equiv bd \pmod m$

引理 4.1：$m$ 个模 $m$ 不同余的整数的集合构成一个模 $m$ 的完全剩余系；

定理 4.6：若 $r_1, r_22, \cdots ,r_m$ 是一个模 $m$ 的完全剩余系，且正整数 $a$ 使得 $(a, m) =1$，则对任何整数 $b$：

$$ar_1 + b, ar_2 + b, \cdots ,ar_m + b$$

都是模 $m$ 的完全剩余系；

定理 4.7：若 $a, b, k$ 和 $m$ 是整数，$k>0$, $m>0$, 且 $a \equiv b \pmod m$，则 $a^k \equiv b^k \pmod m$

定理 4.8：若 $a \equiv b \pmod {m_1}$, $a \equiv b \pmod {m_2}$, $\cdots$, $a \equiv b \pmod {m_k}$，其中 $a, b, m_1, m_2, m_k$ 是整数，且 $m_1, m_2, \cdots, m_k$ 是正的，则：

$$a \equiv b \pmod {[m_1, m_2, \cdots, m_k]}$$

其中 $[m_1, m_2, \cdots, m_k]$ 是 $m_1, m_2, \cdots, m_k$ 的最小公倍数；

推论 4.8.1：若 $a \equiv b \pmod {m_1}$, $a \equiv b \pmod {m_2}$, $\cdots$, $a \equiv b \pmod {m_k}$，其中 $a, b$ 是整数，且 $m_1, m_2, \cdots, m_k$ 两两互素的正整数，则：

$$a \equiv b \pmod {m_1m_2\cdots m_k}$$

模指数运算

这里是 快速模幂算法及其证明 的详细信息

计算 $b^N$ 模 $m$ 的一般过程，其中 $b, m$ 和 $N$ 是正整数；

1. 将 $N$ 用二进制记号表示成 $N = (a_ka_{k-1} \cdots a_1a_0)_2$；
2. 用逐个平方及模 $m$ 约化求出 $b, b^2, b^4, \cdots, b^{2^k}$ 模 $m$ 的最小正剩余，其中 $a^k = 1$；
3. 取 $a^j = 1$ 的 $j$ 所对应的 $b^{2^j}$ 模 $m$ 的最小正剩余的乘积
4. 再模 $m$ 约化即可；

例子：求 $2^{644} \bmod 645$

1. $644 = (1010000100)_2$
2. 计算二进制位为 $1$ 的模算数：
   • $2^{2^2} = 2^{4} \equiv 16 \pmod {645}$
   • $2^{2^7} = 2^{128} \equiv 391 \pmod {645}$
   • $2^{2^9} = 2^{512} \equiv 256 \pmod {645}$
3. 计算乘积再求模：

定理 4.9：设 $b, m$ 和 $N$ 是正整数，且 $b < m$. 则计算 $b^N$ 模 $m$ 的最小正剩余要用 $O[(\log_2m)^2 \log_2N]$ 次位运算；

证明：

我们可以用上面所描述的算法来求 $b^N$ 模 $m$ 的最小正剩余；

首先，用逐个平方及模 $m$ 约化求出 $b, b^2, b^4, \cdots, b^{2^k}$ 模 $m$ 的最小正剩余，其中 $2^k \leqslant N < 2^{k+1}$；

这总共需要 $O [(\log_2m)^2 \log_2N]$ 比特的运算，因为要做 $[\log_2N]$ 次模 $m$ 平方，每次平方需要 $O[(\log_2m)^2]$ 次位运算；

然后，取 $N$ 的二进制表示中为 $1$ 的数字对应的 $b^{2^j}$ 的最小正剩余的乘积，在每次乘法之后模 $m$ 约化，这也需要 $O[(\log_2m)^2 \log_2N]$ 次位运算；

因为至多有 $[log2N]$ 次乘法，而每次乘法需要 $O[(\log_2m)^2]$ 次位运算；

因此，总共需要 $O[(\log_2m)^2 \log_2N]$ 次位运算；

线性同余方程

设 $x$ 是未知整数，形如：

的同余式称为 一元线性同余方程；

定理 4.10：设 $a, b$ 和 $m$ 是整数，$m > 0$，$(a, m) = d$，
- 若 $d \nmid b$, 则 $ax \equiv b \pmod m$ 无解；
- 若 $d \mid b$, 则 $ax \equiv b \pmod m$ 恰有 $d$ 个模 $m$ 不同余的解；

推论 4.10.1：若 $a$ 和 $m>0$ 互素，且 $b$ 是整数，则线性同余方程 $ax \equiv b \pmod m$ 有模 $m$ 的唯一解；

模逆元定义：给定整数 $a$, 有 $(a, m)=1$, 称 $ax \equiv 1 \pmod m$ 的一个解为 $a$ 模 $m$ 的逆；

定理 4.11：设 $p$ 是素数，正整数 $a$ 是其自身模 $p$ 的逆，当且仅当 $a \equiv 1 \pmod p$ 或 $a \equiv -1 \pmod p$；

证明:

若 $a \equiv 1 \pmod p$ 或 $a \equiv -1 \pmod p$，则 $a^2 \equiv 1 \pmod p$，所以 $a$ 其自身模 $p$ 的逆；

反过来，若 $a$ 是其自身模 $p$ 的逆，则 $a^2 = a \cdot a \equiv 1 \pmod p$，因此，$p \mid (a^2 - 1)$，又因为 $a^2 - 1 = (a - 1)(a + 1)$，所以 $p \mid (a-1)$ 或 $p \mid (a+1)$，因此，或者 $a \equiv 1 \pmod p$，或者 $a \equiv -1 \pmod p$；

中国剩余定理（孙子定理）

出自公元四、五世纪中国南北朝时期的《孙子算经》卷下第二十六题，叫做 物不知数 问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？^[1]

以上问题可以转化为：求一个数，它被 $3$ 除余 $2$，被 $5$ 除余$3$，被 $7$ 除余 $2$，即下面的同余方程组：

涉及同余方程组的问题在公元一世纪希腊数学家尼科马凯斯(Nicomachus) 的著作中出现过，也在公元七世纪印度婆罗摩发多的著作中出现过；然而，直到 1247 年，秦九韶才在其著作《数书九章》中给出解线性同余方程组的一般方法；

引理一：如果整数 $a, b, c$, $(a, b) = (a, c) =1$, 那么 $(a, bc) = 1$；

证明：

$(a, b) = (a, c) = 1$，则存在 $k, l \in \mathbb{Z}$，使得 $b = ka + 1, c = la + 1$；

于是：

故：

引理二：如果对整数 $a_1, a_2, \cdots, a_n$，有另一个整数 $b$，使得 $(a_1, b) = (a_2, b) = \cdots = (a_n, b) = 1$, 那么 $(a_1 a_2 \cdots a_n, b) = 1$

证明：用数学归纳法

1. $n = 1$ 时，显然 $(a_1, b) = (a_1, b) = 1$ 成立；
2. 设 $n = k$ 时，$(a_1 a_2 \cdots a_k, b) = 1$ 成立
3. 当 $n = k + 1$ 时， 由于 $(a_{k + 1}, b) = 1$，由引理一有：

证毕；

中国剩余定理：设 $m_1, m_2, \cdots, m_r$，是两两互素的正整数，则同余方程组：

$$\begin{aligned} x &\equiv a_1 \pmod {m_1}, \\ x &\equiv a_2 \pmod {m_2}, \\ & \vdots \\ x &\equiv a_r \pmod {m_r} \\ \end{aligned}$$

有模 $M = m_1m_2 \cdots m_r$ 的唯一解；

证明：

首先，构造同余方程组的一个联立解，为此，令 $M_k = M /m_k =m_1\cdots m_{k-1} m_{k+1} \cdots m_r$；

因为 $j \neq k$ 时 $(m_j, m_k) = 1$, 所以由上面的 引理二 知 $(M_k, m_k)=1$；

再由 定理 4.10 可求得 $M_k$ 模 $m_k$ 的一个逆 $y_k$，所以 $M_k y_k \equiv 1 \pmod {m_k}$ 现在构造和：

此 $x$ 就是 $r$ 个同余方程的联立解；

要证明这一点，只须证对 $k = 1, 2, \cdots, r$ 有 $x \equiv a_k \pmod m_k$；

因为 $j \neq k$ 时 $m_j \mid M_k$，所以 $M_j \equiv 0 \pmod {m_k}$，因此，在 $x$ 的和式中，除了第 $k$ 项之外的所有项都和 $0 \pmod {m_k}$ 同余；

从而，$x \equiv a_k M_k y_k \equiv a_k \pmod {m_k}$，这是因为 $M_k y_k \equiv 1 \pmod {m_k}$；

现在来证任意两个解都是模 $M$ 同余的；

设 $x_0$ 和 $x_1$ 都是同余方程组 $r$ 个方程的联立解，则对每个 $k, x_0 \equiv x_1 \equiv a_k \pmod {a_k}$，所以 $m_k \mid (x_0 - x_1)$；

由 定理 4.8 可见，$M \mid (x_0 - x_1)$，因此 $x_0 \equiv x_1 \pmod M$，这说明同余方程组的 $r$ 个方程的联立解是模 $M$ 唯一的；

例：解方程组

解：

解方程组：

有：

构造：

引理 4.2：若 $a$ 和 $b$ 是正整数，则 $2^a-1$ 模 $2^b - 1$ 的最小正剩余是 $2^r - 1$, 其中 $r$ 是 $a$ 模 $b$ 的最小正剩余，即 $r = a \bmod b$；

引理 4.3：若 $a$ 和 $b$ 是正整数，则 $2^a -1$ 和 $2^b - 1$ 的最大公约数是 $2^{(a,b)} - 1$；

定理 4.13：正整数 $2^a - 1$ 和 $2^b - 1$ 是互素的，当且仅当 $a$ 与 $b$ 是互素的；

关键词

• 孙子：与《孙子兵法》作者孙武不是同一个人
• 秦九韶
• 尼科马凯斯(Nicomachus)
• 婆罗摩发多
• 中国剩余定理的计算机算术运算

参考引用

• https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86/2841597

求解多项式同余方程

定理 4.14：亨泽尔引理

设 $f(x)$ 是整系数多项式，$k \geqslant 2$ 是整数，再设 $r$ 是同余方程 $f(x) \equiv 0 \pmod {p^{k - 1}}$ 的解，则：

1. 若 $f'(r) \not\equiv 0 \pmod p$，则存在唯一整数 $t$, $0 \leqslant t \leqslant p$，使得 $f(r+tp^{k-1}) \equiv 0 \pmod {p^k}$，其中 $t$ 由：

$$t \equiv -\overline{f'(r)} (f(r)/p^{k - 1})\pmod p$$

给出，其中 $\overline{f'(r)}$ 是 $f'(r)$ 的模$p$ 逆；

2. 若 $f'(r)\equiv 0 \pmod p$, $f(r) \equiv 0 \pmod {p^k}$，则所有整数 $t$ 都有 $f(r+tp^{k-1}) \equiv 0 \pmod{p^k}$;
3. 若 $f'(r)\equiv 0 \pmod p$, $f(r) \not\equiv 0 \pmod {p^k}$，则 $f(x) \equiv 0 \pmod {p^k}$ 不存在解使得 $x\equiv r \pmod p^{k - 1}$；

在情形 $(1)$ 中，可见 $f(x) \equiv \pmod {p^{k - 1}}$ 的一个解提升为 $f(x) \equiv 0 \pmod {p^k}$ 的唯一解；

在情形 $(2)$ 中，这样的一个解或者提升为 $p$ 个模 $p^k$ 不同余的解，或者不能提升为模 $p^k$ 的解；

线性同余方程组

定理 4.15：设 $a, b, c, d, e, f$ 和 $m$ 是整数，$m>0$, 且 $(\Delta, m) =1$, 其中 $\Delta= ad - be$，则同余方程组：

$$\begin{aligned} ax + by \equiv e \pmod m \\ cx + dy \equiv f \pmod m \\ \end{aligned}$$

有模 $m$ 的唯一解如下：

$$\begin{aligned} x \equiv \overline{\Delta}(de - bf) \pmod m \\ y \equiv \overline{\Delta}(af - ce) \pmod m \\ \end{aligned}$$

其中 $\overline{\Delta}$ 是 $\Delta$ 模 $m$ 的一个逆；

TODO:......

利用波拉德 $\rho$ 方法分解整数

TODO:......

同余的应用

特殊的同余式

威尔逊定理和费马小定理

定理 6.1：威尔逊定理

若 $p$ 是素数，则 $(p - 1)! \equiv -1 \pmod p$

定理 6.2 设 $n$ 是正整数且 $n \geqslant 2$，若 $(n - 1)! \equiv -1\pmod n$，则 $n$ 是素数。

定理 6.3：费马小定理

设 $p$ 是一个素数，$a$ 是一个正整数且 $p \nmid a$，则 $a^{p - 1} \equiv 1\pmod p$

定理 6.4 设 $p$ 是素数且 $a$ 是一个正整数，则 $a^p \equiv a \pmod p$

定理 6.5 若 $p$ 是素数，$a$ 是一个整数且 $p\nmid a$，那么 $a^{p-2}$ 是 $a$ 模 $p$ 的逆

推论 6.5.1 若 $a$ 和 $b$ 是正整数，$p$ 是素数且 $p \nmid a$，那么线性同余方程 $ax \equiv b \pmod p$ 的解是满足 $x \equiv a^{p - 2} b \pmod p$ 的整数 $x$

伪素数

定义：令 $b$ 是一个正整数，若 $n$ 是一个正合数且 $b^n \equiv b \pmod n$，则 $n$ 称为 以 $b$ 为基的伪素数

引理 6.1：若 $d$ 和 $n$ 均是正整数且 $d$ 整除 $n$, 那么 $2^d -1$ 整除 $2^n - 1$

定理 6.6：以 $2$ 为基的伪素数有无穷多个

定义：一个合数 $n$ 若对所有满足 $(b, n) =1$ 的正整数 $b$ 都有 $b^{n - 1} \equiv 1 \pmod n$ 成立，则称之为卡迈克尔(Carmichael)数，或者称之为绝对伪素数；

1992年，已经证实存在无穷多个卡迈克尔数；

定理 6.7 若 $n=q_1q_2 \cdots q_k$, 其中 $q_j$ 是不同的素数满足 $(q_j - 1) \mid (n - 1)$ 对所有 $j$ 成立且 $k>2$，那么 $n$ 是一个卡迈克尔数；

定义：令 $n$ 是一个正整数，满足 $n > 2$ 且 $n-1 =2^st$，其中 $s$ 是一个非负整数，$t$ 是一个奇正整数，如果有 $b^t \equiv 1 \pmod n$ 或者 $b^{2^j t} \equiv -1 \pmod n$ 对某个 $j$ 成立，其中 $1 \leqslant j \leqslant s -1$，称 $n$ 通过 以 $b$ 为基的米勒检验；

定理 6.8 若 $n$ 是素数且 $b$ 是正整数满足$n \mid b$，那么 $n$ 能通过以 $b$ 为基的米勒检验；

定义：设 $n$ 是一个合数，且通过以 $b$ 为基的米勒检验，那么称 $n$ 为以 $b$ 为基的强伪素数；

定理 6.9 有无穷多个以 $2$ 为基的强伪素数

定理 6.10 若 $n$ 是一个奇正合数，那么最多有 $(n-1)/4$ 个 $b$，其中 $1 \leqslant b \leqslant n - 1$，使得 $n$ 能够通过以 $b$ 为基的米勒检验；

定理 6.11：拉宾(Rabin) 概率素性检验

设 $n$ 是一个正整数，取 $k$ 个不同的小于 $n$ 的正整数作为基，并且对 $n$ 做每一个基的米勒检验．若 $n$ 是一个合数，则 $n$ 通过所有 $k$ 个检验的概率不超过 $(1/4)^k$；

猜想 6.1 对任何一个正合数 $n$, 存在一个基 $b$, 且 $b < 2 (\log_2 n)^2$, 使得 $n$ 不能通过以 $b$ 为基的米勒检验；

定理 6.12 若广义黎曼猜想是正确的，那么存在一个算法来判断一个正整数 $n$ 是否是素数，并且该算法的位运算量是 $O[(\log_2 n)^5]$

欧拉定理

定义：设 $n$ 是一个正整数，欧拉 $\phi$ 函数 $\phi(n)$ 定义为不超过 $n$ 且与 $n$ 互素的正整数的个数

定义：模 $n$ 的既约剩余系 是由 $\phi(n)$ 个整数构成的集合，集合中的每个元素均与 $n$ 互素，且任何两个元素模 $n$ 不同余

定理 6.13：设 $r_1, r_2, \cdots, r_{\phi(n)}$ 是模 $n$ 的一个既约剩余系，若 $a$ 是一个正整数且 $(a, n) = 1$, 那么集合 $ar_1, ar_2, \cdots, ar_{\phi(n)}$ 也是模 $n$ 的一个既约剩余系

证明：反证法

先证明每个整数 $ar_j$ 与 $n$ 互素；

假设 $(ar_j, n) > 1$，那么 $(ar_j, n)$ 有一个素因子 $p$；

因此，或者 $p \mid a$ 或者 $p \mid r_j$；

从而有：或者 $p \mid a$ 且 $p \mid n$, 或者 $p \mid r_j$ 且 $p \mid n$；

但是因 $r_j$ 是模 $n$ 的既约剩余系中的元素，故 $p \mid r_j$ 与 $p \mid n$ 不能同时成立；

又因 $(a, n) =1$，故 $p \mid a$ 和 $p \mid n$ 不能同时成立；

因此，可以知道 $ar_j$ 与 $n$ 互素对 $j = 1, 2, \cdots, \phi(n)$ 成立；

为了说明 $ar_j$ 模 $n$ 彼此不同余，设 $ar_j = ar_k \pmod n$，其中 $j, k \in \mathbb{N^+}$，$j \neq k$ 且 $1 \leqslant j \leqslant \phi(n)$，$1 \leqslant k \leqslant \phi(n)$；

因 $(a, n) =1$，由 推论 4.4.1 知 $r_j \equiv r_k \pmod n$，又因 $r_j$ 和 $r_k$ 是前一个模 $n$ 的既约剩余系中的元素，故 $r_j \not\equiv r_k \pmod n$，得到矛盾；

定理 6.14：欧拉定理

设 $m$ 是一个正整数，$a$ 是一个整数且 $(a, m)=1$, 那么 $a^{\phi(m)} \equiv 1 \pmod m$

证明

令 $r_1, r_2, \cdots, r_{\phi(m)}$ 是由不超过 $m$ 且和 $m$ 互素的元素组成的既约剩余系；

由 定理 6.13, 因 $(a, m) = 1$, 故集合 $ar_1, ar_2, \cdots, ar_{\phi(m)}$ 也是模 $m$ 的一个既约剩余系；

从而，在一定的顺序下 $ar_1, ar_2, \cdots, ar_{\phi(m)}$ 的最小正剩余一定是 $r_1, r_2, \cdots, r_{\phi(m)}$；

因此，若把每个既约剩余系中所有项都乘起来，可得

因而

因为 $(r_1 r_2 \cdots r_{\phi(m)}, m) = 1$，由 推论 4.4.1 知 $a^{\phi(m)} \equiv 1 \pmod m$；

可以利用欧拉定理来寻找模 $m$ 的逆，若 $a$ 和 $m$ 互素，则

因此， $a^{\phi(m) - 1}$ 是 $a$ 模 $m$ 的逆；

乘性函数

欧拉 $\phi$ 函数

定义：定义在所有正整数上的函数称为 算术函数

定义：算术函数 $f$ 如果满足对任意两个互素的正整数 $n$ 和 $m$，均有 $f(mn) = f(m) f(n)$，就称为乘性函数（或积性函数）；

如果对任意两个正整数 $n$ 和 $m$, 均有 $f(mn) = f(m) f(n)$，就称为完全乘性（或完全积性）函数；

定理 7.1：如果 $f$ 是一个乘性函数，对任意正整数 $n$ 有素数幂分解 $n =p_1^{a_1}p_2^{a_2} \cdots p_s^{a_s}$，那么 $f(n) = f(p_1^{a_1})f(p_2^{a_2}) \cdots f(p_s^{a_s})$

证明：用数学归纳法

定理 7.2：如果 $p$ 是素数，那么 $\phi(p)=p-1$，反之，如果 $p$ 是一个正整数且满足小 $\phi(p) = p - 1$, 那么 $p$ 是素数；

定理 7.3：设 $p$ 是素数，$a$ 是一个正整数，那么 $\phi(p^a) =p^a - p^{a-1}$

定理 7.4：设 $m$ 和 $n$ 是互素的正整数，那么 $\phi(mn) = \phi(m)\phi(n)$

定理 7.5：设 $n = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}$ 为正整数 $n$ 的素数幂分解，那么

$$\phi(n) = n \left(1 - {1 \over p_1}\right)\left(1 - {1 \over p_2}\right) \cdots \left(1 - {1 \over p_k}\right)$$

定理 7.6：设 $n$ 是一个大于 $2$ 的正整数，那么 $\phi(n)$ 是偶数；

定理 7.7：设 $n$ 为一个正整数，那么

$$\sum_{d \mid n} \phi(d) = n$$

因子和与因子个数

定义：因子和函数 $\sigma$ 定义为整数 $n$ 的所有正因子之和，记为 $\sigma(n)$

定义：因子个数函数 $\tau$ 定义为正整数 $n$ 的所有正因子个数，记为 $\tau(n)$；

定理 7.8： 如果 $f$ 是乘性函数，那么 $f$ 的和函数，即 $\displaystyle F(n) = \sum_{d \mid n}f(d)$ 也是乘性函数；

推论 7.8.1：因子和函数 $\sigma$ 与因子个数函数 $\tau$ 是乘性函数；

引理 7.1：设 $p$ 是一个素数，$a$ 是一个正整数，那么：

$$\sigma(p^a) = 1 + p + p^2 + \cdots + p^a = {p^{a + 1} - 1 \over p - 1}$$

和

$$\tau(p^a) = a + 1$$

定理 7.9：设正整数 $n$ 有素因子分解 $n = p_1^{a_1}p_2^{a_2} \cdots p_s^{a_s}$，那么：

$$\sigma(n) = \prod_{j=1}^s {p_j^{a_j + 1} - 1 \over p_j - 1}$$

和

$$\tau(n) = \prod_{j=1}^s (a_j + 1)$$

完全数和梅森素数

定义：如果 $n$ 是一个正整数且 $\sigma(n) =2n$, 那么 $n$ 称为完全数；

定理 7.10：正整数 $n$ 是一个偶完全数当且仅当

$n = 2^{m - 1}(2^m-1)$

其中 $m \geqslant 2$ 是使得 $2^m - 1$ 是一个素数的整数

定理 7.11：如果 $m$ 是一个正整数且 $2^m -1$ 是一个素数，则 $m$ 必是素数；

定义：如果 $m$ 是一个正整数，那么 $M_m=2^m-1$ 称作笫 $m$ 个梅森数(Mersenne number)，如果 $p$ 是一个素数且 $M_p＝ 2^p -1$ 也是素数，那么 $M_p$ 就称为梅森素数(Mersenne prime)；

定理 7.12：如果 $p$ 是一个奇素数，那么梅森数 $M_p= 2^p -1$ 因子均形如 $2kp + 1$，其中 $k$ 是一个正整数；

定理 7.13 (Lucas-Lehmer 判定法）设 $p$ 是素数，设第 $p$ 个梅森数为 $M_p =2^p -1$，定义 $r_1 =4$，对 $k \geqslant 2$, 利用

$$r_k \equiv r_{k - 1}^2 - 2 \pmod {M_p}, \quad 0 \leqslant r_k < M_p$$

可以递归得到一整数序列，那么 $M_p$ 是素数当且仅当 $r_{p-1} \equiv 0 \pmod {M_p}$

莫比乌斯反演

定义莫比乌斯函数 $μ(n)$ 定义为

$$\mu(n) - \begin{cases} 1 & n = 1 \\ (-1)^r & n = p_1p_2\cdots p_r \\ 0 & n = \text{other} \end{cases}$$

其中，$p_i$ 为素数

定理 7.14：莫比乌斯函数 $μ(n)$ 是乘性函数；

定理 7.15：莫比乌斯函数的和函数在 $n$ 处的值 $\displaystyle F(n) = \sum_{d \mid n}μ(d)$，满足

$$F(n) = \begin{cases} 1 & n = 1 \\ 0 & n > 1 \end{cases}$$

定理 7.16：莫比乌斯反演公式
若 $f$ 是算术函数，$F$ 为 $f$ 的和函数，满足

$$F(n) = \sum_{d \mid n} f(d)$$

则对任意正整数 $n$

$$f(n) = \sum_{d\mid n} μ(d) F (n / d)$$

定理 7.17：设 $f$ 算术函数，它的和函数为 $\displaystyle F(n) = \sum_{d\mid n} f(d)$，那么如果 $F$ 是乘性函数，则 $f$ 也是乘性函数；

密码学

原根

整数的阶和原根

定义 设 $a$ 和 $n$ 是互素的正整数，使得 $a^x \equiv 1 \pmod n$ 成立的最小正整数 $x$ 称为 $a$ 模 $n$ 的阶；

记 $a$ 模 $n$ 的次数为 $\text{ord}_n a$，这个记号是由高斯于 1801 年在他的《算术探讨》(Disquisitiones Arithmeticae) 中首先引入的。

定理 9.1：如果 $a$ 和 $n$ 是互素的整数且 $n > 0$，那么正整数 $x$ 是同余式 $a^x \equiv 1 \pmod n$ 的一个解当且仅当 $\text{ord}_n a \mid x$

推论 9.1.1：如果 $a$ 和 $n$ 是互素的整数且 $n > 0$，那么 $\text{ord}_n a \mid \phi(n)$

原根与整数的阶的应用

二次剩余

十进制分数与连分数

某些非线性丢番图方程

高斯整数

参考引用

• Kenneth H．Rosen - 《初等数论及其应用》