本节对应原书 PDF 第 274–278 页（印刷 p259–p263）。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

11.4.1 一次同余方程

设 m>0，方程

ax \equiv c(\bmod\ m) \tag{11.1}

称作一次同余方程，使方程(11.1)成立的整数称作方程的解。

方程(11.1)不一定有解。例如，假设方程 4x \equiv 1(\bmod\ 6) 有解，设解为 x_0，则 6 \mid 4x_0-1，而 4x_0-1 是奇数，矛盾，故方程无解。下述定理给出方程(11.1)有解的条件。

定理 11.9 方程(11.1)有解的充分必要条件是 \gcd(a,m) \mid c。

证明 充分性。记 d = \gcd(a,m)，a = da_1，m = dm_1，c = dc_1，其中 a_1 与 m_1 互素。由定理 11.8，存在 x_1 和 y_1 使得 a_1x_1+m_1y_1 = 1。令 x = c_1x_1，y = c_1y_1，得 a_1x+m_1y = c_1。等式两边同乘 d，得 ax+my = c。所以，ax \equiv c(\bmod\ m)，即 x 是方程(11.1)的解。

必要性。设 x 是方程的解，则存在 y 使得 ax+my = c。由性质 11.1.1，有 d \mid c。

解读：把 ax \equiv c 看成 ax+my = c，问题的本质就是「用 a 和 m 的整系数组合能表示出哪些整数」。能表示出的恰好是 \gcd(a,m) 的所有倍数，这就是判别条件的来源。

设 x_0 是方程(11.1)的解，不难验证所有与 x_0 模 m 同余的数都是方程(11.1)的解，从而方程(11.1)的解可以写成 x \equiv x_0(\bmod\ m)。于是，只需对模 m 的每一个等价类取一个代表，验证是否使方程成立，就能找到方程的所有解。

例 11.9 解一次同余方程 6x \equiv 3(\bmod\ 9)。

解 \gcd(6,9) = 3，3 \mid 3，由定理 11.9，方程有解。取模 9 等价类的代表 x = -4,-3,-2,-1,0,1,2,3,4，计算结果如下：

\begin{aligned} 6 \times (-4) &\equiv 6 \times (-1) \equiv 6 \times 2 \equiv 3(\bmod\ 9) \\ 6 \times (-3) &\equiv 6 \times 0 \equiv 6 \times 3 \equiv 0(\bmod\ 9) \\ 6 \times (-2) &\equiv 6 \times 1 \equiv 6 \times 4 \equiv 6(\bmod\ 9) \end{aligned}

得方程的解 x \equiv -4,-1,2(\bmod\ 9)，方程的最小正整数解是 2。

定义 11.6 如果 ab \equiv 1(\bmod\ m)，则称 b 是 a 的模 m 逆，记作 a^{-1}(\bmod\ m) 或 a^{-1}。

根据定义，a 的模 m 逆就是方程

ax \equiv 1(\bmod\ m) \tag{11.2}

的解。

定理 11.10 （1）a 的模 m 逆存在的充分必要条件是 a 与 m 互素。

（2）设 a 与 m 互素，则在模 m 下 a 的模 m 逆是唯一的，即 a 的任意两个模 m 逆都模 m 同余。

证明 （1）这是定理 11.9 的直接推论。

（2）设 b_1 和 b_2 是 a 的两个模 m 逆，即 ab_1 \equiv 1(\bmod\ m)，ab_2 \equiv 1(\bmod\ m)。由性质 11.3.2，得 a(b_1-b_2) \equiv 0(\bmod\ m)。而 a 与 m 互素，由性质 11.3.5，b_1-b_2 \equiv 0(\bmod\ m)，得证 b_1 \equiv b_2(\bmod\ m)。

例 11.10 求 5 的模 7 逆。

解 方法 1：5 与 7 互素，故 5 的模 7 逆存在。采用例 11.9 中的方法解方程 5x \equiv 1(\bmod\ 7)。对 x = -3,-2,-1,0,1,2,3 计算，最后得到 5^{-1} \equiv 3(\bmod\ 7)。

