【DLC】宝宝你是一个很难学的数论啊啊啊啊啊啊啊

不知不觉时间已经来到了 8 月底，今天是浙江夏季的第三个台风过境的日子，也不知道这篇文章和大伙见面的时间会在什么时候了，希望能尽快吧。

附上和群友面基时留下的照片，超级好人，我哭死。二人一起去看了《龙餐馆》，看预告和网评时以为会是比较红色比较战狼的片子，看完了感觉是比较纯粹的反战片，没有在营销爱国情怀，还是很值得去看的！

那么，这篇文章的主要任务是写一些数论的基础知识，顺带解决上篇文章留下来的疑难杂症，作为本文的最后 BOSS，所以内容会相对较少，我会尽力让文章没那么晦涩难读，准备好的话就开始吧！

对象和运算

数论的研究对象还是有必要强调一下的，那就是整数，经过再三考虑，本文决定将关于整数的严谨定义省去，我们用下面的非常偷工减料的方式定义整数：

Definition

形如 $\cdots, -2, -1, 0, 1, 2, \cdots$ 的数，我们称为整数。

余数

类似地，我们直接跳过整数之间关于加减乘运算的定义，相信接下来的内容不会因为缺失了严谨性导致读者朋友们理解困难🥰

Definition

对于可以写成

$$am + r = x\qquad 0\le r < m$$

的形式，我们称带余除法 $x$ 除以 $m$ 等于 $a$，余 $r$。若 $r = 0$，就称 $m$ 整除 $x$，记作 $m \mid x$。

上面的式子中 $r$ 便是余数，为了方便地表示 $r$ 是 $x$ 除以 $m$ 情况下的余数，我们称 $x$ 对 $m$ 取模为 $r$，写作 $x \bmod m = r$，这样，$m$ 就可以称为取模时的模数。

那么，为什么要叫作“模”呢？

考据认为“模”来自于 modulo 的音译，modulo 可来自于高斯的《算术研究》（Disquisitiones Arithmeticae）中，全文使用拉丁语写作。原文为 $a \equiv b \textbf{ modulo } m$，modus 在拉丁语中是名词，代表尺度、度量、规格、循环单位；modulus 是 modus 的指小词，代表小度量单位、标尺；modulo 是 modulus 的夺格（ablative），可以表达以……为尺度，即以 $m$ 这个标尺去衡量、去做等价判断。回过头来，“模” 本义也可以有模具的意思，即标尺、范本等，所以模可以是一个很信达雅的翻译🥰

关于模运算

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

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

也就是说，取模运算的结果取决于除法运算的结果，至于除法运算的结果如何规定，则是由编译器决定。从 C99 和 C++11 标准版本起，规定 商向零取整（舍弃小数部分），取模的结果就与被除数保持同样的正负性。以下断言保证为真：

assert(5 % 3 == 2);
assert(5 % -3 == 2);
assert(-5 % 3 == -2);
assert(-5 % -3 == -2);

因此在编程语言中，余数可能会是负数。但是在数论中，我们一般规定余数 $0 \le r < \left | b\right |$，下文同样会默认这一点。

当某个整数对一堆互质的整数取模的余数均为 $0$ 时，还有一个有趣的性质：

互质即最大公约数为 $1$，至于什么是最大公约数，请见下文。

若 $n_1,n_2,\dots,n_k$ 两两互质，$n_1\mid A,\ n_2\mid A,\ \dots,\ n_k\mid A$，则 $n_1n_2 \cdots n_k \mid A$，此处不作证明🥰

同余

认真阅读本文的朋友们不难发现我们提前提到了 $a \equiv b \pmod m$，那么这个 $\equiv$ 是什么意思呢？

Definition

设整数 $m\ne0$．若 $(a-b) \bmod m = 0$，称 $m$ 为 模数（模），$a$ 同余于 $b$ 模 $m$。记作 $a\equiv b\pmod m$。

否则，$a$ 不同余于 $b$ 模 $m$。记作 $a\not\equiv b\pmod m$。

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

