初等数论入门 Lesson 6 同余方程与中国剩余定理

剩余系

• 完全剩余系：一组数 $a_1,a_2,\dots,a_m$ 称为模 $m$ 的一个完全剩余系，如果它们分别取自模 $m$ 的 $m$ 个不同的剩余类。

  有以下两种典型的剩余系：

  • 最小非负剩余系：$\{0, 1, 2, \dots, m - 1\}$
  • 绝对最小剩余系：$\left\{ -\left\lfloor \frac{m}{2} \right\rfloor, \dots, -1, 0, 1, \dots, \left\lceil \frac{m}{2} \right\rceil \right\}$

  有一个性质：

  • 如果 $\{a_1,\dots,a_m\}$ 是完全剩余系，且$\gcd(a,m)=1$，则 $\{aa_1 + b, aa_2 + b, \dots, aa_m + b\}$ 也是一个模 $m$ 的完全剩余系。

• 缩系（简化剩余系）

  在完全剩余系中，如果我们只挑与 $m$ 互素的代表元，就得到了缩系。

  性质：乘法封闭性

  • 如果 $\{r_1,r_2,\dots,r_{\varphi(m)}\}$ 是模 $m$ 的缩系，且 $a\in \{r_i\}$，则 $\{ar_1,ar_2,\dots,ar_{\varphi(m)}\}$ 仍然为模 $m$ 的缩系。

欧拉定理

设 $m\ge 2$，且 $(a,m)=1$，则：

$$\boxed{a^{\varphi(m)}\equiv 1\pmod m}$$

推导过程：

1. 取 $m$ 的缩系 $\{r_1,r_2,\dots,r_{\varphi(m)}\}$

2. 又 $(a,m)=1$，所以 $\{ar_1,ar_2,\dots,ar_{\varphi(m)}\}$ 仍为模 $m$ 的缩系

3. 因此：

   $$r_1r_2\cdots r_{\varphi(m)}\equiv (ar_1)(ar_2)\cdots(ar_{\varphi(m)})\pmod m$$

4. 变化得：

   $$r_1r_2\cdots r_{\varphi(m)}\equiv a^{\varphi(m)}(r_1r_2\cdots r_{\varphi(m)})\pmod m$$

5. 又 $\forall r_i:(r_i,m)=1$， 故：

   $$a^{\varphi(m)}\equiv 1\pmod m$$

   成立

费马小定理

当 $p$ 为素数，且 $p\nmid a$，则：

$$\boxed{a^{p-1}\equiv 1\pmod p}$$

费马小定理本质上是欧拉定理 $m$ 为素数的一个特例。

应用：降幂：化简大指数

一元线性同余方程

求解：

$$ax\equiv b\pmod m$$

等价于：

$$ax-b=my \\ ax + m'y =b$$

于是 解同余方程变成了解不定方程

我们规范 $ax\equiv b\pmod m$ 求解步骤如下，令 $d=\gcd(a,m)$

1. 判断：若 $d\nmid b$，则无解

2. 约简（我们在此处约简，而不再解不定方程处约简）：

   $$\dfrac a d x\equiv \dfrac b d\pmod {\dfrac m d}$$

3. 求逆元，我们要求一个 $t$ 满足：

   $$\dfrac a d \cdot t \equiv 1\pmod {\dfrac m d}$$

   这一步我们就使用拓展欧几里得算法求出：

   $$\dfrac a d \cdot t+\dfrac m d \cdot s =1$$

4. 求特解与通解：

   • 特解：$x_0\equiv t \cdot \dfrac b d\pmod {\dfrac m d}$
   • 通解：$x\equiv x_0+k\cdot \dfrac m d\pmod m$，其中 $k=0,1,\dots,d-1$

   因此模 $m$ 意义下共有 $d$ 个不同的解。

中国剩余定理

Chinese Remainder Theorem CRT

模数互素情况

已知 $m_i$ 两两互质，求解：

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \cdots \\ x \equiv a_k \pmod{m_k} \end{cases}$$

1. 计算 $M=m_1m_2\cdots m_k$，这是解的周期

2. 对于每个 $i$，令 $M_i=\dfrac M{m_i}$，必有 $\gcd(M_i,m_i)=1$

3. 求解 $t_i$：

   $$M_it_i\equiv 1\pmod {m_i}$$

4. 构造解：

   $$x=a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k$$

CRT断言：该方程组在模 $M$ 意义下有唯一解

拓展中国剩余定理

模数不互质情况

我们先来解决两个方程的情况：

$$\begin{cases} x\equiv a_1 \pmod{m_1}\\ x\equiv a_2\pmod {m_2} \end{cases}$$

令 $d=\gcd(m_1,m_2)$

可解性定理：该方程组有解，当且仅当：

$$a_1\equiv a_2\pmod d$$

证明：

因为 $d\mid m_1,\;d\mid m_2$，故：

$$\begin{cases} x-a_1\equiv 0 \pmod{d}\\ x-a_2\equiv 0\pmod {d} \end{cases}$$

因此：

$$a_1-a_2\equiv 0\pmod d$$

步骤：

1. 由方程1：$x=a_1+m_1k$

2. 代入方差2：$a_1+m_1k\equiv a_@\pmod {m_2}$

   即：

   $$m_1k\equiv a_2-a_1\pmod {m_2}$$

3. 解关于 $k$ 的同余方差。由于 $\gcd(m_1,m_2)=d|(a_2-a_1)$，故方程有解

4. 设解得 $k\equiv k_0\pmod {\dfrac{m_2}d}$，代回得：

   $$x=a_1+m_1k_0+\dfrac{m_1m_2}d\cdot t$$

5. 合并后的方程：

   $$x\equiv x_0\pmod {\text{lcm}(m_1,m_2)}$$

   其中 $x_0=a_1+m_1k_0$ （解）

多方程推广

策略：两两合并

若某一步 $a_i \not\equiv a_j \pmod{\gcd(m_i, m_j)}$，则无解