方法 2：做辗转相除法，求得整数 b,k 使得 5b+7k = 1，则 b 是 5 的模 7 逆。计算如下：

\begin{aligned} 7 &= 5+2 \\ 5 &= 2 \times 2+1 \end{aligned}

回代，得

\begin{aligned} 1 &= 5-2 \times 2 \\ &= 5-2 \times (7-5) \\ &= 3 \times 5-2 \times 7 \end{aligned}

故 3 是 5 的模 7 逆。对任意的整数 k，7k+3 都是 5 的模 7 逆。

解读：方法 1 是穷举，方法 2 才是可扩展的做法：辗转相除法的每一步都保留了 5 与 7 的组合系数，回代后直接读出 5b+7k = 1 中的 b。模数很大时只能走方法 2。

根据定理 11.10，设 b 是 a 的模 m 逆，a 的模 m 逆的全体恰好是 [b]_m。今后用 a^{-1}(\bmod\ m) 代表 [b]_m 中的任意一个指定的数，通常是指 [b]_m 中的最小正整数。

定理 11.10 表明，方程(11.2)的解在模 m 下是唯一的。但是，在一般的情况下，一次同余方程(11.1)的解可能不止一个。如例 11.9 中的方程在模 9 下有 3 个解。实际上，设 d = \gcd(a,m)，当 d \mid c 时，方程(11.1)在模 m 下有 d 个解（见习题 11.44）。

11.4.2 中国剩余定理

我国南北朝时期有一部著名的数学著作《孙子算经》^①^，里面有一个"物不知数"问题，现称孙子问题："今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"

用今天的话说，这就是求一次同余方程组

\begin{aligned} x &\equiv 2(\bmod\ 3) \\ x &\equiv 3(\bmod\ 5) \\ x &\equiv 2(\bmod\ 7) \end{aligned}

的正整数解。下述定理给出一次同余方程组有解的条件。

定理 11.11（中国剩余定理） 设正数 m_1,m_2,\cdots,m_k 两两互素，则一次同余方程组

\begin{aligned} x &\equiv a_1(\bmod\ m_1) \\ x &\equiv a_2(\bmod\ m_2) \\ &\vdots \\ x &\equiv a_k(\bmod\ m_k) \end{aligned} \tag{11.3}

有整数解，并且在模 m = m_1m_2\cdots m_k 下解是唯一的，即任意两个解都是模 m 同余的。

证明 假设对 i = 1,2,\cdots,k，有

x_i \equiv \begin{cases} a_i(\bmod\ m_i) \\ 0(\bmod\ m_j) & j \neq i,\ 1 \leqslant j \leqslant k \end{cases} \tag{11.4}

令 x = x_1+x_2+\cdots+x_k，由性质 11.3.2，有

x \equiv a_i(\bmod\ m_i) \quad i = 1,2,\cdots,k

即 x 是所求的解。于是，问题转化为求一组满足方程(11.4)的 x_i，i = 1,2,\cdots,k。

令 M_i = m/m_i，i = 1,2,\cdots,k。M_i 是除 m_i 之外的 k-1 个 m_j 的乘积。根据方程(11.4)，m_j \mid x_i，j \neq i，1 \leqslant j \leqslant k，又 m_1,m_2,\cdots,m_k 两两互素，故 M_i \mid x_i。设 x_i = M_iy_i，应该有

M_iy_i \equiv a_i(\bmod\ m_i)

因此，只需要 M_i 有模 m_i 逆，就可得到 y_i。因为 m_i 与所有的 m_j(j \neq i) 互素，m_i 与 M_i 也互素，所以 M_i 有模 m_i 逆，设为 M_i^{-1}。取 y_i = a_iM_i^{-1}，则 x_i = M_iy_i = a_iM_i^{-1}M_i 满足方程组(11.4)。于是，

x = a_1M_1^{-1}M_1+a_2M_2^{-1}M_2+\cdots+a_kM_k^{-1}M_k \tag{11.5}

是同余方程组(11.3)的解。

