初等数论 第二章 同余

同余的定义与性质

定义

$$\forall m \in \mathbb{Z}^+, \; a,b \in \mathbb{Z}, \text{若} \; m \mid (a-b),$$

则存在 $k \in \mathbb{Z}$ 使得：

$$a - b = km \quad \Longleftrightarrow \quad a = km + b.$$

此时称 a 与 b 模 m 同余，记作：

$$a \equiv b \pmod m, \quad \text{反之记作 } a \not\equiv b \pmod m.$$

示例

$$7 \mid (27 - 6) \Rightarrow 27 \equiv 6 \pmod 7, \quad 29 \equiv 1 \pmod 7.$$

性质

有时使用“$\mid$”符号更容易直观理解同余的意义。

1. 自反性：

   $$a \equiv a \pmod m$$

2. 对称性：

   $$a \equiv b \pmod m \Leftrightarrow b \equiv a \pmod m$$

3. 传递性：

   $$a \equiv b \pmod m, \; b \equiv c \pmod m \Rightarrow a \equiv c \pmod m$$

4. 唯一性：
   若 $a \equiv b \pmod m$，则它们除以 $m$ 的最小非负余数相同。

5. 线性可加性：

   $$a_1 \equiv b_1 \pmod m, \quad a_2 \equiv b_2 \pmod m$$

   则对任意整数 $s,t$，

   $$s a_1 + t a_2 \equiv s b_1 + t b_2 \pmod m$$

6. 可乘性：

   $$a_1 \equiv b_1 \pmod m, \quad a_2 \equiv b_2 \pmod m \Rightarrow a_1 a_2 \equiv b_1 b_2 \pmod m$$

   推论：

   $$a \equiv b \pmod m \Rightarrow a^i \equiv b^i \pmod m$$

多项式同余

根据可加性与可乘性，可得：

$$x \equiv y \pmod m, \quad a_i \equiv b_i \pmod m \Rightarrow a_0 + a_1x + \dots + a_nx^n \equiv b_0 + b_1y + \dots + b_ny^n$$

应用例子：判断整除性（被 3 或 9 整除）

若 $3 \mid n$，当且仅当其各位数字之和能被 3 整除。

证明：

$$10 \equiv 1 \pmod 3 \Rightarrow n = a_k10^k + \dots + a_0 \equiv a_k + \dots + a_0 \pmod 3.$$

例题：同余的周期

$$2^1 \equiv 2, \; 2^2 \equiv 4, \; 2^3 \equiv 1 \pmod 7$$

周期为 3。

$$2003 = 666\times3 + 2 \Rightarrow 2^{2003} \equiv 2^2 \equiv 4 \pmod 7.$$

错误命题（反例）

$$ad \equiv bd \pmod m \;\;\Rightarrow\;\; a \equiv b \pmod m$$

不一定成立，因为 $d$ 可能与 $m$ 不互素，也就是 0 因子。

例题

$$a \equiv b \pmod m \Rightarrow (a,m) = (b,m)$$

证明：

$$a \equiv b \pmod m \Rightarrow a = mk + b \Rightarrow (a,m) = (b,m)$$

剩余类与完全剩余系

剩余类定义

$$C_a = \{ c \in \mathbb{Z} \mid c \equiv a \pmod m \}$$

即所有模 $m$ 余 $a$ 的整数集合。

• 模 $m$ 的剩余类共有 $m$ 个：$C_0, C_1, \dots, C_{m-1}$。
• 每个 $C_a$ 都非空。

完全剩余系

若有 $m$ 个整数 $r_0, r_1, \dots, r_{m-1}$，它们模 $m$ 的余数互不相同，则称它们构成一个 模 $m$ 的完全剩余系。

$$\{ r_0, r_1, \dots, r_{m-1} \}$$

性质定理

1. 若 $(a,m)=1$，则对任意 $b\in \mathbb{Z}$，
   当 $x$ 取遍模 $m$ 的一个完全剩余系时，$ax+b$ 也构成一个完全剩余系。

2. 若 $(m_1, m_2)=1$，则

   $$m_2x_1 + m_1x_2$$

   当 $x_1$、$x_2$ 分别取遍模 $m_1$、$m_2$ 的完全剩余系时，构成模 $m_1m_2$ 的完全剩余系。

简化剩余系

动机

