9. 数论初步

由于数论的研究对象是整数集

Z

，在不加说明的情况下本节的所有变量默认都定义在

Z

上。

众所周知，在整数集上的除法运算是这样定义的：整数 $a$ 除以整数 $b$ 会得到一个 商（quotient） $q$ 和 余数（remainder） $r$ ，使得 $a = q b + r$ 。除法定理 表明，存在唯一的 $q$ 与 $r$ ，满足 $a = q b + r$ 且 $r \in [0, | b |)$ 。在后面，我们记两个整数 $a$ 与 $b$ 的商与余数分别为 $qcnt (a, b)$ 与 $rem (a, b)$ 。

我们称 $a$ 整除 $b$ ，当且仅当 $\exists k \in Z . k a = b$ 。记作 $a ∣ b$ 。

依据整除的定义，显然有如下整除的性质成立：

$n ∣ 0$ ， $n ∣ n$
若 $a ∣ b$ ，则 $a ∣ k b$
若 $a ∣ b$ 且 $b ∣ c$ ，则 $a ∣ c$
若 $a ∣ b$ 且 $a ∣ c$ ，则 $a ∣ p b + q c$ 对任意 $p$ 与 $q$ 成立

在最后一条性质中，我们称对整数 $b$ 与 $c$ ，所有可以被写作 $p b + q c$ 的整数为 $b$ 与 $c$ 的 整数线性组合，简称线性组合。更一般而言，对于一组整数 $a_{1}, a_{2}, \dots, a_{n}$ ， $A$ 为这组数的一个线性组合，当且仅当存在一组整数 $k_{1}, k_{2}, \dots, k_{n}$ ，有

A = \sum_{i = 1}^{n} k_{i} a_{i}

此外，对于能够同时整除 $b$ 与 $c$ 的 $a$ ，我们称其为 $b$ 与 $c$ 的 公约数。所有公约数中最大的数称作 最大公约数，记作 $a = gcd (b, c)$ 。依据良序原理，只要两个整数 $a$ 与 $b$ 不同时为 $0$ ，则 $gcd (a, b)$ 存在。

显然有如下关于最大公约数的性质成立：

$gcd (n, n) = gcd (n, 0) = n$ ， $gcd (n, 1) = 1$

欧几里得算法 可以用于在 $O (\log n)$ 的时间复杂度^[1]内快速求出两个数的最大公约数。其基于如下的引理：

若 $b \neq 0$ ， $gcd (a, b) = gcd (b, rem (a, b))$

证明

依据除法的定义，对给定的 $a$ 与 $b$ 存在 $q$ 与 $r$ 满足 $a = q b + r$ 。因此 $a$ 是 $b$ 与 $r$ 的线性组合，基于整除的性质，对任意 $x$ ，如果有 $x ∣ b$ 且 $x ∣ r$ ，则 $x ∣ a$ ；变形该式子得到 $r = a - q b$ ，因此 $r$ 是 $a$ 与 $b$ 的线性组合。同理得到对任意 $x$ ，如果有 $x ∣ a$ 且 $x ∣ b$ ，则 $x ∣ r$ ，这表明 $a$ 与 $b$ 的所有公因数与 $b$ 与 $r$ 的所有公因数完全相同，显然二者的最大公因数也相同，引理得证。

欧几里得算法可以被描述为一个定义在 $N^{2}$ 上的状态机：

初始状态：需要求最大公因数的两个数组成的数对 $(a, b)$ 。
转移规则： $(x, y) \to (y, rem (x, y))$ 。
终止条件与结果：当 $y = 0$ 时，状态机终止。得到 $gcd (a, b) = gcd (x, 0) = x$ 。

依据上面的引理，显然组成数对的两个数的最大公因数在状态转移过程中不会改变^[2]，因此该状态机是偏序正确的。考虑将状态机中的 $y$ 作为状态机的一个派生变量。由于在每次转移中显然有 $rem (x, y) < y$ 成立，该派生变量是严格递减的，因此该状态机必然会终止。由此我们证明了欧几里得算法的正确性。

裴蜀定理 是数论中的一条重要定理：

