初等数论 第三章 同余方程

同余式

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

为模 $m$ 的同余式 。

如果 $m \nmid a_n$ 称 $n$ 为 $f(x)$ 的次数 $\deg f$，而 $f(x)$ 称为 模 $m$ 的 $n$ 次同余式 。

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

$$C_a = \{a'\mid 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$ 一次同余式 $ax \equiv 1 \mod m$ 有解 $\lrArr (a,m)=1$ 且在有解时该解是唯一的 。

证明

存在性

$$(a,m)=1 \rArr sa+tm=1 \quad (\text{扩展欧几里得算法})\\ sa \equiv 1 \pmod m \quad (\text{模} m)\\ \rArr x \equiv s \pmod m \text{ 是 } ax \equiv 1 \pmod m \text{ 的一个解} \\ \text{假设还有解 } x', \text{ 则 } a(x'-x) \equiv 0 \pmod m \\ \text{因为 } (a,m)=1, \text{ 所以 } m \mid (x'-x) \text{，即 } x' \equiv x \pmod m \\ \text{则还在同一个剩余系内，视为一个解. (唯一性得证)}$$

必要性

如果同余式 $ax \equiv 1 \mod m$ 有解 $x \equiv x_0 \pmod m$，则存在整数 $q$ 使得 $ax_0 = 1 + qm$，即 $ax_0 - qm = 1$ ，因此有 $(a,m)=1$ 。

定理 设 $m \in \Z^+, m \nmid a, d = (a,m)$ 则 $ax \equiv b \mod m$ 有解 $\lrArr$ $d \mid b$ 。且在有解时解数必为 $d$ 。

证明

$\Rightarrow$ (必要性)

$ax \equiv b \mod m$ 有解 $x \equiv x_0 \pmod m$ 意味着 $m \mid (ax_0 - b)$ 。 因为 $d \mid m$ 且 $m \mid (ax_0 - b)$，所以 $d \mid (ax_0 - b)$ 。 又因为 $d \mid a$，所以 $d \mid ax_0$ 。 因此 $d \mid (ax_0 - (ax_0 - b))$，即 $d \mid b$ 。

$\Leftarrow$ (充分性)

设 $d=(a,m)$ 且 $d \mid 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 \pmod m$ 。 这说明 $x \equiv s \cdot \frac{b}{d} \pmod m$ 是一个解 。

求解的一般方法

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

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

代入特解的表达式：

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

逆元

$a$ 是模 $m$ 的简化剩余 $\lrArr 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} \pmod m$ 。

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

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

解一次同余方程组：

$$\begin{cases}     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 \end{cases}$$

对于两两互素的 $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$ 下的意义唯一 ：

$$\begin{cases} x \equiv b_1 \mod m_1\\ x \equiv b_2 \mod m_2\\ \dots\\ x \equiv b_k \mod m_k\\   \end{cases}$$

其解的表达式

令

$$m = \prod_{i=1}^{k} m_i,\\ M_j = \frac{m}{m_j}, \quad M_j'M_j \equiv 1 \mod m_j \quad (\text{其中 } M_j' \text{ 是 } M_j \text{ 模 } m_j \text{ 的逆元}) \\ (j = 1, 2, \dotsb k)\\$$

则解为：

$$x \equiv \sum_{i=1}^{k} M_i'M_ib_i \mod m$$

这是一个构造式的解。

证明中国剩余定理

唯一性证明

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

$$\begin{cases} r \equiv b_i \mod m_i\\ s \equiv b_i \mod m_i \end{cases} \implies r \equiv s \mod m_i, \quad \forall i=1, 2, \dots, k$$