最后，证明唯一性。设同余方程组(11.3)有两个解 c_1 和 c_2，类似定理 11.10 的证明，可证对每一个 i，c_1 和 c_2 模 m_i 同余，即 m_i \mid c_1-c_2。又 m_1,m_2,\cdots,m_k 两两互素，故有 m \mid c_1-c_2，即 c_1 和 c_2 模 m 同余。

解读：证明的思路是「各个击破」：先造出 x_i，让它在自己的模 m_i 下等于 a_i、在其他所有模下等于 0，再加起来。M_i = m/m_i 恰好被所有 m_j(j \neq i) 整除，所以把 M_i 乘上一个系数即可；而「m_i 与 M_i 互素」保证了所需的模逆一定存在。

中国剩余定理又称孙子定理，定理的证明是构造性的，它给出了求解一次同余方程组的计算步骤：首先计算 M_i 和 M_i^{-1}(1 \leqslant i \leqslant k)，然后按公式(11.5)计算，即可得到一次同余方程组(11.3)的解。如下例所示。

例 11.11 解《孙子算经》中的"物不知数"问题，即求一次同余方程组

\begin{aligned} x &\equiv 2(\bmod\ 3) \\ x &\equiv 3(\bmod\ 5) \\ x &\equiv 2(\bmod\ 7) \end{aligned}

的正整数解。

解 这里 m_1 = 3，m_2 = 5，m_3 = 7，m = 105。

M_1 = 5 \times 7 = 35，M_1 \equiv 2 \times 1 \equiv 2(\bmod\ 3)，2 \times 2 \equiv 1(\bmod\ 3)，故 M_1^{-1} = 2。同理，M_2 = 3 \times 7 = 21，M_2 \equiv 3 \times 2 \equiv 1(\bmod\ 5)，M_2^{-1} = 1。M_3 = 3 \times 5 = 15，M_3 \equiv 1(\bmod\ 7)，M_3^{-1} = 1。代入公式(11.5)，

x \equiv 2 \times 2 \times 35+3 \times 1 \times 21+2 \times 1 \times 15 = 233 \equiv 23(\bmod\ 105)

因此，问题的正整数解是 105k+23，k = 0,1,2,\cdots。最小正整数解是 23。

11.4.3 大整数算术运算

作为应用，下面介绍利用模算术运算进行大整数算术运算。设 m_1,m_2,\cdots,m_k 是 k 个大于 1 的两两互素的正整数，记 m = m_1m_2\cdots m_k。根据中国剩余定理，对任意的 0 \leqslant x<m，x 与 (x_1,x_2,\cdots,x_k) 一一对应，其中 x_i = x\ \bmod\ m_i，i = 1,2,\cdots,k。把 (x_1,x_2,\cdots,x_k) 称作 x 关于 m_1,m_2,\cdots,m_k 的模表示，简称 x 的模表示，记作 x = (x_1,x_2,\cdots,x_k)。

设 x = (x_1,x_2,\cdots,x_k)，y = (y_1,y_2,\cdots,y_k)，由于

\begin{aligned} (x+y)\ \bmod\ m_i &= (x_i+y_i)\ \bmod\ m_i \\ (x-y)\ \bmod\ m_i &= (x_i-y_i)\ \bmod\ m_i \\ xy\ \bmod\ m_i &= x_iy_i\ \bmod\ m_i \end{aligned}

故有

\begin{aligned} x+y &= ((x_1+y_1)\ \bmod\ m_1, (x_2+y_2)\ \bmod\ m_2, \cdots, (x_k+y_k)\ \bmod\ m_k) \\ x-y &= ((x_1-y_1)\ \bmod\ m_1, (x_2-y_2)\ \bmod\ m_2, \cdots, (x_k-y_k)\ \bmod\ m_k) \\ xy &= (x_1y_1\ \bmod\ m_1, x_2y_2\ \bmod\ m_2, \cdots, x_ky_k\ \bmod\ m_k) \end{aligned}

这表明可以通过对模表示的分量做模加、模减、模乘得到两个整数和、差、积的模表示。

解读：这一段的实质是「运算可以逐分量独立进行」。这正是并行计算和避免大整数进位的根据：每个分量都很小，可以放进单精度整数。