$a$ 与 $b$ 的最大公约数 $gcd (a, b)$ 是 $a$ 与 $b$ 的线性组合，即存在整数 $p$ 与 $q$ 使得
$gcd (a, b) = p a + q b$
一列不全为零的整数 $a_{1}, a_{2}, \dots, a_{n}$ 的最大公约数 $gcd (a_{1}, a_{2}, \dots, a_{n})$ 是该列数的线性组合，即存在 $k_{1}, k_{2}, \dots, k_{n}$ 使得
$gcd (a_{1}, a_{2}, \dots, a_{n}) = \sum_{i = 1}^{n} k_{i} a_{i}$

基于整除的性质，很容易得出推论：一个整数 $x$ 是 $a$ 与 $b$ 的线性组合，当且仅当 $gcd (a, b) ∣ x$ 。同理其是一列数 $a_{1}, a_{2}, \dots, a_{n}$ 的线性组合，当且仅当 $gcd (a_{1}, a_{2}, \dots, a_{n}) ∣ x$ 。

该定理可以通过拓展欧几里得算法证明。拓展欧几里得算法又称粉碎机，其不仅可以计算两个整数的最大公因数，还可以通过记录一些额外信息从而以与欧几里得算法相同的速度计算该最大公因数对应着何种线性组合。

粉碎机是一个定义在 $N^{6}$ 上的状态机：

初始状态： $(a, b, 1, 0, 0, 1)$ 。
转移规则： $(x, y, s, t, u, v) \to (y, r, u, v, s - q u, t - q v)$ 。式中 $q = qcnt (x, y)$ ， $r = rem (x, y)$ 。
终止条件与结果：当 $y = 0$ 时，状态机终止。得到 $gcd (a, b) = gcd (x, 0) = x = s a + t b$ 。

该算法的终止性与计算 $gcd (a, b)$ 的偏序正确性显然。下面详细叙述我们如何推导出该状态机的初始状态与转移规则与为什么这样的转移规则是正确的。

容易发现，欧几里得算法中的 $x$ 与 $y$ 在转移过程中总可以表示成初始状态对应的 $a$ 与 $b$ 的某种线性组合，这启示我们可以引入一些变量来记录这一信息。具体而言，我们令 $x = s a + t b$ ， $y = u a + v b$ 。初始状态下 $x = 1 \times a + 0 \times b$ 而 $y = 0 \times a + 1 \times b$ ，从而得到状态机初始状态下 $s = 1$ ， $t = 0$ ， $u = 0$ ， $v = 1$ 。接下来考虑欧几里得算法的转移过程：

\begin{aligned} x^{'} = y = u a + v b \\ y^{'} = r = x - q y = s a + t b - q (u a + v b) = (s - q u) a + (t - q v) b \end{aligned}

从而得到了状态机的转移规则。与此同时新状态中的 $x$ 与 $y$ 同样可以表示为 $a$ 与 $b$ 的线性组合，显然当状态机停止时， $gcd (a, b)$ 也可以表示为 $a$ 与 $b$ 的线性组合，裴蜀定理得证。

为了验证这样的转移规则是偏序正确的，我们希望证明下面两条性质是保持不变式：

\begin{array}{r} x = s a + t b \\ y = u a + v b \end{array}

证明是显然的，此处略去。

粉碎机所得到的只是 $gcd (a, b)$ 的一种线性组合表示。事实上， $gcd (a, b)$ 对应无限多种线性组合，这允许当粉碎机给出的结果不符合我们的需要时，可以在此基础上轻而易举地得到新的线性组合。例如，设粉碎机得到的结果为 $gcd (a, b) = s a + t b$ ，一种简单的变换方法如下：

gcd (a, b) = (s + k b) a + (t - k a) b

式中 $k$ 为任意正整数。该变换的正确性显然。

最大公因数还有如下性质：

对任意 $k > 0$ ， $gcd (k a, k b) = k gcd (a, b)$
$d ∣ a$ 且 $d ∣ b$ 当且仅当 $d ∣ gcd (a, b)$
若 $gcd (a, b) = 1$ 且 $gcd (a, c) = 1$ ，则 $gcd (a, b c) = 1$
若 $a ∣ b c$ 且 $gcd (a, b) = 1$ ，则 $a ∣ c$
$gcd (a^{n}, b^{n}) = (gcd (a, b))^{n}$
$gcd (a_{1}, a_{2}, \dots, a_{n}) = gcd (a_{1}, gcd (a_{2}, \dots, a_{n}))$

与最大公因数对应的概念是 最小公倍数，记作 $lcm (a, b)$ 。关于最小公倍数只需记住一个重要结论为

gcd (a, b) \times lcm (a, b) = a b

