初等数论入门 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}$

推导过程：

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

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

因此：

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

变化得：

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

又 $\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)$

判断：若 $d\nmid b$ ，则无解
约简（我们在此处约简，而不再解不定方程处约简）：

$\dfrac a d x\equiv \dfrac b d\pmod {\dfrac m d}$
求逆元，我们要求一个 $t$ 满足：

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

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

$\dfrac a d \cdot t+\dfrac m d \cdot s =1$
求特解与通解：
- 特解： $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}$

计算 $M=m_1m_2\cdots m_k$ ，这是解的周期
对于每个 $i$ ，令 $M_i=\dfrac M{m_i}$ ，必有 $\gcd(M_i,m_i)=1$
求解 $t_i$ ：

$M_it_i\equiv 1\pmod {m_i}$
构造解：

$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： $x=a_1+m_1k$
代入方差2： $a_1+m_1k\equiv a_@\pmod {m_2}$

即：

$m_1k\equiv a_2-a_1\pmod {m_2}$
解关于 $k$ 的同余方差。由于 $\gcd(m_1,m_2)=d|(a_2-a_1)$ ，故方程有解
设解得 $k\equiv k_0\pmod {\dfrac{m_2}d}$ ，代回得：

$x=a_1+m_1k_0+\dfrac{m_1m_2}d\cdot t$
合并后的方程：

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

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