第三章同余方程

同余式

\forall m \in Z^{+}, f (x) = a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0} \equiv 0 mod m

为模 $m$ 的同余式 。

如果 $m ∤ a_{n}$ 称 $n$ 为 $f (x)$ 的次数 $de g f$ ，而 $f (x)$ 称为 模 $m$ 的 $n$ 次同余式 。

如果我们能找到一个解 $a \in Z$ ，那么所有满足 $a^{'} \equiv a mod m$ 的 $a^{'}$ 都是它的解。

C_{a} = {a^{'} ∣ a \in Z, a^{'} \equiv a mod m}

IMPORTANT

剩余类中的所有解看作一个解，用 $x \equiv a mod m$ 规范表述。

什么时候看作不同的解呢？

当 $a_{1}, a_{2}$ 都是同余式的解，且它们对模 $m$ 不同余（即 $a_{1} mod m \neq = a_{2} mod m$ 时），称 $a_{1}, a_{2}$ 为不同的解。

解数：模 $m$ 同余式的解数是所有对模 $m$ 两两不同余的解的个数，它至多为 $m$ 。

一次同余式

定理设 $m \in Z^{+}, a \in Z$ 一次同余式 $a x \equiv 1 mod m$ 有解 $\Leftrightarrow (a, m) = 1$ 且在有解时该解是唯一的。

证明

存在性

(a, m) = 1 \Rightarrow s a + t m = 1 (扩展欧几里得算法) s a \equiv 1 (mod m) (模 m) \Rightarrow x \equiv s (mod m) 是 a x \equiv 1 (mod m) 的一个解 假设还有解 x^{'}, 则 a (x^{'} - x) \equiv 0 (mod m) 因为 (a, m) = 1, 所以 m ∣ (x^{'} - x) ，即 x^{'} \equiv x (mod m) 则还在同一个剩余系内，视为一个解 . (唯一性得证)

必要性

如果同余式 $a x \equiv 1 mod m$ 有解 $x \equiv x_{0} (mod m)$ ，则存在整数 $q$ 使得 $a x_{0} = 1 + q m$ ，即 $a x_{0} - q m = 1$ ，因此有 $(a, m) = 1$ 。

定理设 $m \in Z^{+}, m ∤ a, d = (a, m)$ 则 $a x \equiv b mod m$ 有解 $\Leftrightarrow$ $d ∣ b$ 。且在有解时解数必为 $d$ 。

证明

$\Rightarrow$ (必要性)

$a x \equiv b mod m$ 有解 $x \equiv x_{0} (mod m)$ 意味着 $m ∣ (a x_{0} - b)$ 。因为 $d ∣ m$ 且 $m ∣ (a x_{0} - b)$ ，所以 $d ∣ (a x_{0} - b)$ 。又因为 $d ∣ a$ ，所以 $d ∣ a x_{0}$ 。因此 $d ∣ (a x_{0} - (a x_{0} - b))$ ，即 $d ∣ b$ 。

$\Leftarrow$ (充分性)

设 $d = (a, m)$ 且 $d ∣ b$ 。因为 $(\frac{a}{d}, \frac{m}{d}) = 1$ ，存在整数 $s, t$ 使得 $s \cdot \frac{a}{d} + t \cdot \frac{m}{d} = 1$ 。两边同乘以 $\frac{b}{d}$ ： $s \cdot \frac{a}{d} \cdot \frac{b}{d} + t \cdot \frac{m}{d} \cdot \frac{b}{d} = \frac{b}{d}$ $a \cdot (s \cdot \frac{b}{d}) + m \cdot (t \cdot \frac{b}{d}) = b$ $a \cdot (s \cdot \frac{b}{d}) \equiv b (mod m)$ 。这说明 $x \equiv s \cdot \frac{b}{d} (mod m)$ 是一个解。

求解的一般方法

设 $x_{0} = s \cdot \frac{b}{d}$ 是一个特解，则 $a x \equiv b mod m$ 的全部解为：

x \equiv x_{0} + k \cdot \frac{m}{d} mod m, (k = 0, 1, \dots, d - 1)

代入特解的表达式：

x \equiv s \cdot \frac{b}{d} + k \cdot \frac{m}{d} mod m, (k = 0, 1, \dots, d - 1)

逆元

$a$ 是模 $m$ 的简化剩余 $\Leftrightarrow a$ 是模 $m$ 的可逆元。

定义：对于 $m \in Z^{+}, a \in Z$ ，如果存在 $a_{0} \in Z$ 使得 $a a_{0} \equiv 1 mod m$ ，则称 $a$ 是模 $m$ 的可逆元，并将 $a_{0}$ 称为 $a$ 模 $m$ 的逆元，记作 $a^{- 1} (mod m)$ 。

性质： $a$ 模 $m$ 的逆元存在当且仅当 $(a, m) = 1$ 。

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

解一次同余方程组：

⎩ ⎨ ⎧ f_{1} (x) \equiv 0 mod m_{1} f_{2} (x) \equiv 0 mod m_{2} \dots f_{n} (x) \equiv 0 mod m_{n}

对于两两互素的 $m_{1}, m_{2}, \dots m_{k} \in Z^{+}, b_{1}, b_{2}, \dots, b_{k} \in Z$ 则下面的一次同余方程组有解，且解在模 $m_{1} m_{2} \dots m_{k}$ 下的意义唯一：

⎩ ⎨ ⎧ x \equiv b_{1} mod m_{1} x \equiv b_{2} mod m_{2} \dots x \equiv b_{k} mod m_{k}

其解的表达式

令

m = i = 1 \prod k m_{i}, M_{j} = \frac{m}{m _{j}}, M_{j}^{'} M_{j} \equiv 1 mod m_{j} (其中 M_{j}^{'} 是 M_{j} 模 m_{j} 的逆元) (j = 1, 2, \dots k)