简单来说，同余即 同一个剩余，$a$ 和 $b$ 同余就是在说用 $m$ 这个标尺去衡量$a$ 和 $b$，它们多余的部分是相同的。

既然同余这个符号长得和等于号辣么像，那么它是否满足一些优秀的性质呢？答案是当然满足，它拥有自反性、对称性、传递性，而且支持做线性运算！

• $a\equiv a\pmod m$.
• 若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$
• 若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$
• 若 $a, b, c, d \in \mathbb{Z}, m \in \mathbb{N}^*, a \equiv b \pmod m,c \equiv d \pmod m$，则 $a \pm c \equiv b \pm d \pmod m$ 且 $a \cdot c \equiv b \cdot d \pmod m$

除了上面的四条性质，本文的证明内容还需要用到一个特别的性质：若 $a \equiv b \pmod m$，$m \equiv 0 \pmod c$，则 $a\equiv b\pmod c$。

这条性质要怎么证明呢？首先，从定义出发，$a \equiv b\pmod m$ 就代表 $(a - b) \bmod m = 0$，就代表 $a - b = q \cdot m$，$q$ 是整数。接下来，$m \equiv 0 \pmod c$ 就代表 $m = k \cdot c$，$k$ 是整数。

将该式代入到 $a - b = q \cdot m$ 中即可得到 $a - b = q \cdot k \cdot c$，即 $a - b = (qk) \cdot c$，所以 $a\equiv b\pmod c$。

模算术

模算术就是在某一模数下的各种整数运算，包括但不限于加减乘除，其中乘法就有在上篇文章中我们简单涉略的乘法逆元部分。模算术中的一些基本性质是这样的：

