第二章 同余

同余的定义与性质

定义

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

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

$$a-b=km⟺a=km+b.$$

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

$$a\equiv b(\mathrm{mod}m),\text{反之记作 }a\not\equiv b(\mathrm{mod}m).$$

示例

$$7\mid (27-6)\Rightarrow 27\equiv 6(\mathrm{mod}7),29\equiv 1(\mathrm{mod}7).$$

性质

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

1. 自反性：

   $$a\equiv a(\mathrm{mod}m)$$

2. 对称性：

   $$a\equiv b(\mathrm{mod}m)\iff b\equiv a(\mathrm{mod}m)$$

3. 传递性：

   $$a\equiv b(\mathrm{mod}m),b\equiv c(\mathrm{mod}m)\Rightarrow a\equiv c(\mathrm{mod}m)$$

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

5. 线性可加性：

   $$a_1\equiv b_1(\mathrm{mod}m),a_2\equiv b_2(\mathrm{mod}m)$$

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

   $$s{a}_1+t{a}_2\equiv s{b}_1+t{b}_2(\mathrm{mod}m)$$

6. 可乘性：

   $$a_1\equiv b_1(\mathrm{mod}m),a_2\equiv b_2(\mathrm{mod}m)\Rightarrow a_1{a}_2\equiv b_1{b}_2(\mathrm{mod}m)$$

   推论：

   $$a\equiv b(\mathrm{mod}m)\Rightarrow a^i\equiv b^i(\mathrm{mod}m)$$

多项式同余

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

$$x\equiv y(\mathrm{mod}m),a_i\equiv b_i(\mathrm{mod}m)\Rightarrow a_0+a_{1}x+\cdots +a_n{x}^n\equiv b_0+b_{1}y+\cdots +b_n{y}^n$$

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

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

证明：

$$10\equiv 1(\mathrm{mod}3)\Rightarrow n=a_{k}10^k+\cdots +a_0\equiv a_k+\cdots +a_0(\mathrm{mod}3).$$

例题：同余的周期

$$2^1\equiv 2,2^2\equiv 4,2^3\equiv 1(\mathrm{mod}7)$$

周期为 3。

$$2003=666\times 3+2\Rightarrow 2^{2003}\equiv 2^2\equiv 4(\mathrm{mod}7).$$

错误命题（反例）

$$ad\equiv bd(\mathrm{mod}m)\Rightarrow a\equiv b(\mathrm{mod}m)$$

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

例题

$$a\equiv b(\mathrm{mod}m)\Rightarrow (a,m)=(b,m)$$

证明：

$$a\equiv b(\mathrm{mod}m)\Rightarrow a=mk+b\Rightarrow (a,m)=(b,m)$$

剩余类与完全剩余系

剩余类定义

$$C_a=\{c\in \mathbb{Z}\mid c\equiv a(\mathrm{mod}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_2{x}_1+m_1{x}_2$$

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

简化剩余系

动机

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

$$8\equiv 0\mathrm{mod}8,但是\{\begin{array}{l}2\equiv 2\mathrm{mod}8\\ 4\equiv 4\mathrm{mod}8\end{array}$$

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

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

定义

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

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

记：

$$\varphi (m)=|\{1\le a<m\mid (a,m)=1\}|$$

示例

模 10 的简化剩余系：

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

性质与推论

1. 若 $(a,m)=1$，则 $ax$ 遍历简化剩余系中所有元素。
2. 若 $(a,m)=1$，则存在 $a^{\prime }$ 使得： $$a{a}^{\prime }\equiv 1(\mathrm{mod}m)$$ 这就是 乘法逆元。

由贝祖等式：

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

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

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

或简写为：

$${\mathbb{Z}}_m^{\ast }=\{a\mid 0\le a<m,(a,m)=1\},|{\mathbb{Z}}_m^{\ast }|=\varphi (m)$$

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

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

Wilson 定理

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

$$(p-1)!\equiv -1(\mathrm{mod}p)$$

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

$$a{a}^{\prime }\equiv 1(\mathrm{mod}p)$$

故：

$$(p-1)!\equiv 1\cdot (p-1)\equiv -1(\mathrm{mod}p)$$

欧拉函数与性质

1. 质数幂性质

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

2. 互素乘积性质

若 $(m,n)=1$，

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

特别地：

$$\begin{gathered} \forall p,q\in \mathbb{P}, \\ \varphi (pq)=(p-1)(q-1)=pq-p-q+1 \end{gathered}$$

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

若

$$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s},$$

则：

$$\varphi (n)=n\prod _{i=1}^s\left(1-\frac{1}{p_i}\right)$$

NOTE

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

4. 求和公式

$$\sum _{d\mid n}\varphi (d)=n$$

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

Euler 定理

定理：

$$(a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$$

证明： 设

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

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

$$a{r}_1,a{r}_2,\dots ,a{r}_{\varphi (m)}$$

也是简化剩余系。

两边连乘：

$$a^{\varphi (m)}(r_1{r}_2\dots r_{\varphi (m)})\equiv r_1{r}_2\dots r_{\varphi (m)}(\mathrm{mod}m)$$

约去积得：

$$a^{\varphi (m)}\equiv 1(\mathrm{mod}m).$$

Fermat 小定理

$$\begin{gathered} \forall p\in \mathbb{P},a\in \mathbb{Z}, \\ {a}^p\equiv a\mathrm{mod}p. \end{gathered}$$

平方乘算法（快速幂）

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

原理

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