利用已经学到的关于线性组合与最大公约数的知识，我们将解决两个数论领域的经典问题：

例题一

现有两个无刻度的水桶与无限的水源，容积分别为 $a$ 升与 $b$ 升。允许执行如下操作：

将一个水桶倒满水。
将一个水桶倒空。
将一个水桶中的水倒向另一个水桶，直至该水桶空或另一水桶满。

试判断对于任意的 $c \in (0, min (a, b)]$ ，能否恰好得到 $c$ 升水？若可以，给出操作方法。

解答

显然我们可以建立一个关于水桶中盛水的状态机，其定义在 $N^{2}$ 上，状态机内的状态 $(x, y)$ 代表两个水桶各自的盛水量。

初始状态： $(0, 0)$
转移规则：

装满水桶 A：若 $x < a$ ， $(x, y) \to (a, y)$
装满水桶 B：若 $y < b$ ， $(x, y) \to (x, b)$
倒空水桶 A： $(x, y) \to (0, y)$
倒空水桶 B： $(x, y) \to (x, 0)$
将水桶 A 的水倒入水桶 B：

(x, y) \to {\begin{cases} (0, x + y), & x + y \leq b \\ (x + y - b, b), & otherwise \end{cases}

将水桶 B 的水倒入水桶 A：

(x, y) \to {\begin{cases} (x + y, 0), & x + y \leq a \\ (a, x + y - a), & otherwise \end{cases}

通过观察上面的转移规则，我们可以总结出下面的引理：

每一个水壶内的水量总是两个水壶的容积 $a$ 与 $b$ 的线性组合。

通过证明该引理为保持不变式并利用不变性原理即可得证。对于上述所有转移规则，保持不变性显然，证明此处略去。

随后依据裴蜀定理的推论，可以得出结论：可以通过上述操作得到 $c$ 升水，当且仅当 $gcd (a, b) ∣ c$ 。

利用粉碎机，我们可以得到目标水量 $c$ 对应的 $a$ 与 $b$ 的线性表示。对于线性表示的系数 $s$ 与 $t$ ，可以认为系数为正代表“操作过程中一共将对应的水桶从空装满的次数”，而为负代表“操作过程中一共将对应的水桶从满倒空的次数”，这一线性组合就生动表现了接入的水量与倒去的水量之差，也就是留在水桶中的总水量。因此我们的操作方法呼之欲出，为了方便叙述，下面我们假设 $s > 0$ 而 $t \leq 0$ （可以通过上面给出的变换方法更改系数的正负性）：

装满水桶 A。
将水桶 A 的水倒入水桶 B。若水桶 B 满，倒空水桶 B，重复这一步。若水桶 A 空，返回第一步。

反复重复这一过程，依据上面的推导，当水桶 B 中的水恰好为目标的水量时，我们一定恰好执行了 $| s |$ 次步骤一，并倒空了水桶 B $| t |$ 次。在实际操作时，我们根本不需要在意我们执行了该步骤多少次。

例题二

现有点数为 $a$ 与 $b$ 的牌若干，且 $gcd (a, b) = 1$ 。试问是否存在一些无法由这些牌凑出的点数？

质数（Prime） 是大于 $1$ 且只能被 $1$ 与本身组成的数。其余的数称作 合数（Composite）。质数是数论的核心概念之一，现代数学有许多关于质数的未解之谜。质数在整数中的密度有着明确上界，且在逐渐减小。质数定理 表明，所有小于 $n$ 的质数个数 $π (n)$ 满足

lim_{n \to \infty} \frac{π (n)}{\frac{n}{\ln n}} = 1

质数的分布

几千年来数学家都希望找到一个能够精确刻画质数分布的定理，但至今仍未实现。尽管如此，人们还是发现了一些虽然不精确但是十分常用的质数分布定理。例如：

切比雪夫质数定理： $\forall n > 1,$
$π (n) > \frac{n}{3 \ln n}$

伯特兰-切比雪夫定理：对 $\forall n > 3$ ，必然存在一质数 $p$ 满足 $n < p < 2 n - 2$ 。

数论领域有一个重要的定理为 唯一分解定理（Unique Factorization Theorem）：

每个不为 $1$ 的正整数都是一个唯一的弱递减质数序列的乘积。^[3]

证明

我们需要证明两个引理：

引理一：每个不为 $1$ 的正整数都可以表示为一列质数的乘积。
引理二：设 $p$ 是质数，若 $p ∣ \prod a_{i}$ ，则 $\exists a_{i} . p ∣ a_{i}$ 。

引理一证明

使用强归纳法证明。

归纳假设 $P (n)$ ： $\forall n \in N_{+}, n \geq 2$ ， $n$ 是一列质数序列的乘积。

基本情况： $2$ 可以表示为仅包含自身的质数序列乘积。

归纳步骤：假设对 $\forall k \in [2, n)$ ， $P (k)$ 为真，欲证明 $P (n)$ 成立，分为两种情况：

$n$ 是质数，则可以简单表示为仅包含自身的质数序列乘积。
$n$ 是合数，设 $n = a \times b$ ，由于 $a, b < n$ ， $P (a)$ 与 $P (b)$ 为真，可表示为 $a = \prod p_{i}$ ， $b = \prod q_{i}$ ， $p_{i}$ 与 $q_{i}$ 均为质数。则 $n = \prod p_{i} q_{i}$ ，是一列质数序列的乘积。

故 $P (n)$ 得证，依据归纳法原引理得证。

引理二证明

此处只证明该引理的一个简单版本：设 $p$ 是质数，若 $p ∣ a b$ ，则 $p ∣ a$ 与 $p ∣ b$ 至少有一条成立。该简化命题可利用归纳法自然推广至引理二。

该引理证明分两种情况：

若 $gcd (a, p) = p$ ，依据质数的定义显然 $p ∣ a$ 。
若 $gcd (a, p) \neq p$ ，依据质数的定义显然 $gcd (a, p) = 1$ 。依据裴蜀定理，存在 $s$ 与 $t$ 满足 $s a + t p = 1$ 。等式两边同乘 $b$ 得到 $s (a b) + (b t) p = b$ ，故 $b$ 是 $a b$ 与 $p$ 的线性组合。由于 $p ∣ a b$ 且 $p ∣ p$ ，依据整除的性质， $p ∣ b$ 。

引理一得证后，我们只需证明该质数序列在不考虑次序的情况下唯一。

考虑基于良序原理的反证法：设存在由一些存在不止一种弱递减的质数序列乘积正整数组成的集合。基于良序原理，设 $n$ 为该集合中最小的整数，基于我们的假设，将其表示为

n = p_{1} p_{2} \dots = q_{1} q_{2} \dots

其中 $p_{1}, p_{2}, \dots$ 与 $q_{1}, q_{2}, \dots$ 均为一系列弱递减的质数，且 $p_{1} \leq q_{1}$ 。

若 $p_{1} < q_{1}$ ，则对任意 $p_{i}$ 都有 $p_{i} < q_{1}$ 。与此同时，因为 $q_{1} ∣ n$ 即 $q_{1} ∣ p_{1} p_{2} \dots$ ，依据引理二，存在 $p_{i}$ 使得 $q_{1} ∣ p_{i}$ ，与前述的 $p_{i} < q_{1}$ 矛盾，故该情况不成立。

若 $p_{1} = q_{1}$ ，则考虑 $\frac{n}{p_{1}} = p_{2} p_{3} \dots = q_{2} q_{3} \dots$ ，即 $\frac{n}{p_{1}}$ 存在不止一种弱递减的质数序列乘积，但 $\frac{n}{p_{1}} < n$ ，与 $n$ 为该集合中最小的整数矛盾，故该情况不成立。

综合两种情况，假设不成立，不存在有不止一种弱递减的质数序列乘积的正整数，唯一分解定理得证。

我们称 $a$ 与 $b$ 模 $n$ 同余，当且仅 $n ∣ (a - b)$ ，记作 $a \equiv b (\mod n)$ 。根据同余的字面意思，很容易得出一个等价定义： $a \equiv b (\mod n)$ 当且仅当 $rem (a, n) = rem (b, n)$ 。证明此处略去。

基于同余的定义，很容易得到同余关系与定义在 $Z$ 上的相等关系具有相同的性质，具体而言，它们都是等价关系。即具有：

自反性： $a \equiv a (\mod n)$
对称性： $a \equiv b (\mod n)$ 当且仅当 $b \equiv a (\mod n)$
传递性：若 $a \equiv b (\mod n)$ 且 $b \equiv c (\mod n)$ ，则 $a \equiv c (\mod n)$

以及一条很重要的推论：

a \equiv rem (a, n) (\mod n)

基于这点，我们可以这样看待模 $n$ 同余：它定义了一种将 $Z$ 划分为 $n$ 个集合的方式，这 $n$ 个集合叫做 同余类 或 剩余类^[4]。可以证明同余运算与普通的代数运算十分相似，许多在普通代数运算中成立的性质在同余运算中同样满足。例如：

若 $a \equiv b (\mod n)$ 且 $c \equiv d (\mod n)$ ，则 $a + c \equiv b + d (\mod n)$ ，且 $a c \equiv b d (\mod n)$ 。

这表明，为了计算一些大数加减乘之后模 $n$ 的值，可以考虑直接先将乘数与加数模 $n$ ，中间的运算结果一旦大于 $n$ 之后也立刻模 $n$ ，从而降低了计算难度。

更确切地说，所有 $[0, n)$ 内的整数与定义在该集合上的两种运算 $+_{n}$ 与 $\times_{n}$ ^[5]构成了 模 $n$ 剩余类环，记作 $Z_{n}$ 。在该系统中，我们所熟知的加法与乘法性质均成立，例如交换律、结合律、乘法对加法的分配律等。^[6]

环

环是一个由元素集合 $S$ 与定义在 $S^{2} \to S$ 上的两个运算 $\oplus$ 与 $\otimes$ 组成的代数系统，且满足：

$(R, \oplus)$ 是 Abel 群，即

零元 $0$ 存在且唯一
每个元素 $a$ 的 加法逆 $- a$ 存在且唯一
$\oplus$ 满足交换律、结合律

$(R, \otimes)$ 是半群，即

$\otimes$ 满足结合律

$\otimes$ 对 $\oplus$ 满足分配律

依据该定义，环具有的一些基本性质举例：

$a \otimes 0 = 0 \otimes a = 0$
$a \otimes (- b) = (- a) \otimes b = - (a \otimes b)$
$(- a) \otimes (- b) = a \otimes b$

有一些特殊的环，其运算具有更多优良性质，如：

$\otimes$ 满足交换律 的环称作 交换环。
$\otimes$ 存在单位元 $1$ 的环称作 含幺环。
不存在零因子的环称作 无零因子环，无零因子环上有乘法消去律成立，即等式两边同除任何非 $0$ 因子后等式仍然成立。
整环是同时为交换环、含幺环、无零因子环且零元与单位元不等的环。
每个非零元 $a$ 都有乘法逆 $a^{- 1}$ 且零元与单位元不等的 含幺环 称作除环。
域是既为交换环又为除环的环。

我们最常见的环就是定义在 $Z$ 上的 整数环，它是最基础的整环，但不是域。其它常见的环如下：

有理数环 $Q$ 、实数环 $R$ 、复数环 $C$ 既是整环也是域。
模 $n$ 剩余系环 $Z_{n}$ 是交换环、幺环，当且仅当 $n$ 为质数时为整环、域，具体见下。
整数多项式环 $Z [x]$ 是整环。

在 $Z_{n}$ 上，所有的同余关系可以直接化为等价关系，因此我们可以直接将上面的性质重新叙述为若 $a = b (Z_{n})$ 且 $c = d (Z_{n})$ ，则 $a + c = b + d (Z_{n})$ 且 $a c = b d (Z_{n})$ 。这与普通的代数运算的性质别无二致，因此我们在计算大数的加减乘后求余运算时可以自由地将某些大于 $n$ 的数模 $n$ 化为较小的数，并利用在一般代数运算中的简便方法，同时不影响计算结果。

然而，同余运算与普通的代数运算在一点上存在显著差异：求逆与约去。我们定义一个数 $x$ 的 乘法逆 $x^{- 1}$ 满足 $x \times x^{- 1} = 1$ 。下文将简称乘法逆为倒数。在 $R$ 上，每一个非零实数都有倒数；在 $Z$ 上，仅有 $1$ 与 $- 1$ 有倒数，为各自本身；而在环 $Z_{n}$ 上，判定要稍微复杂一些。

我们称两个整数互质，当且仅当两数没有共同的质约数，等价于 $gcd (a, b) = 1$ 。显然 $0$ 不与任何数互质， $1$ 与任何非自身的数互质。一个数在环上是否存在倒数的判定定理如下：

$k$ 与 $n$ 互质，当且仅当 $k$ 在 $Z_{n}$ 上的倒数存在且唯一。

证明

$\Rightarrow$ ：依据裴蜀定理，由 $gcd (k, n) = 1$ 得存在 $p$ 与 $q$ 使得 $p k + q n = 1$ ，两边对 $n$ 取余得到 $(p % n) k \equiv 1 (\mod n)$ ，这表明 $k$ 的倒数存在且唯一，为 $p mod n$ 。

$\Leftarrow$ ：由 $k^{- 1} \times k \equiv 1 (\mod n)$ ，依据同余的定义， $n ∣ k^{- 1} \times k - 1$ 。依据整除的定义，存在 $s$ 使得 $k^{- 1} \times k - 1 = s n$ ，变形得 $k^{- 1} \times k - s n = 1$ ，即 $1$ 是 $k$ 与 $n$ 的线性组合，依据裴蜀定理推论， $gcd (k, n) ∣ 1$ ，即 $gcd (k, n) = 1$ ，得证。

除此之外，我们通过举例也可以得知我们不能像在普通代数中一样随意约去两个同余数的因数。具体而言，我们称一个数 $k$ 在 $Z_{n}$ 上是 可约的（Cancellable），当且仅当对 $\forall a, b \in [0, n)$ ，

k a \equiv k b (\mod n) \to a \equiv b (\mod n)

可约的判定定理为：

$k$ 在 $Z_{n}$ 上是可约的，当且仅当 $k$ 在 $Z_{n}$ 上的倒数存在。

该结论是显然的，约去 $k$ 等同于等式两边同乘其乘法逆。总而言之， $k$ 是可约的， $k$ 的倒数存在， $k$ 与 $n$ 互质三条性质是互相等价的。我们记在 $Z_{n}$ 上与 $n$ 互质的数组成集合 $Z_{n}^{*}$ 。在实际运算中，我们希望 $n$ 为质数，这能减少很多不必要的麻烦，因为显然此时 $Z_{n}^{*} = Z_{n}$ ，每一个环内的整数都有逆元。

欧拉 $ϕ$ 函数 被定义为计算所有小于 $n$ 且与 $n$ 互质的非负整数个数^[7]，即

$ϕ (n) \equiv [0, n)$ 中与 $n$ 互质的数的个数

显然 $ϕ (n) = | Z_{n}^{*} |$ 。设 $p$ 是质数， $ϕ (p) = p - 1$ 。此外，对于 $ϕ (p^{k})$ ，由于每 $p$ 个数就有 $1$ 个数不与 $p$ 互质（ $p$ 的倍数），其余数均与 $p$ 互质，容易得到 $ϕ (p^{k}) = p^{k} - p^{k - 1}$ 。

欧拉函数是 积性函数，即对于任意互质的数 $a$ ， $b$ ，有 $ϕ (a b) = ϕ (a) ϕ (b)$ 。

为了证明该性质，我们需要首先介绍介绍另一条定理——中国剩余定理：

若 $m$ ， $n$ 互质且大于 $1$ ，则对任意 $a$ ， $b$ ，存在 $x$ 是该线性同余方程组的解：
${\begin{cases} x \equiv a (\mod m) \\ x \equiv b (\mod n) \end{cases}$
且该解在模 $m n$ 意义下唯一。

更一般的形式是，设 $m_{1}, m_{2}, \dots, m_{k}$ 是一列大于 $1$ 且两两互质，令 $p = \prod_{i} m_{i}$ ，则对任意整数列 $a_{1}, a_{2}, \dots, a_{k}$ ，存在 $x$ 是该线性同余方程组的解：
${\begin{cases} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{k} (\mod m_{k}) \end{cases}$
且该解在模 $p$ 意义下唯一。该解的构造方法如下：

另构造出一列数 $s_{1}, s_{2}, \dots, s_{k}$ ，其中 $s_{i} = \frac{p}{m_{i}}$ ，与这列数各自在 $Z_{m_{i}}$ 上的倒数 $t_{i}$ 。方程组的解
$x = \sum_{i} a_{i} s_{i} t_{i} (Z_{p})$

中国剩余定理证明

Todo

欧拉函数是积性函数证明

Todo

积性函数的事实允许我们以相当简单的方法计算任何数的欧拉函数值。进一步地，搭配上唯一分解定理，我们可以得到欧拉函数的计算方法：

对任意整数 $n$ ，设 $p_{1}, p_{2}, \dots$ 是 $n$ 的所有互异的质约数
$ϕ (n) = n \prod_{i} (1 - \frac{1}{p_{i}})$

证明

依据唯一分解定理， $n = \prod_{i} p_{i}^{α_{i}}$ ，其中 $p_{i}$ 为 $n$ 的质约数。则

\begin{aligned} ϕ (n) = & ϕ (\prod_{i} p_{i}^{α_{i}}) \\ = & \prod_{i} ϕ (p_{i}^{α_{i}}) \\ = & \prod_{i} (p_{i}^{α_{i}} - p_{i}^{α_{i} - 1}) \\ = & \prod_{i} p_{i}^{α_{i}} (1 - \frac{1}{p_{i}}) \\ = & n \prod_{i} (1 - \frac{1}{p_{i}}) \end{aligned}

还有一种基于计数规则的证明，会在 15. 基数法则与组合数学初步中给出。

$ϕ$ 函数与 欧拉定理 紧密相关，欧拉定理的内容为：

若 $n$ 与 $k$ 互质，则 $k^{ϕ (n)} \equiv 1 (\mod n)$

证明

我们需要两个引理：

引理一： $x, y \in Z_{n}^{*}$ ，当且仅当 $x \times_{n} y \in Z_{n}^{*}$ 。
引理二：若 $k \in Z_{n}^{*}$ ， $S \subseteq Z_{n}$ 。我们定义集合 $k S \equiv {k \times_{n} s ∣ s \in S}$ ，则 $| k S | = | S |$ 。即 $Z_{n}^{*}$ 中元素对 $Z_{n}$ 的乘法是封闭的。

证明不难，具体过程此处略去。直接应用最大公约数的性质可以证明引理一；应用同余运算上乘法的性质可以直接证明引理二。

从这两个引理可以得到推论：若 $k \in Z_{n}^{*}$ ，则 $k Z_{n}^{*} = Z_{n}^{*}$ ，

从该推论出发，我们考虑将左右两集合的所有元素相乘从而构建一个等式：

\prod_{e \in Z_{n}^{*}} e = \prod_{e \in Z_{n}^{*}} k e = k^{ϕ (n)} \prod_{e \in Z_{n}^{*}} e (Z_{n})

依据引理一， $Z_{n}^{*}$ 中所有元素相乘后后得到的数仍然是可约的，将其约去即可得到欧拉定理

k^{ϕ (n)} = 1 (Z_{n})

该定理解决了任意模数下任意大指数的幂的计算问题，并可以引申出大量推论，例如 费马小定理：

设 $p$ 是质数且 $p ∤ k$ ，则 $k^{p - 1} \equiv 1 (\mod p)$ ，或可等价为 $k^{p} \equiv k (\mod p)$

费马小定理给出了当模数为质数时一种简便的求环 $Z_{p}$ 上每个数的倒数的方法，即计算 $k^{p - 2} mod p$ 。

然而，欧拉定理仍然要求底数与模数互质，存在一定使用限制。我们可以考虑将其推广到底数与指数不互质的情形，从而处理任意模数下任意底数的幂次计算问题。先给出推论内容：

对任意 $a$ 与 $n$ ，有
$a^{k} \equiv {\begin{cases} a^{k}, & k < ϕ (n), \\ a^{rem (k, ϕ (n)) + ϕ (n)}, & k \geq ϕ (n), \end{cases} (\mod n)$

证明

$k < ϕ (n)$ 的情况显然，我们着重证明 $k \geq ϕ (n)$ 的情况：

从该推论出发很容易得到一条比较简单的推论：

对任意 $a$ 与 $n$ ，有 $a^{n} \equiv a^{n - ϕ (n)} (\mod n)$ 。

基于所学的数论知识，我们将分析数论的一大重要应用——密码学，具体来说，我们将研究 RSA 加密系统：

RSA 加密系统是一种典型的 非对称 加密算法。其最大优势在于，在正式通信前，消息的接收方与发送方不必提前接触以提前对密钥作出约定，发送方仅需接收方所发布的公开信息就可以向接收方发送只有接收方可以解密的加密消息。做到这点依赖于被称作 单向陷门函数 (Trapdoor One-way Function) 的技术。这类函数就如同计算上的“二极管”一样，已知函数输入很容易得到输出，但从输出倒推输入是十分困难甚至是不可能的。具体到 RSA 上，它使用大质数的乘积与因式分解作为“二极管”，这基于如下猜想：

低效分解猜想：给定两个大质数的乘积 $n = p q$ ，不存在多项式时间内求解 $p$ 与 $q$ 的算法。

目前已经能够证实我们可以以 $O (n)$ 的时间复杂度将大质数的因式分解规约到大名鼎鼎的 NP 问题：SAT 问题上，因此低效分解猜想，本质上就是计算领域的著名问题——“P ?= NP"，该问题至今仍未有明确答案。规约的过程简要说明如下：考虑设计一个简单的乘法检查器，其由具有 $4 k$ 位输入与 $1$ 位输出，内部由具有 $2 k$ 位输出的乘法器与 $2 k$ 位输入， $1$ 位输出的检查器连接组成，其中 $k$ 为 $p$ 与 $q$ 的二进制表示的位数。我们向乘法器分别输入 $x$ 与 $y$ ，向检查器输入 $n = p q$ ，该电路会检查 $n = x y$ 是否成立，并输出对应信号。由于数字电路可以被形式化为命题公式，我们取该电路的命题公式做 $k$ 轮 SAT 测试，在第 $i$ 轮中，将乘法器中输入 $x$ 的第 $i$ 位固定为 $1$ ，输入欲分解的数 $n$ ，并测试在该情况下该命题公式能否满足，测试结果无论如何都能确定该位的具体值，在 $k$ 轮 SAT 测试后，其中一个因数就能够分解出来，从而因式分解 $n$ 位大数就被规约到了 $O (n)$ 次 SAT 测试上。

我们接下来详细讲一下 RSA 的工作流程：

通信开始前，信息的接收方需要创建两个密钥，一个为本地保密的私钥，另一个为公开的公钥。公钥与私钥通过如下流程生成：

通过具有高随机性的算法生成两个大质数 $p$ 与 $q$ ，通常有数百位长。
计算 $N = p q$ 。
选择一个同样大的整数 $e$ ，且 $gcd (e, ϕ (N)) = 1$ 。显然 $ϕ (N) = (p - 1) (q - 1)$ 。二元组 $(e, N)$ 即为公钥，可以对外公开发布。
求 $e$ 在 $Z_{ϕ (N)}$ 上的倒数 $d$ ，为私钥，秘密保存。

发送方获取到公钥后，可以将其用于加密将要发送的信息。设 $m \in [0, N)$ 为明文，加密方使用公钥加密该消息，得到密文

\hat{m} = m^{e} (Z_{N})

发送给接收方。

接收方接收到消息后，使用私钥解密该消息，得到明文

m = {\hat{m}}^{d} (Z_{N})

我们首先证明该加解密方案是有效的，即假设传输无错时，接收方总能解密出发送方希望发送的原文，也即我们想要证明，对不等的两个质数 $p$ 与 $q$ ，设 $N = p q$ ， $d e \equiv 1 (\mod ϕ (N))$ ，对任意 $m \in [0, N)$ ，

(m^{e})^{d} \equiv m (\mod N)

证明

从实用角度来说， $m$ 与 $N$ 必然互质。因为若不是这样，我们会自然意识到 $gcd (m, N)$ 一定为 $p$ 或 $q$ ，从而破解掉密文。然而由于 $p$ 与 $q$ 为质数且相当大，其倍数的分布相当稀疏，因此 $m$ 与 $N$ 不互质的概率微乎其微。不过后面仍然会证明即使去掉互质条件上面的性质依然成立（尽管这个性质对于 RSA 本身没有意义）。

先考虑 $m$ 与 $N$ 互质这一简单的情况，直接套用欧拉定理有

m^{d e} = m^{d e mod ϕ (N)} = m (Z_{N})

接着考虑 $m$ 与 $N$ 不互质的情况

该时间复杂度的严格证明见 14. 求和与渐进分析初步。 ↩︎
更形式化的表述是，谓词 $P ((x, y)) \equiv [gcd (x, y) = gcd (a, b)]$ 是一个保持不变式，其中 $(a, b)$ 为起始状态。 ↩︎
对于 $1$ ，我们认为它是空序列的乘积。 ↩︎
关于剩余系的具体概念不在本课程要讨论的范围内，请参考初等数论教材。 ↩︎
$i +_{n} j \equiv rem (i + j, n)$ ， $i \times_{n} j \equiv rem (i j, n)$ ↩︎
关于群、环的具体概念不在本课程要讨论的范围内，请参考抽象代数教材。 ↩︎
由于 $0$ 不与任何数互质， $ϕ$ 也可等价定义为与 $n$ 互质的正整数个数。 $ϕ (0)$ 一般无定义。 ↩︎