例 11.12 取 m_1 = 9，m_2 = 7，m_3 = 5，m = 9 \times 7 \times 5 = 315，可以通过关于模 9,7,5 的算术运算实现 315 以内的算术运算。例如，设 x = 20，y = 13，有

x = (2,6,0),\ y = (4,6,3)
x+y = ((2+4)\ \bmod\ 9, (6+6)\ \bmod\ 7, (0+3)\ \bmod\ 5) = (6,5,3) \tag{①}
x-y = ((2-4)\ \bmod\ 9, (6-6)\ \bmod\ 7, (0-3)\ \bmod\ 5) = (7,0,2) \tag{②}
xy = (2 \times 4\ \bmod\ 9, 6 \times 6\ \bmod\ 7, 0 \times 3\ \bmod\ 5) = (8,1,0) \tag{③}

由数的模表示反过来求这个数是解一次同余方程组，例如，由①求 x+y 要解一次同余方程组

\begin{aligned} z &\equiv 6(\bmod\ 9) \\ z &\equiv 5(\bmod\ 7) \\ z &\equiv 3(\bmod\ 5) \end{aligned}

根据式(11.5)，计算如下：

M_1 = 35,\quad M_2 = 45,\quad M_3 = 63
M_1^{-1} = 8,\quad M_2^{-1} = 5,\quad M_3^{-1} = 2

得

\begin{aligned} x+y &= (6 \times 8 \times 35+5 \times 5 \times 45+3 \times 2 \times 63)\ \bmod\ 315 = 33 \\ x-y &= (7 \times 8 \times 35+0 \times 5 \times 45+2 \times 2 \times 63)\ \bmod\ 315 = 7 \\ xy &= (8 \times 8 \times 35+1 \times 5 \times 45+0 \times 2 \times 63)\ \bmod\ 315 = 260 \end{aligned}

为了做大整数的算术运算，通常取 m_i = 2^e-1。这样做的好处是可以简化模计算。记 A = 2^e，将 x 的二进制表示分段，每段长为 e，

x = a_rA^r+a_{r-1}A^{r-1}+\cdots+a_1A+a_0

其中 0 \leqslant a_j<A，j = 0,1,\cdots,r。

注意到，A\ \bmod\ m_i = 1，得

\begin{aligned} x\ \bmod\ m_i &= (a_rA^r+a_{r-1}A^{r-1}+\cdots+a_1A+a_0)\ \bmod\ m_i \\ &= (a_r+a_{r-1}+\cdots+a_1+a_0)\ \bmod\ m_i \end{aligned}

由 \gcd(2^a-1,2^b-1) = 2^{\gcd(a,b)}-1（见习题 11.48），易知 2^a-1 与 2^b-1 互素 \Leftrightarrow a 与 b 互素。于是，只需取一组较小的两两互素的正整数 e_i，i = 1,2,\cdots,k（这是比较容易做到的），就可得到一组两两互素的很大的模 m_i = 2^{e_i}-1，i = 1,2,\cdots,k。设整数在计算机中的单精度表示占 4 个字节 32 位，无符号整数的最大值为 2^{32}-1。可取 m_1 = 2^{32}-1，m_2 = 2^{31}-1，m_3 = 2^{29}-1，m_4 = 2^{27}-1，m_5 = 2^{25}-1，此时 m = m_1m_2m_3m_4m_5>7 \times 10^{41}。这就可以用上述方法计算结果不超过 7 \times 10^{41} 的整数加、减、乘。所有的运算，除少量的外，都可用单精度整数实现。不仅如此，这个算法还非常便于并行化。

解读：取 m_i = 2^e-1 的理由是 2^e \equiv 1(\bmod\ 2^e-1)，于是求 x 的模表示时不必真做除法，只要把二进制分段后各段相加再取模即可，这正好适配计算机的位运算。

① 不要把《孙子算经》与《孙子兵法》中两个孙子当成一个人。《孙子兵法》的作者是孙武，公元前春秋时期人。而《孙子算经》大约成书于公元 5—6 世纪南北朝时期，作者不详。