完全剩余系中含有 0 因子，破坏了一些直觉的代数性质：

$$8 \equiv 0 \bmod 8, 但是 \begin{cases} 2 \equiv 2 \bmod 8\\ 4 \equiv 4 \bmod 8 \end{cases}$$

它让一些本该能“消去”“反转”的运算失效.

简化剩余系的工作，就是把完全剩余系里面的0因子剔除，选取出能够组成域的元素.

定义

模 $m$ 的 简化剩余类：
包含所有与 $m$ 互素的剩余类。

模 $m$ 的 简化剩余系：
从每个简化剩余类中取一个代表元。

记：

$$\phi(m) = |\{ 1 \leq a < m \mid (a,m)=1 \}|$$

示例

模 10 的简化剩余系：

$$\{1, 3, 7, 9\}, \quad \phi(10)=4.$$

性质与推论

1. 若 $(a,m)=1$，则 $ax$ 遍历简化剩余系中所有元素。
2. 若 $(a,m)=1$，则存在 $a'$ 使得：

   $$a a' \equiv 1 \pmod m$$

   这就是 乘法逆元。

由贝祖等式：

$$(a,m)=1 \Rightarrow \exists s,t \text{ 使 } sa+tm=1 \Rightarrow sa \equiv 1 \pmod m.$$

模 $m$ 的简化剩余系记号

$$(\mathbb{Z}/m\mathbb{Z})^* = \{ C_a \mid 0 \leq a < m, (a,m)=1 \}$$

或简写为：

$$\mathbb{Z}_m^* = \{ a \mid 0 \leq a < m, (a,m)=1 \}, \quad |\mathbb{Z}_m^*| = \phi(m)$$

简化剩余系=完全剩余系的条件

$$m=p 为素数 \lrArr \mathbb{F}_p^* = \{ C_1, C_2, \dots, C_{p-1} \}$$

Wilson 定理

定理： 若 $p$ 是素数，则：

$$(p-1)! \equiv -1 \pmod p$$

证明： 每个 $a \in \{1,\dots,p-1\}$ 都有逆元 $a'$。 除了 $a=1$ 和 $a=p-1$，其余元素两两配对：

$$a a' \equiv 1 \pmod p$$

故：

$$(p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod p$$

欧拉函数与性质

1. 质数幂性质

$$\phi(p^\alpha) = p^\alpha - p^{\alpha-1}$$

2. 互素乘积性质

若 $(m,n)=1$，

$$\phi(mn) = \phi(m)\phi(n)$$

特别地：

$$\forall p,q \in \mathbb{P},\\ \phi(pq) = (p-1)(q-1) = pq - p - q + 1$$

3. 通式（分解乘积形式）

若

$$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_s^{\alpha_s},$$

则：

$$\phi(n) = n\prod_{i=1}^s \left(1 - \frac{1}{p_i}\right)$$

NOTE

若无法分解 $n$，则难以计算 $\phi(n)$，这正是 RSA 加密的数学基础。

4. 求和公式

$$\sum_{d\mid n} \phi(d) = n$$

这是一个整除关系的分划结论。

Euler 定理

定理：

$$(a,m)=1 \Rightarrow a^{\phi(m)} \equiv 1 \pmod m$$

证明： 设

$$\{ r_1, r_2, \dots, r_{\phi(m)} \}$$

为模 $m$ 的最小简化剩余系。
则

$$a r_1, a r_2, \dots, a r_{\phi(m)}$$

也是简化剩余系。

两边连乘：

$$a^{\phi(m)} (r_1 r_2 \dots r_{\phi(m)}) \equiv r_1 r_2 \dots r_{\phi(m)} \pmod m$$

约去积得：

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

Fermat 小定理

$$\forall p \in \mathbb{P}, a \in \Z,\\ a^p \equiv a \bmod p.$$

平方乘算法（快速幂）

RSA 等加密算法的关键实现。

原理

$$a^{b+c} \equiv (a^b a^c) \pmod m$$

递归实现

long long quick_pow_recursive(long long base, long long exponent, long long MOD) {
    if (exponent == 0) return 1;
    long long half = quick_pow_recursive(base, exponent >> 1, MOD);
    long long result = (half * half) % MOD;
    if (exponent % 2 == 1)
        result = (result * base) % MOD;
    return result;
}