• 加法：$(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$，也可写成 $a + b \equiv a \bmod m + b \bmod m \pmod m$
• 乘法：$ab \bmod m = (a \bmod m)(b \bmod m) \bmod m$，也可写成 $ab \equiv (a \bmod m)(b \bmod m) \pmod m$

从以上性质可以推论出，对于一个拥有加减乘运算的复杂表达式，若结果需要对 $m$ 取模，我们可以任意地在中间过程对 $m$ 取模，只要保证最后会有一次取模运算，就不会影响结果。

若表达式中有除法

上述结论只针对加减乘运算有效，若表达式中有除法，前提是求出除数对 $m$ 的逆元，若逆元存在，将除以 $x$ 换成乘以 $x^{-1}$ 即可。

在了解了这个基本性质以后我们就可以做很多事情了，还记得在小学的时候老师教了我一个快速判断一个数是不是 3 或者 9 的倍数的方式，那就是把这个数的每一位的数字相加后计算是不是 3 或者 9 的倍数！当时我还是把这个方式当作一个工具去使用，并没有纠结背后的原理，既然今天了解了这么多的数论知识了，那就试试证明一下这个工具吧！

Problem

若十进制整数 $x$ 的各位数字相加的结果是 $3$ 的倍数，那么 $x$ 就是 $3$ 的倍数，否则不是。
若十进制整数 $x$ 的各位数字相加的结果是 $9$ 的倍数，那么 $x$ 就是 $9$ 的倍数，否则不是。

首先，我们将 $x$ 按位分解，我们用 $i$ 表示从低到高第几位，$a_i$ 就是对应位上的数字，设 $x$ 共有 $n$ 位，那么 $x=\sum \limits_{i=0}^{n-1}a_i \times 10^{i}$。我们先证明第一条，令这个式子对 $3$ 取模，即 $(\sum \limits_{i=0}^{n-1}a_i \times 10^{i}) \bmod 3$，这样我们就可以任意地在过程中对 $3$ 取模而不影响结果。令 $(\sum \limits_{i=0}^{n-1}a_i \times 10^{i}) \bmod 3$ 写成 $(\sum \limits_{i=0}^{n-1}a_i \times (10^{i} \bmod 3)) \bmod 3$。

接下来，由于 $1$ 对 $3$ 取模结果为 $1$，$10$ 对 $3$ 取模结果也为 $1$。要求 $10^2$ 对 $3$ 取模，我们可以将其写成 $10 \times 10$，接下来就可以对其中间过程任意取模，其结果为 $1 \times 1$，最后对 $3$ 取模结果为 $1$。然后，根据数学归纳法，$10^2, 10^3, \dots , 10^n$ 对 $3$ 取模结果都为 $1$。

于是 $(\sum \limits_{i=0}^{n-1}a_i \times (10^{i} \bmod 3)) \bmod 3$ 就变成了 $(\sum \limits_{i=0}^{n-1}a_i) \bmod 3$，这恰好就是将各位数字相加的形式，于是我们得出了十进制整数 $x$ 的各位数字相加的结果是 $3$ 的倍数和 $x$ 是 $3$ 的倍数是等价的结论。即 $\sum \limits_{i=0}^{n-1}a_i \equiv \sum \limits_{i=0}^{n-1}a_i \times 10^{i} \pmod 3$。

同理，我们也可以证出 $\sum \limits_{i=0}^{n-1}a_i \equiv \sum \limits_{i=0}^{n-1}a_i \times 10^{i} \pmod 9$。

顺带地，我们还可以快速地举出在其他进制下，求特定整数的倍数的方式。例如，在八进制下，若某数的各位数字相加结果为 $7$ 的倍数，那么这个数就是 $7$ 的倍数。

一元线性同余方程

设 $a, b, m$ 为整数，$x$ 为未知数，那么，形如

$$ax\equiv b\pmod m$$

的方程称为 一元线性同余方程。

逆元

因为同余是可以做线性运算的，所以我们不难想到，要求解上面的线性同余方程，可以假设存在一个 $a^{-1}$ 使 $a^{-1} \cdot a \equiv 1 \pmod m$。令方程两边同时乘以 $a^{-1}$，就可以得到方程的解：$x \equiv ba^{-1} \pmod m$。

关于解的存在性和解的数量的证明，本文就不深入讨论了，毕竟本文主打一个轻量化。

那么求解单个线性同余方程的难点就在于求逆元了，不难发现求逆元本身其实也是一个线性同余方程，即求 $ax' \equiv 1 \pmod m$。

需要说明的是，逆元存在的 充要条件 是 $\gcd(a, m) = 1$，该结论的证明过于繁琐，本文会直接利用这个结论，下文若无特别说明，都会默认 $\gcd(a, m) = 1$。

这个方程看上去似乎要简单很多，让我们试试求解吧。在正式开始前，我们还要先引入 欧几里得算法，欧几里得算法是一个求解 最大公约数 的算法，已了解的朋友们可以直接跳到拓展欧几里得部分。

欧几里得

最大公约数即为 Greatest Common Divisor，缩写为 gcd。如果我们已知两个数 $a$ 和 $b$，如何求出二者的 gcd 呢？

不妨设 $a > b$，如果 $b$ 是 $a$ 的约数，那么 $b$ 就是二者的最大公约数。所以下面讨论不能整除的情况，即设 $a = b \times k + r$，其中 $r < b$，即 $r = a \bmod b$。

设 $d \mid a,~d \mid b$，即 $d$ 是 $a$ 和 $b$ 的一个公约数。

则 $r = a - b \times k$，$\frac{r}{d}=\frac{a}{d} - \frac{b}{d}k$。

由右边的式子可知 $\frac{r}{d}$ 是一个整数，即 $d$ 是 $r$ 的一个约数，而 $r = a \bmod b$。

也就是说，对于 $a$、$b$ 的公约数，它也会是 $b$、$a \bmod b$ 的公约数。

既然公约数都是相同的，那么最大公约数也肯定相同，所以我们得到了式子 $\gcd(a, b) = \gcd(b, r) = \gcd(b, a \bmod b)$。

将 $\gcd(a, b) = \gcd(b, r)$ 这个过程递归，$a$ 会被赋值成一个小于 $a$ 的数 $b$，$b$ 会被赋值成一个小于 $b$ 的数 $a \bmod b$，并且在下一轮的递归中，函数的第一个参数同样比第二个参数大。通过数学归纳法可以预见的是，每递归一层，函数的两个参数都严格小于上一层，那么递归的终点在哪里呢？

让我们关注较小的第二个参数，这里统一用 $b_k$ 表示递归第 $k$ 轮的第二个参数。已知 $b_0>b_1>b_2>\dots \ge 0$，每一个 $b_k$ 至少比前一个小 $1$，即至多递归 $b_0$ 次，$b_{b_0}$ 会等于 $0$。确定了递归的终点就好办很多了，由于 $0$ 能整除任何数，所以对于 $b_n = 0$，$\gcd(a, b) = \gcd(b_{n - 1}, b_n) = \gcd(b_{n - 1}, 0) = b_{n - 1}$。

那么我们也就得到了关于两个数的最大公约数的一个递归求法，这个算法就是 欧几里得算法。

欧几里得的递归代码模板如下：

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

欧几里得的递推代码模板如下：

int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

欧几里得算法的时间复杂度

欧几里得算法的时间效率如何呢？是否真的会出现需要迭代 $b_{b_0}$ 的情况？实际上这种情况非常少见，欧几里得的时间复杂度是 $O(\log⁡\max(a,b))$，并且当我们用欧几里得算法去求斐波那契数列相邻两项的最大公约数时，会让该算法达到最坏复杂度，具体证明留给感兴趣的朋友们🥰

拓展欧几里得

问题回到解决 $ax' \equiv 1 \pmod m$ 上，有没有觉得这个同余符号很不顺眼呢？没关系，我们把它去掉就好，$ax' \equiv 1 \pmod m$ 和 $ax' + my' = 1$ 其实是等价的写法，其中，$y$ 是整数。

接下来，由于我们要求的是 $a$ 的逆元，根据逆元存在的充要条件 $\gcd(a, m) = 1$，我们可以直接改写该方程为 $ax' + my' = \gcd(a, m)$。为了更方便地读懂下文，我们还需要忘记 $\gcd(a, m) = 1$ 这个已知的事实，只关注 $ax' + my' = \gcd(a, m)$ 方程本身。

这个方程要怎么解呢？唉，既然本节的标题是拓展欧几里得，那就试试和上一节的内容联动一下吧！有没有觉得这个 $\gcd(a, m)$ 很欠揍？不如试试利用上一节的小结论 $\gcd(a, m) = \gcd(m, a \bmod m)$ 吧！

怎么利用呢？我们可以把方程 $ax' + my' = \gcd(a, m)$ 写成

$$ax_1 + my_1 = \gcd(a, m) \tag{1}$$

我们要求的就是满足上面方程的一对 $(x_1, y_1)$ 的解。接下来，我们再设一个新的方程

$$mx_2 + (a \bmod m)y_2 = \gcd(m, a \bmod m) \tag{2}$$

显然两个方程的右式是相等的，合并左式可以得到：

$$ax_1 + my_1 = mx_2 + (a \bmod m)y_2 \tag{3}$$

回顾模运算的定义，$a \bmod m$ 实际上就是用 $m$ 来分 $a$ 时多出来的那一部分，假设 $a$ 能分出来 $q$ 份 $m$，即 $a = qm + a \bmod m$，那么 $a \bmod m$ 就可以写成 $a - qm$，将其带入到 $(3)$ 式可得：

$$ax_1 + my_1 = mx_2 + (a - qm)y_2 \tag{4}$$

接下来，展开：

$$ax_1 + my_1 = mx_2 + ay_2 - qmy_2 \tag{5}$$

移项：

$$ax_1 + my_1 = ay_2 + mx_2 - qmy_2 \tag{6}$$

合并：

$$ax_1 + my_1 = ay_2 + m(x_2 - qy_2) \tag{7}$$

为了更方便观察，我们将 $a, m$ 的位置换一下：

$$x_1 \boldsymbol {a} + y_1 \boldsymbol {m} = y_2 \boldsymbol {a} + (x_2 - qy_2) \boldsymbol {m} \tag{8}$$

观察 $(8)$ 式左右两边 $a, m$ 的系数，不难得出：

$$\begin{cases} x_1 = y_2\\ y_1 = x_2 - qy_2 \end{cases}$$

若我们知道 $x_2, y_2$ 的值，就可以轻易地使用上式求出 $x_1, y_1$，所以问题就变成了求解方程 $mx_2 + (a \bmod m)y_2 = \gcd(m, a \bmod m)$，那要怎么解这个方程呢？唉~要不再试试继续设方程？

后面的步骤就是不断地按照欧几里得算法的递归形式去设立方程了，不难发现，一直递归地去设立新方程，我们最终会来到 $\gcd$ 函数中第二个参数为 $0$ 的递归边界，到了这里我们就可以恢复先前遗忘的记忆了！由于 $\gcd(a, m) = 1$，所以当第二个参数为 $0$ 时，要令 $\gcd$ 为 $1$，函数的第一个参数只能为 $1$，所以方程的右式一定是：

$$\gcd(1, 0)$$

假设这是设立的第 $n$ 个方程，该方程的形式就是：

$$1 \cdot x_n + 0 \cdot y_n = \gcd(1, 0) = 1 \tag{9}$$

取 $x_n = 1$ 就可以得到这个方程的通解，为了后续计算的方便，我们可以取 $y_n = 0$，这同样是一组解，之后沿着递归栈一路向上还原出 $x_1$，$y_1$ 即可。

推导完成，算法实现方面，在欧几里得的过程中加入 $x$，$y$ 即是拓展欧几里得：

// 求 gcd(a, m)，并顺便求出 ax + my = gcd(a, m) 的一组解
int exgcd(int a, int m, int &x, int &y) {
  if (m == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int _x, _y;            // 下一层 (m, a % m) 的解
  int g = exgcd(m, a % m, _x, _y);
  x = _y;
  y = _x - a / m * _y;
  return g;
}

最后，怎么求线性同余方程呢？对于方程

$$ax\equiv b\pmod m$$

已知解的形式是 $x \equiv ba^{-1} \pmod m$，那么 $x = ba^{-1}$ 必定是一个解（同余的自反性）。我们可以先使用拓展欧几里得求出 $a$ 的逆元，然后计算 $ba^{-1}$ 即可。

int solve(int a, int b, int m) {
  int inverse, y;
  exgcd(a, m, inverse, y);
  return b * inverse;
}

中国剩余定理

Definition

形如

$$\begin{cases} a_1x \equiv b_1 \pmod {m_1} \\ a_2x \equiv b_2 \pmod {m_2} \\ \vdots \\ a_kx \equiv b_k \pmod {m_k} \\ \end{cases}$$

的方程组称为一元线性同余方程组。

What

一元线性同余方程组的求解较为复杂，但是我们有方法可以求解出特别形式的一元线性同余方程组。

被认为出现在南北朝时期的《孙子算经》中，有一道经典问题：

Problem

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

翻译成白话就是在问：一个数 $x$ 模 $3$ 剩 $2$，模 $5$ 剩 $3$，模 $7$ 剩 $2$，这个数是多少？

让我们进一步翻译成现代的数学语言，这个问题实际上就是在求解线性同余方程组：

$$\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}$$

在约 800 年后的宋朝，数学家秦九韶在《数学九章》给出了该类问题的通用解法，由于该解法从中国传入西方国家，因此被西方命名为 Chinese Remainder Theorem，缩写为 CRT，即 中国剩余定理。

Definition

中国剩余定理 可以求解形如

$$\begin{cases} x \equiv y_1 \pmod {m_1} \\ x \equiv y_2 \pmod {m_2} \\ \vdots \\ x \equiv y_k \pmod {m_k} \end{cases}$$

的一元线性同余方程组，其中 $m_1, m_2, \cdots, m_k$ 需要两两互质。

那么该算法是如何求解的呢？明朝数学家程大位在《算法统宗》中给出了单个问题的解答口诀：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

• 三 人同行 七十 希，对应的即是第一个同余方程 $x \equiv 2 \pmod 3$，计算 $70 \times 2 = 140$。
• 五 树梅花 廿一 支，对应的即是第二个同余方程 $x \equiv 3 \pmod 5$，计算 $21 \times 3 = 63$。
• 七 子团圆 正半月，对应的即是第三个同余方程 $x \equiv 2 \pmod 7$，计算 $15 \times 2 = 30$。

最后，除百零五 便得知，将三式相加对 $105$ 取模，即可得到 $(140 + 63 + 30) \bmod 105 = 23$。

CRT 的算法过程描述其实非常简单，首先需要计算所有模数的积 $m = \prod \limits_{i=1}^{k} m_i$，接下来对每个同余方程：

• 计算 $n_i = \frac{m}{m_i}$
• 计算 $n_i$ 在模 $m_i$ 下的逆元 $n_i^{-1}$
• 计算 $q_i = n_in_i^{-1}$（结果不取模）

最后，方程组在模 $m$ 意义下的 唯一解 为：$x = \sum \limits_{i=1}^k y_iq_i \pmod m$。

了解了流程我们就可以知道上节中 $70$、$21$、$15$ 等数字是怎么来的了，当然，光了解还是不够，让我们来证明一下 CRT 试试吧~

How

我们要证明的是使用上面算法得出的 $x$ 对于任意 $i = 1, 2, \cdots, k$ 满足 $x \equiv y_i \pmod {m_i}$。

当 $l \neq r$ 时，有 $n_r = \frac{m}{m_r} = \frac{\prod \limits_{i=1}^{k} m_i}{m_r}$，$\frac{\prod \limits_{i=1}^{k} m_i}{m_r}$ 中必定包含因子 $m_l$，所以 $n_r \bmod m_l = 0$，即 $n_r \equiv 0 \pmod {m_l}$。

因为 $n_rn_r^{-1} \equiv n_rn_r^{-1} \pmod {m_l}$，所以 $q_r \equiv n_rn_r^{-1} \pmod {m_l}$。又因为 $n_r \equiv 0 \pmod {m_l}$，我们得到：

$$\begin{aligned} q_r &\equiv 0 \times n_r^{-1} \pmod {m_l} \\ &\equiv 0 \pmod {m_l} \\ \end{aligned}$$

即：

$$q_r \equiv 0 \pmod {m_l}, l \neq r \tag{1}$$

同时，因为 $n_l^{-1}$ 是 $n_l$ 在模 $m_l$ 下的逆元，所以有：

$$q_l = n_ln_l^{-1} \equiv n_ln_l^{-1} \pmod {m_l} \equiv 1 \pmod {m_l}$$

即：

$$q_l \equiv 1 \pmod {m_l} \tag{2}$$

接下来：

$$x = \sum \limits_{i=1}^k y_iq_i \pmod {m} \equiv \sum \limits_{i=1}^k y_iq_i \pmod {m}$$

由于 $m = \prod \limits_{i=1}^{k} m_i$，所以 $m$ 以 任意 的 $m_i$ 作为模数时，都 同余 $0$。利用 若 $a \equiv b \pmod m$，$m \equiv 0 \pmod c$，则 $a\equiv b\pmod c$ 的性质我们可以得出：

$$\begin{aligned} x&\equiv \sum \limits_{i=1}^k y_iq_i \pmod {m}\\ &\equiv \sum \limits_{i=1}^k y_iq_i \pmod {m_i} \end{aligned}$$

其中 $m_i$ 可任取。接下来：

$$\begin{aligned} x&\equiv \sum \limits_{i=1}^k y_iq_i &\pmod {m_l} \quad & 取m_l作为模数\\ &\equiv y_1q_1 \bmod {m_l} + \cdots + y_kq_k \bmod {m_l} &\pmod {m_l} \quad & 展开，任意加入模运算\\ &\equiv y_lq_l \bmod {m_l} &\pmod {m_l} \quad & (1)式\\ &\equiv y_l &\pmod {m_l} \quad & (2)式 \end{aligned}$$

即对于任意 $i=1,2,\cdots,k$，上面算法得到的 $x$ 总是满足 $x\equiv y_i \pmod{m_i}$，故证明了该算法的正确性。

接下来，假设上述方程组存在两个不同的解 $x_1$ 和 $x_2$，因为 $x_1, x_2$ 均是方程组的解，所以对每一个 $i$ 都有：

$$\begin{cases} x_1 \equiv y_i \pmod{m_i}\\ x_2 \equiv y_i \pmod{m_i} \end{cases}$$

即对于任意的 $i$ 都有 $x_1 \equiv x_2 \pmod {m_i}$，从我们对同余的定义出发，即 $(x_1 - x_2) \bmod m_i = 0$，也就是说 $m_i \mid (x_1 - x_2)$。

前文提到若 $n_1,n_2,\dots,n_k$ 两两互质，$n_1\mid A,\ n_2\mid A,\ \dots,\ n_k\mid A$，则 $n_1n_2 \cdots n_k \mid A$。幸运的是，CRT 适用的情景就是 $m_1, m_2, \cdots, m_k$ 两两互质，所以 $m = m_1m_2 \cdots m_k \mid (x_1 - x_2)$，即 $x_1 \equiv x_2 \pmod m$，故证明了该算法的解是模 $m$ 意义下的唯一解。

CRT 的示例代码如下：

int CRT(int k, int* y, int* m) {
  int M = 1, x = 0;

  for (int i = 1; i <= k; i ++ ) M = M * m[i];

  for (int i = 1; i <= k; i ++ ) {
    int m_ = M / m[i];
    int m_inv_, t_y;

    exgcd(m_, m[i], m_inv_, t_y);  // m_inv_ * m_ mod m[i] = 1

    x += y[i] * m_ * m_inv;
  }
  return x % M;
}

欧拉函数

欧拉函数 $\varphi(n)$，表示 从 1 到 $n$ 的数中，和 $n$ 互质的数的个数。在数论中，若函数 $f(n)$ 满足 $f(1)=1$，且 $f(xy)=f(x)f(y)$ 对任意互质的 $x, y \in\mathbb{N}^*$ 都成立，则称 $f(n)$ 是 积性函数，欧拉函数是一个的积性函数。

如何证明欧拉函数是一个 积性函数 是上一篇文章没能处理好的一个问题，那么废话不多说，首先，设 $x$ 是 $[0, mn - 1]$ 中的一个与 $mn$ 互质的数，即：

$$x \in [0, mn - 1], \gcd(x, mn) = 1$$

设 $x \bmod m = a$，$x \bmod n = b$。不难得出 $a \in [0, m - 1], b \in [0, n - 1]$。

对于 $x \bmod m = a$，设 $d = \gcd(x, m)$，根据最大公约数的定义可知 $d \mid x$ 且 $d \mid m$。

将 $d \mid m$ 写成 $m = q \cdot d$，两边同乘 $n$ 可得 $mn = qn \cdot d$，即 $d \mid mn$。于是 $d$ 同时整除 $x$ 与 $mn$，即 $d$ 是 $x,mn$ 的公约数。由先前的假设可知 $\gcd(x, mn) = 1$，因此 $d = 1$。所以：

$$\gcd(x, m) = d = 1$$

根据欧几里得的公式可知 $\gcd(x, m) = \gcd(m, x \bmod m)$，而 $x \bmod m = a$，所以 $\gcd(x, m) = \gcd(m, a) = \gcd(a, m) = 1$。

即由 $[0, mn - 1]$ 中的一个与 $mn$ 互质的数 $x$ 可以唯一确定一个数 $a = x \bmod m$ 满足 $a \in [0, m - 1]$ 且 $\gcd(a, m) = 1$，同理 $b = x \bmod n$ 也是唯一确定的。

即可建立映射：

$$\begin{aligned} F:\ \mathbb Z_{mn} &\rightarrow \mathbb Z_m \times \mathbb Z_n\\ x &\;\mapsto\; (a, b) \end{aligned}$$

接下来，设任意一对 $(a, b)$，其中 $0 \le a < m$，$0 \le b < n$，且 $\gcd(a, m) = 1$，$\gcd(b, n) = 1$，设线性同余方程组：

$$\begin{cases} x\equiv a \pmod{m}\\ x\equiv b \pmod{n} \end{cases}$$

在上文已经证明，使用 CRT 求解该线性同余方程组，在模 $mn$ 意义下该方程组存在 唯一解 $x$，$x < mn$。对于 $x\equiv a \pmod m$，可知 $x \bmod m = a \bmod m = a$。由 $\gcd(a, m) = 1$ 可知

$$\begin{aligned} \gcd(x, m)&= \gcd(m, x \bmod m) \\ &= \gcd(m, a \bmod m) \\ &= \gcd(a, m) \\ &= 1 \end{aligned}$$

同理可推出 $\gcd(x, n) = 1$。

已知 $\gcd(m, n) = 1$，$\gcd(x, m) = 1$，$\gcd(x, n) = 1$，设 $\gcd(x, mn) = d > 1$，即 $d$ 含素因子 $p > 1$ 满足 $p \mid x$，$p \mid mn$ 且 $p \mid m$ 或 $p \mid n$。

若 $p \mid m$，又因为 $p \mid x$，所以 $\gcd(x, m) \ge p > 1$，与 $\gcd(x, m)=1$ 矛盾。

同理若 $p \mid n$，与 $\gcd(x, n) = 1$ 矛盾。故 $d = 1$，即 $\gcd(x, mn) = 1$。

即由 $[0, m - 1]$ 中的一个与 $m$ 互质的数 $a$ 和由 $[0, n - 1]$ 中的一个与 $n$ 互质的数 $b$ 可以唯一确定一个数 $x$ 满足 $x \in [0, mn - 1]$ 且 $\gcd(x, mn) = 1$。

即可建立映射：

$$\begin{aligned} G:\ \mathbb Z_m \times \mathbb Z_n &\rightarrow \mathbb Z_{mn}\\ (a, b) &\;\mapsto\; x \end{aligned}$$

任取 $x \in \mathbb Z_{mn}$，记 $(a, b) = F(x)$。由 $G$ 的定义，$G(a, b) = t$ 是满足

$$\begin{cases} t\equiv a\pmod{m}\\ t\equiv b\pmod{n}\\ 0 \le t < mn \end{cases}$$

的唯一元。而 $x$ 本身满足该方程组，故 $G(F(x)) = t = x$，即 $G\circ F=\mathrm{id}_{\mathbb Z_{mn}}$。

任取 $(a,b)\in\mathbb Z_m\times\mathbb Z_n$，令 $x = G(a,b)$。根据

$$\begin{cases} x\equiv a \pmod{m}\\ x\equiv b \pmod{n} \end{cases}$$

可知

$$\begin{cases} a = x \bmod m\\ b = x \bmod n \end{cases}$$

于是 $F(G(a, b)) = (a, b)$，即 $F \circ G = \mathrm{id}_{\mathbb Z_m \times \mathbb Z_n}$。

因此 $F$ 与 $G$ 互为逆映射，$F$ 是双射，欧拉函数是积性函数得证。

总结

这次文章表面上是一篇泛泛地写一些数论的基本知识，实际上是在不断地铺垫证明欧拉函数的知识点，饺子醋大概也就这样了吧。

中间为了节省篇幅还是跳过了不少需要严谨证明的东西，甚至最开始想要严格定义整数来着，洋洋洒洒写了一半的定义后意识到这样写会导致篇幅像上篇一样不受控制地发展……真是吓到我了，于是选择了及时止损，将整数的定义删去了。

正如标题所说，数论真的是非常非常难学的一门学科。对于我这种数学苦手来说，口头上说这些是数论的基础知识，但实际上自己其实最多也就学到这种深度，以后大概是没什么能写的了。

接下来是本博客的未来目标和定位，作为开设本博客的初心，未来肯定依然会是以技术方向的文章为主，会是笔记、教程、、、或是分享。接着是博客装修，大概会一边调主题的同时一边慢慢地迁移技术栈到 Next.js，争取在半年左右的时间让本站焕然一新🥰

最后，感谢 OI Wiki、感谢知乎、感谢各家大模型对本站写作的大力支持。

朋友们，下个月见~