则解为：

x \equiv i = 1 \sum k M_{i}^{'} M_{i} b_{i} mod m

这是一个构造式的解。

证明中国剩余定理

唯一性证明

设 $r$ 和 $s$ 都是同余方程组的解。

{r \equiv b_{i} mod m_{i} s \equiv b_{i} mod m_{i} ⟹ r \equiv s mod m_{i}, \forall i = 1, 2, \dots, k

因此 $m_{i} ∣ (r - s)$ ，即 $r - s$ 是所有 $m_{i}$ 的公倍数。

r \equiv s mod [m_{1}, m_{2}, \dots, m_{k}]

由于 $m_{1}, m_{2}, \dots, m_{k}$ 两两互素，它们的最小公倍数等于它们的乘积，即 $[m_{1}, m_{2}, \dots, m_{k}] = m_{1} m_{2} \dots m_{k} = m$ 。故 $r \equiv s mod m$ ，解在模 $m$ 的意义下是唯一的。

构造式证明（存在性）

构造的解 $x_{0} = \sum_{i = 1}^{k} M_{i}^{'} M_{i} b_{i}$ 满足方程组：

对于任意一个 $m_{j}$ ：

x_{0} \equiv i = 1 \sum k M_{i}^{'} M_{i} b_{i} (mod m_{j})

由于当 $i \neq = j$ 时， $m_{j} ∣ M_{i}$ （因为 $M_{i} = m / m_{i}$ ），所以 $M_{i} \equiv 0 (mod m_{j})$ 。只有 $i = j$ 的项不为零：

x_{0} \equiv M_{j}^{'} M_{j} b_{j} (mod m_{j})

因为 $M_{j}^{'} M_{j} \equiv 1 (mod m_{j})$ ，所以

x_{0} \equiv 1 \cdot b_{j} \equiv b_{j} (mod m_{j})

这表明 $x_{0}$ 是方程组的一个解。

NOTE

课纲要求：了解中国剩余定理的递归证明

递归式证明

设 $x_{i - 1}$ 是前 $i - 1$ 个同余式解，即 $x \equiv x_{i - 1} (mod N_{i - 1})$ ，其中 $N_{i - 1} = m_{1} m_{2} \dots m_{i - 1}$ 。现在求解包含第 $i$ 个同余式的方程组：

{x \equiv x_{i - 1} mod N_{i - 1} x \equiv b_{i} mod m_{i}

由第一个方程，设 $x = x_{i - 1} + y_{i - 1} \cdot N_{i - 1}$ 。代入第二个方程：

x_{i - 1} + y_{i - 1} \cdot N_{i - 1} \equiv b_{i} (mod m_{i}) ⟹ y_{i - 1} \cdot N_{i - 1} \equiv b_{i} - x_{i - 1} (mod m_{i})

由于 $(N_{i - 1}, m_{i}) = 1$ (因为 $m_{j}$ 两两互素)，所以 $N_{i - 1}$ 模 $m_{i}$ 的逆元 $N_{i - 1}^{'}$ 存在，满足 $N_{i - 1} \cdot N_{i - 1}^{'} \equiv 1 (mod m_{i})$ 。同乘以 $N_{i - 1}^{'}$ ：

y_{i - 1} \equiv (b_{i} - x_{i - 1}) \cdot N_{i - 1}^{'} (mod m_{i})

设 $y_{i - 1}^{(0)}$ 是这个解的某个代表元，则 $y_{i - 1} = y_{i - 1}^{(0)} + q m_{i}$ 。代回 $x$ 的表达式，得到第 $i$ 个解 $x_{i}$ ：

x_{i} = x_{i - 1} + y_{i - 1}^{(0)} \cdot N_{i - 1} (mod m_{1} m_{2} \dots m_{i})

这样就将 $i - 1$ 个方程的解扩展到了 $i$ 个方程的解，重复 $k$ 次即可得到最终解 $x_{k}$ 。

中国剩余定理的应用

快速计算大整数取模

若 $x$ 是一个大整数，要求计算它模 $m$ 的值，我们可以把 $m$ 拆成两两互素的 $m_{1}, m_{2}, \dots m_{k}$ ，建立一个同余方程组：

⎩ ⎨ ⎧ x \equiv b_{1} mod m_{1} x \equiv b_{2} mod m_{2} \dots x \equiv b_{k} mod m_{k}

求解这个方程组就可以得到 $x mod m$ 的解。

这么做的好处：

减少计算复杂度：对于模 $l$ bit 整数的质数运算，从传统的 $O ((2 l)^{3})$ 复杂度可以减少到 $O (2 l^{3})$ 复杂度，减少了常数。
并行计算可能性：将大数模运算分解成多个小模运算，可以利用并行计算提高效率。

计算样例：计算 $2^{1000000} mod 77$ 。 $m = 77 = 7 \times 11$ ，其中 $(7, 11) = 1$ 。转化为同余方程组：

{x \equiv 2^{1000000} mod 7 x \equiv 2^{1000000} mod 11

计算 $b_{1} = 2^{1000000} mod 7$ : 由费马小定理， $2^{6} \equiv 1 mod 7$ 。 $1000000 = 6 \times 166666 + 4$ 。 $2^{1000000} = (2^{6})^{166666} \cdot 2^{4} \equiv 1^{166666} \cdot 16 \equiv 16 \equiv 2 mod 7$ 。 $b_{1} = 2$ 。
计算 $b_{2} = 2^{1000000} mod 11$ : 由费马小定理， $2^{10} \equiv 1 mod 11$ 。 $1000000 = 10 \times 100000$ 。 $2^{1000000} = (2^{10})^{100000} \equiv 1^{100000} \equiv 1 mod 11$ 。 $b_{2} = 1$ 。

现在解方程组：

{x \equiv 2 mod 7 (m_{1} = 7, b_{1} = 2) x \equiv 1 mod 11 (m_{2} = 11, b_{2} = 1)

$m = 77, M_{1} = 11, M_{2} = 7$ 。求逆元： $M_{1}^{'} M_{1} \equiv 1 mod m_{1} ⟹ 11 M_{1}^{'} \equiv 1 mod 7 ⟹ 4 M_{1}^{'} \equiv 1 mod 7$ . 解得 $M_{1}^{'} = 2$ 。 $M_{2}^{'} M_{2} \equiv 1 mod m_{2} ⟹ 7 M_{2}^{'} \equiv 1 mod 11$ . 解得 $M_{2}^{'} = 8$ 。解为：

x \equiv M_{1}^{'} M_{1} b_{1} + M_{2}^{'} M_{2} b_{2} mod m x \equiv 2 \cdot 11 \cdot 2 + 8 \cdot 7 \cdot 1 mod 77 x \equiv 44 + 56 mod 77 x \equiv 100 mod 77 x \equiv 23 mod 77

因此 $2^{1000000} mod 77 = 23$ 。

高次同余方程

技巧 3-4 恒等式

若 $h (x) \equiv 0 (mod m)$ 有 $m$ 个解。

f (x) = q (x) h (x) + r (x) \equiv b (mod m) \Rightarrow r (x) \equiv b (mod m)

如：

2 x^{7} - x^{5} - 3 x^{3} + 6 x + 1 2 x^{7} - x^{5} - 3 x^{3} + 6 x + 1 2 x^{7} - x^{5} - 3 x^{3} + 6 x + 1 \equiv 0 (mod 5) = (2 x^{2} - 1) (x^{5} - x) + (- x^{3} + 5 x + 1) \equiv - x^{3} + 5 x + 1 \equiv - x^{3} + 1 (mod 5)

（注：这里利用了费马小定理推论 $x^{p} - x \equiv 0 (mod p)$ ）

技巧 3-5 设 $d$ 是 $m$ 的正因子

{m ∣ f (x) d ∣ m \Rightarrow d ∣ f (x)

f (x) \equiv 0 (mod m) 有解 \Rightarrow f (x) \equiv 0 (mod d) 有解

这个结论可以用来证明方程无解（逆否命题）：

f (x) \equiv 0 (mod d) 无解 \Rightarrow f (x) \equiv 0 (mod m) 无解

多项式的 $g cd$

回顾多项式的除法和多项式 $g cd$ ，在求解模素数 $p$ 的同余方程时，可以利用恒等式进行降次：定理：对于 $f (x) (mod p)$ ，存在多项式 $q (x), r (x)$ 使得 $de g (r (x)) < p$ 且：

f (x) = (x^{p} - x) q (x) + r (x)

从而有：

f (x) \equiv 0 (mod p) \Leftrightarrow r (x) \equiv 0 (mod p)

解的个数

分解 $m$ 若 $m = m_{1} m_{2} \dots m_{k}$ ，且 $m_{i}$ 两两互素：

f (x) \equiv 0 (mod m)

与

⎩ ⎨ ⎧ f (x) \equiv 0 (mod m)_{1} f (x) \equiv 0 (mod m)_{2} \dots f (x) \equiv 0 (mod m)_{k}

等价。前者的解数 $T$ 为后者的每一条方程的解数 $T_{i}$ 的乘积：

T = i = 1 \prod k T_{i}

充分性

对于同余方程组的每一个解 $(c_{1}, c_{2}, \dots, c_{k})$ ，其中 $c_{i}$ 是 $f (x) \equiv 0 (mod m_{i})$ 的解。根据中国剩余定理，存在唯一的 $x_{0} (mod m)$ 满足 $x_{0} \equiv c_{i} (mod m_{i})$ 。对于这个 $x_{0}$ ：

f (x_{0}) \equiv f (c_{i}) \equiv 0 (mod m_{i}), \forall i = 1, \dots, k

从而 $f (x_{0}) \equiv 0 (mod m)$ ，因此 $x_{0}$ 是原方程的解。解数是所有分量方程解数的乘积。

必要性

设 $x_{0}$ 是 $f (x) \equiv 0 (mod m)$ 的解，即 $m ∣ f (x_{0})$ 。由于 $m_{i} ∣ m$ ，所以 $m_{i} ∣ f (x_{0})$ ，即 $f (x_{0}) \equiv 0 (mod m_{i})$ 。因此 $x_{0}$ 也是方程组 ${f (x) \equiv 0 (mod m)_{1} \dots$ 的解。同时，如果 $x_{1} \neq \equiv x_{2} (mod m)$ ，那么它们必有一对 $m_{i}$ 不同余。因此，原方程的每个解都对应方程组的一个唯一的解组合。

定理 (模素数 $p$ )

如果 $x \equiv c_{1}, c_{2}, \dots, c_{k} (mod p)$ 是 $f (x) \equiv 0 (mod p)$ 的不同解，则：

f (x) \equiv i = 1 \prod k (x - c_{i}) f_{k} (x) (mod p)

着告诉我们 解的个数 $k$ 至多为多项式的次数 $n$ ，即 $k \leq min (de g f, p)$ 。

推论

次数小于 $p$ 的同余方程 $f (x) \equiv 0 (mod p)$ 的解数为 $p$ 当且仅当 $p ∣ f (x)$ 的每一个系数。

求解模为素数幂的同余方程

m = i = 1 \prod k p_{i}^{α_{i}} \Rightarrow f (x) \equiv 0 (mod m)

根据同余式的分解性，求解 $f (x) \equiv 0 (mod m)$ 等价于求解 $f (x) \equiv 0 (mod p_{i}^{α_{i}})$ 的系统。

求解 $f (x) \equiv 0 (mod p^{α})$ ，通常采用 Hensel’s Lemma (汉斯尔引理)，从模 $p$ 的解逐步“提升”到模 $p^{2}, \dots, p^{α}$ 的解。

基本思路 (解的提升)：

首先求出 $f (x) \equiv 0 (mod p)$ 的解 $x \equiv c (mod p)$ 。
假设我们已求得 $f (x) \equiv 0 (mod p^{i - 1})$ 的解 $x \equiv c_{i - 1} (mod p^{i - 1})$ 。
我们寻找 $f (x) \equiv 0 (mod p^{i})$ 的解 $x \equiv c_{i} (mod p^{i})$ ，其中 $c_{i}$ 满足 $c_{i} = c_{i - 1} + k \cdot p^{i - 1}$ ，其中 $k \in {0, 1, \dots, p - 1}$ 。
将 $c_{i}$ 代入 $f (x) \equiv 0 (mod p^{i})$ 并进行泰勒展开，利用 $f (c_{i - 1}) \equiv 0 (mod p^{i - 1})$ 的条件，可以得到关于 $k$ 的一个线性同余式： $f^{'} (c_{i - 1}) \cdot k \equiv \frac{- f ( c _{i - 1} )}{p ^{i - 1}} (mod p)$
根据 $f^{'} (c_{i - 1}) (mod p)$ 的值，分情况讨论 $k$ 的解（ $0$ 个， $1$ 个，或 $p$ 个解），从而确定 $c_{i}$ 的个数，然后重复此过程直到求得 $(mod p^{α})$ 的解。

Candlest 的博客

探索

第三章同余方程

同余式

一次同余式

求解的一般方法

逆元

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

证明中国剩余定理

中国剩余定理的应用

高次同余方程

多项式的 $g cd$

解的个数

求解模为素数幂的同余方程

关系图谱

目录

反向链接

Candlest 的博客

探索

第三章 同余方程

同余式

一次同余式

求解的一般方法

逆元

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

证明中国剩余定理

中国剩余定理的应用

高次同余方程

多项式的 gcd

解的个数

求解模为素数幂的同余方程

关系图谱

目录

反向链接

第三章同余方程

多项式的 $g cd$