因此 $m_i \mid (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_ib_i$ 满足方程组：

对于任意一个 $m_j$：

$$x_0 \equiv \sum_{i=1}^{k} M_i'M_ib_i \pmod{m_j}$$

由于当 $i \neq j$ 时，$m_j \mid M_i$ （因为 $M_i = m/m_i$），所以 $M_i \equiv 0 \pmod{m_j}$ 。 只有 $i=j$ 的项不为零：

$$x_0 \equiv M_j'M_jb_j \pmod{m_j}$$

因为 $M_j'M_j \equiv 1 \pmod{m_j}$，所以

$$x_0 \equiv 1 \cdot b_j \equiv b_j \pmod{m_j}$$

这表明 $x_0$ 是方程组的一个解 。

NOTE

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

递归式证明

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

$$\begin{cases} x \equiv x_{i-1} \mod N_{i-1}\\ x \equiv b_i \mod m_i \end{cases}$$

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

$$x_{i-1} + y_{i-1} \cdot N_{i-1} \equiv b_i \pmod{m_i} \\ \implies y_{i-1} \cdot N_{i-1} \equiv b_i - x_{i-1} \pmod{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 \pmod{m_i}$ 。 同乘以 $N_{i-1}'$：

$$y_{i-1} \equiv (b_i - x_{i-1}) \cdot N_{i-1}' \pmod{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} \pmod{m_1 m_2 \dots m_i}$$

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

中国剩余定理的应用

快速计算大整数取模

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

$$\begin{cases}     x \equiv b_1 \mod m_1\\     x \equiv b_2 \mod m_2\\     \dots\\     x \equiv b_k \mod m_k \end{cases}$$

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

这么做的好处：

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

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

$$\begin{cases} x \equiv 2^{1000000} \mod 7\\ x \equiv 2^{1000000} \mod 11 \end{cases}$$

1. 计算 $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$ 。
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$ 。

现在解方程组：

$$\begin{cases} x \equiv 2 \mod 7 \quad (m_1=7, b_1=2)\\ x \equiv 1 \mod 11 \quad (m_2=11, b_2=1) \end{cases}$$

$m = 77, M_1 = 11, M_2 = 7$ 。 求逆元： $M_1' M_1 \equiv 1 \mod m_1 \implies 11 M_1' \equiv 1 \mod 7 \implies 4 M_1' \equiv 1 \mod 7$. 解得 $M_1'=2$ 。 $M_2' M_2 \equiv 1 \mod m_2 \implies 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 \pmod m$ 有 $m$ 个解。

$$f(x) = q(x)h(x) + r(x) \equiv b \pmod m\\ \rArr\\ r(x) \equiv b \pmod m$$

如：

$$\begin{align*}     2x^7 - x^5 - 3x^3 + 6x + 1 &\equiv 0 \pmod 5\\     2x^7 - x^5 - 3x^3 + 6x + 1 &= (2x^2 - 1)(x^5 - x) + (-x^3 + 5x + 1)\\     2x^7 - x^5 - 3x^3 + 6x + 1 & \equiv -x^3 + 5x + 1 \equiv -x^3 + 1 \pmod 5 \end{align*}$$

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

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

$$\begin{cases}     m \mid f(x)\\     d \mid m \end{cases} \rArr d \mid f(x)$$

$$f(x) \equiv 0 \pmod m \text{ 有解 } \rArr f(x) \equiv 0 \pmod d \text{ 有解}$$

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

$$f(x) \equiv 0 \pmod d \text{ 无解 } \rArr f(x) \equiv 0 \pmod m \text{ 无解}$$

多项式的 $\gcd$

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

$$f(x) = (x^p - x)q(x) + r(x)$$

从而有：

$$f(x) \equiv 0 \pmod p \lrArr r(x) \equiv 0 \pmod p$$

解的个数

分解 $m$ 若 $m = m_1 m_2 \dots m_k$，且 $m_i$ 两两互素：

$$f(x) \equiv 0 \pmod m$$

与

$$\begin{cases}     f(x) \equiv 0 \pmod m_1\\     f(x) \equiv 0 \pmod m_2\\     \dots\\     f(x) \equiv 0 \pmod m_k \end{cases}$$

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

$$T = \prod_{i=1}^k T_i$$

充分性

对于同余方程组的每一个解 $\left(c_1, c_2, \dots, c_k\right)$，其中 $c_i$ 是 $f(x) \equiv 0 \pmod{m_i}$ 的解。根据中国剩余定理，存在唯一的 $x_0 \pmod m$ 满足 $x_0 \equiv c_i \pmod{m_i}$ 。 对于这个 $x_0$：

$$f(x_0) \equiv f(c_i) \equiv 0 \pmod{m_i}, \quad \forall i=1, \dots, k$$

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

必要性

设 $x_0$ 是 $f(x) \equiv 0 \pmod m$ 的解，即 $m \mid f(x_0)$ 。 由于 $m_i \mid m$，所以 $m_i \mid f(x_0)$，即 $f(x_0) \equiv 0 \pmod{m_i}$ 。 因此 $x_0$ 也是方程组 $\begin{cases} f(x) \equiv 0 \pmod m_1 \\ \dots \end{cases}$ 的解。 同时，如果 $x_1 \not\equiv x_2 \pmod m$，那么它们必有一对 $m_i$ 不同余 。因此，原方程的每个解都对应方程组的一个唯一的解组合。

定理 (模素数 $p$)

如果 $x\equiv c_1, c_2 ,\dots, c_k \pmod p$ 是 $f(x) \equiv 0 \pmod p$ 的不同解，则：

$$f(x) \equiv \prod_{i=1}^k (x-c_i) f_k(x) \pmod p$$

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

推论

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

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

$$m = \prod_{i=1}^{k} p_i^{\alpha_i} \rArr f(x) \equiv 0 \pmod m$$

根据同余式的分解性，求解 $f(x) \equiv 0 \pmod m$ 等价于求解 $f(x) \equiv 0 \pmod{p_i^{\alpha_i}}$ 的系统 。

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

基本思路 (解的提升)：

1. 首先求出 $f(x) \equiv 0 \pmod p$ 的解 $x \equiv c \pmod p$ 。
2. 假设我们已求得 $f(x) \equiv 0 \pmod {p^{i-1}}$ 的解 $x \equiv c_{i-1} \pmod {p^{i-1}}$。
3. 我们寻找 $f(x) \equiv 0 \pmod {p^i}$ 的解 $x \equiv c_i \pmod {p^i}$，其中 $c_i$ 满足 $c_i = c_{i-1} + k \cdot p^{i-1}$，其中 $k \in \{0, 1, \dots, p-1\}$。
4. 将 $c_i$ 代入 $f(x) \equiv 0 \pmod {p^i}$ 并进行泰勒展开，利用 $f(c_{i-1}) \equiv 0 \pmod {p^{i-1}}$ 的条件，可以得到关于 $k$ 的一个线性同余式：

   $$f'(c_{i-1}) \cdot k \equiv \frac{-f(c_{i-1})}{p^{i-1}} \pmod p$$

5. 根据 $f'(c_{i-1}) \pmod p$ 的值，分情况讨论 $k$ 的解（$0$ 个， $1$ 个，或 $p$ 个解），从而确定 $c_i$ 的个数，然后重复此过程直到求得 $\pmod {p^\alpha}$ 的解 。