数论与密码学基础

数论研究整数的结构，也是计算机科学里一块真正用得上的基石。它可以追溯到古代文明对计数的兴趣，但作为独立学科，通常从欧几里得的《几何原本》算起：素数无穷多、整除的基本性质，至今仍是数论的中心事实。自然数尤其是素数（所有大于 $1$ 的整数的“积木”）的性质，吸引了历代数学家。后来领域扩到素数分布、丢番图方程、模运算，以及黎曼 zeta 一类的数论函数。从整除与素数出发，数论长成了数学里非常活跃的一支，应用从密码学一直延伸到动力系统。

整除性与模运算

先讲整除，是因为它撑起算术基本定理、最大公因数、最小公倍数、模运算，以及许多初等密码构造。讨论整数解、环与域的结构时，也会反复碰到同一套语言。

除法与整除

要谈整除，先把除法说清楚。小学里的除法是把一个数分成若干份，例如 $6\div2=3$，$6\div4=1.5$。有时商是整数，有时不是。定义如下。

定义商与余数

用非零数 $b$ 去除 $a$，记作 $a \div b$ 或 $\frac{a}{b}$，得到商 $q$，以及可能出现的余数 $r$。运算写成

$$a = b \times q + r,$$

其中 $0 \leq r < b$ 且 $q \in \mathbb{Z}$。

$6\div2=3$ 时，$6=2\times3+0$，于是 $r=0$、$q=3$。$6\div4$ 若做整数除法，则 $6=4\times1+2$，即 $q=1$、$r=2$；若做实数除法，则 $6/4=1.5$。下面把这两种运算分开。

定义实数除法

实数除法把余数并进商的小数部分。用 $b$ 除 $a$ 时，商 $q$ 是实数

$$q = \frac{a}{b}.$$

实数除法没有单独的余数，因为它关心的是“每份有多大”。整数除法关心的是整除关系与余数，这正是本章后面的主题。

有了两种除法，整除就好说了。

定义整除

设 $a$、$b$ 为整数且 $a\neq 0$。若存在整数 $c$ 使得 $b=a\times c$，就称 $a$ 整除 $b$。等价说法是 $b/a$ 为整数。此时称 $a$ 是 $b$ 的因数或约数，$b$ 是 $a$ 的倍数。记号 $a\mid b$ 表示 $a$ 整除 $b$；$a\nmid b$ 表示 $a$ 不整除 $b$。

例如 $4\mid 20$，因为 $20\div4$ 是整数；但 $4\nmid 21$。用存在量词写就是 $a\mid b \iff \exists c\,(ac=b)$。

问题不超过 $n$ 且被 $d$ 整除的正整数个数

设 $n$ 和 $d$ 是正整数。有多少个不超过 $n$ 的正整数能被 $d$ 整除？

被 $d$ 整除的正整数都形如 $dk$，其中 $k$ 是正整数。于是不超过 $n$ 且被 $d$ 整除的正整数个数，等于满足 $0<dk\le n$ 的整数 $k$ 的个数，也就是 $0<k\le n/d$ 的个数。因此答案是 $\left\lfloor n/d \right\rfloor$。

整除有下面几条性质，都可以直接证明。

定理整除的基本性质

设 $a$、$b$、$c$ 为整数，且 $a\neq 0$。则：

1. 若 $a \mid b$ 且 $a \mid c$，则 $a \mid (b+c)$；
2. 若 $a \mid b$，则对任意整数 $c$ 都有 $a \mid bc$；
3. 若 $a \mid b$ 且 $b\mid c$，则 $a \mid c$。

证明

由 $a \mid b$ 与 $a \mid c$，存在整数 $m$、$n$ 使得 $b=am$、$c=an$。于是 $b+c=am+an=a(m+n)$，$m+n$ 是整数，故 $a\mid(b+c)$。

由 $a\mid b$，存在整数 $k$ 使得 $b=ak$。对任意整数 $c$，$bc=a(kc)$，$kc$ 是整数，故 $a\mid bc$。

由 $a\mid b$ 且 $b\mid c$，存在整数 $p$、$q$ 使得 $b=ap$、$c=bq$。代入得 $c=(ap)q=a(pq)$，$pq$ 是整数，故 $a\mid c$。

由此立刻得到线性组合仍被整除。

推论线性组合的整除

设 $a$、$b$、$c$ 为整数且 $a\neq 0$。若 $a\mid b$ 且 $a\mid c$，则对任意整数 $m$、$n$ 都有 $a\mid mb+nc$。

证明

写 $b=au$、$c=av$，其中 $u,v$ 为整数。则 $mb+nc=a(mu+nv)$，括号内仍是整数，故得证。

模运算

这一小节盯住余数，也就是模运算。除法定义里已经出现商 $q$ 和余数 $r$，下面用专门记号写出它们。

记号商运算与余数运算

对 $a$、$b$，由 $a = b\times q + r$ 规定

$$q = a\ \textbf{div}\ b,$$$$r = a\ \textbf{mod}\ b.$$

当 $a$ 是整数、$b$ 是正整数时，$a\ \textbf{div}\ b = \left \lfloor a/b \right \rfloor$。

例$93$ 除以 $9$ 的商和余数

$93$ 除以 $9$ 的商和余数各是多少？

$93 = 9\times 10 + 3$，所以 $q = 10$，$r = 3$。

商：$93\ \textbf{div}\ 9 = 10 = \lfloor93/9\rfloor = \lfloor10.3333\dots \rfloor = 10$。

余数：$93\ \textbf{mod}\ 9 = 3 = 93 - 90$。

例$-93$ 除以 $9$ 的商和余数

$-93$ 除以 $9$ 的商和余数各是多少？

$-93 = 9\times (-11) + 6$，所以 $q = -11$，$r = 6$。

必须保证 $r\ge 0$。虽然也可以写 $-93 = 9\times(-10) - 3$，但这里的余数约定非负。别的除法算法允许负余数，习题里会碰到。

记号 $a\ \textbf{mod}\ m$ 表示用正整数 $m$ 除整数 $a$ 所得余数。下面引入一个相关但不同的记号：用同一个正整数去除两个整数，余数相同。为什么要关心“除以同一个正整数后余数一样”的数？这是数论的基本课题，后面会看出用处。

定义模 $m$ 同余

设 $a$、$b$ 为整数，$m$ 为正整数。若 $m$ 整除 $a-b$，则称 $a$ 模 $m$ 同余于 $b$，记作 $a \equiv b \pmod{m}$。这个关系叫做同余，$m$ 叫做模。若不同余，则写 $a \not\equiv b \pmod{m}$。

注意 $\bmod$ 与 $\textbf{mod}$ 不是同一个符号：前者是整数上的关系，后者是求余函数。二者有联系。

定理同余与余数

设 $a$、$b$ 为整数，$m$ 为正整数。则 $a \equiv b \pmod{m}$ 当且仅当 $a\ \textbf{mod}\ m = b\ \textbf{mod}\ m$。

证明

先设 $a \equiv b \pmod{m}$。按定义，$m$ 整除 $a-b$，即存在整数 $k$ 使得 $a-b=km$。

用 $m$ 除 $a$ 和 $b$，二者留下同一个余数 $r$：因为 $a=q_1m+r$、$b=q_2m+r$，而 $a-b$ 是 $m$ 的倍数，不改变余数。

反过来，若 $a \bmod m = b \bmod m$，则用 $m$ 去除二者时余数相同，记这个余数为 $r$。于是 $a=q_1m+r$、$b=q_2m+r$。相减得 $a-b=(q_1-q_2)m$，即 $m$ 整除 $a-b$，故 $a\equiv b\pmod{m}$。

注充要条件要证两头

说“当且仅当”时，必须从这一边推到那一边，再从那一边推回这一边。

定理同余的差形式

设 $m$ 为正整数。整数 $a$ 与 $b$ 模 $m$ 同余，当且仅当存在整数 $k$ 使得 $a=b+km$。

证明与上一条类似，习题里完成。

定理同余对加法和乘法封闭

设 $m$ 为正整数。若 $a \equiv b \pmod{m}$ 且 $c \equiv d \pmod{m}$，则 $a + c \equiv b + d \pmod{m}$ 且 $ac \equiv bd \pmod{m}$。

证明

由 $a \equiv b \pmod{m}$ 与 $c \equiv d \pmod{m}$，存在整数 $s$、$t$ 使得 $b=a+sm$、$d=c+tm$。于是

$$b + d = (a + sm) + (c + tm) = (a + c) + m(s + t),$$$$bd = (a + sm)(c + tm) = ac + m(at + cs + stm).$$

因此 $a + c \equiv b + d \pmod{m}$ 且 $ac \equiv bd \pmod{m}$。

例模 $5$ 的加法与乘法

由 $7 \equiv 2 \pmod{5}$ 与 $11 \equiv 1 \pmod{5}$，得到 $18 = 7 + 11 \equiv 2 + 1 = 3 \pmod{5}$，以及 $77 = 7 \cdot 11 \equiv 2 \cdot 1 = 2 \pmod{5}$。

推论先取模再运算

设 $m$ 为正整数，$a$、$b$ 为整数。则

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m,$$$$ab \bmod m = ((a \bmod m)(b \bmod m)) \bmod m.$$

证明

按 $\bmod$ 与同余的定义，$a \equiv (a \bmod m) \pmod{m}$，$b \equiv (b \bmod m) \pmod{m}$。于是 $a + b \equiv (a \bmod m) + (b \bmod m) \pmod{m}$，且 $ab \equiv (a \bmod m)(b \bmod m) \pmod{m}$。推论中的等式由这两条同余立刻得到。

在集合 $\mathbb{Z}_m=\{0,1,\ldots,m-1\}$ 上可以定义算术。加法 $\oplus_m$ 规定为

$$a \oplus_m b = (a + b) \bmod m,$$

右边是普通整数加法；乘法 $\odot_m$ 规定为

$$a \odot_m b = (a \cdot b) \bmod m,$$

右边是普通整数乘法。这两个运算叫做模 $m$ 加法和模 $m$ 乘法，使用它们就是在做模 $m$ 算术。

例在 $\mathbb{Z}_{11}$ 里计算

用 $\mathbb{Z}_m$ 中的定义求 $7 \oplus_{11} 9$ 和 $7 \odot_{11} 9$。

按模 $11$ 加法，

$$7 \oplus_{11} 9 = (7 + 9) \bmod 11 = 16 \bmod 11 = 5,$$$$7 \odot_{11} 9 = (7 \cdot 9) \bmod 11 = 63 \bmod 11 = 8.$$

因此 $7 \oplus_{11} 9 = 5$，$7 \odot_{11} 9 = 8$。

注下标写法

有时也用普通运算符号加下标来表示同一套计算。

习题

练习证明线性组合的整除

证明：若 $a$、$b$、$c$ 为整数且 $a\neq 0$，$a\mid b$ 且 $a\mid c$，则对任意整数 $m$、$n$ 都有 $a\mid mb+nc$。

证明

由整除的基本性质第二条，$a\mid b$ 给出 $a\mid mb$，$a\mid c$ 给出 $a\mid nc$。再由第一条，$a\mid(mb+nc)$。

练习证明同余的差形式

证明：整数 $a$ 与 $b$ 模 $m$ 同余，当且仅当存在整数 $k$ 使得 $a=b+km$。可以用本章其他定理。

证明

若 $a \equiv b \pmod{m}$，则 $m\mid(a-b)$，故存在整数 $k$ 使得 $a=b+km$。反过来，若存在整数 $k$ 使得 $a=b+km$，则 $km=a-b$，于是 $m\mid(a-b)$，即 $a\equiv b\pmod{m}$。

练习由 $ac\mid bc$ 推出 $a\mid b$

设 $a,b,c\in\mathbb{Z}^{+}$，$a,c\neq 0$，且 $ac\mid bc$。证明 $a\mid b$。

证明

$ac\mid bc$ 表示存在整数 $k$ 使得 $bc=k(ac)$，从而 $b=ka$，即 $a\mid b$。

练习整除则 $a$ 奇或 $b$ 偶

证明：若 $a$、$b$ 为整数且 $a$ 整除 $b$，则 $a$ 是奇数或 $b$ 是偶数。

证明

用逆否。设 $a$ 为偶数且 $b$ 为奇数，并假设 $a\mid b$。则存在整数 $k$ 使得 $b=ka$。令 $a=2n$、$b=2m+1$（原稿把奇数写成与 $a$ 共用同一个 $n$，这里分开写以免混淆），则 $2m+1=k\cdot 2n$，于是 $k=(2m+1)/(2n)$ 不是整数，与 $k\in\mathbb{Z}$ 矛盾。故原命题成立。

练习证明 $4\nmid(a^2+2)$

证明：若 $a$ 是正整数，则 $4\nmid (a^2+2)$。

证明

任意正整数 $a$ 必取下列四种形式之一，其中 $n$ 为整数：$a=4n$，$a=4n+1$，$a=4n+2$，$a=4n+3$。分别看 $a^2$ 模 $4$：

$$\begin{aligned} (4n)^2 &= 16n^2 = 4 \cdot 4n^2 \equiv 0 \pmod{4}, \\ (4n + 1)^2 &= 16n^2 + 8n + 1 = 4(4n^2 + 2n) + 1 \equiv 1 \pmod{4}, \\ (4n + 2)^2 &= 16n^2 + 16n + 4 = 4(4n^2 + 4n + 1) \equiv 0 \pmod{4}, \\ (4n + 3)^2 &= 16n^2 + 24n + 9 = 4(4n^2 + 6n + 2) + 1 \equiv 1 \pmod{4}. \end{aligned}$$

再加上 $2$：

$$\begin{aligned} a^2 + 2 &\equiv 2 \pmod{4} \quad \text{若 } a^2 \equiv 0 \pmod{4}, \\ a^2 + 2 &\equiv 3 \pmod{4} \quad \text{若 } a^2 \equiv 1 \pmod{4}. \end{aligned}$$

两种情形余数都不是 $0$，故 $4$ 不能整除 $a^2+2$。

练习由给定同余求 $c$

设 $a$、$b$ 为整数，$a \equiv 11 \pmod{19}$，$b \equiv 3 \pmod{19}$。求满足 $0 \leq c \leq 18$ 的整数 $c$，使得

1. $c \equiv 13a \pmod{19}$；
2. $c \equiv 8b \pmod{19}$；
3. $c \equiv a - b \pmod{19}$；
4. $c \equiv 7a + 3b \pmod{19}$；
5. $c \equiv 2a^2 + 3b^2 \pmod{19}$；
6. $c \equiv a^3 + 4b^3 \pmod{19}$。

这相当于求右端模 $19$ 的余数。直接算：

1. $13 \cdot 11 = 143 \equiv 10 \pmod{19}$
2. $8 \cdot 3 = 24 \equiv 5 \pmod{19}$
3. $11 - 3 = 8 \pmod{19}$
4. $7 \cdot 11 + 3 \cdot 3 = 86 \equiv 10 \pmod{19}$
5. $2 \cdot 11^2 + 3 \cdot 3^2 = 269 \equiv 3 \pmod{19}$
6. $11^3 + 4 \cdot 3^3 = 1439 \equiv 14 \pmod{19}$

练习同余则余数相同

设 $m$ 为正整数。证明：若 $a \equiv b \pmod{m}$，则 $a \bmod m = b \bmod m$。

证明

设 $a \equiv b \pmod{m}$，则 $m\mid a-b$，即 $a-b=mc$，从而 $a=b+mc$。令 $b=qm+r$，其中 $0\le r<m$（也就是 $r=b\bmod m$）。则 $a=qm+r+mc=(q+c)m+r$。按定义，$r$ 也等于 $a\bmod m$。

练习同余两边同除以公因数

设 $a \equiv b \pmod{n}$，且 $d\mid a$、$d\mid b$、$d\mid n$。证明

$$\frac{a}{d}\equiv \frac{b}{d} \pmod{\frac{n}{d}}.$$

证明

由 $a \equiv b \pmod{n}$，存在整数 $k$ 使得 $a=b+kn$。又 $d\mid a$、$d\mid b$，故 $a=dm_1$、$b=dm_2$；由 $d\mid n$ 得 $n=dl$。代入得 $dm_1=dm_2+k(dl)$。两边除以 $d$：$m_1=m_2+kl$，即

$$\frac{a}{d} = \frac{b}{d} + k \left(\frac{n}{d}\right).$$

$k(n/d)$ 是整数，故 $a/d$ 模 $n/d$ 同余于 $b/d$。

练习证明 $8$ 整除 $2(x+y)^{13}+y-1$

设整数 $x$、$y$ 满足 $x \equiv 2 \pmod{8}$、$y \equiv 7 \pmod{8}$。证明 $8$ 整除 $2(x + y)^{13} + y - 1$。

证明

先求 $x+y$ 模 $8$：

$$x + y \equiv 2 + 7 \equiv 9 \equiv 1 \pmod{8}.$$

于是

$$(x + y)^{13} \equiv 1^{13} \equiv 1 \pmod{8},$$$$2(x + y)^{13} \equiv 2 \cdot 1 \equiv 2 \pmod{8},$$$$2(x + y)^{13} + y - 1 \equiv 2 + 7 - 1 \equiv 8 \equiv 0 \pmod{8}.$$

故 $8$ 整除 $2(x+y)^{13}+y-1$。

数的表示与算法

日常生活用十进制写整数，但并非处处如此：计时用六十进制。计算机科学里则广泛使用二进制、八进制和十六进制。二进制只有 $0$ 和 $1$，正好对应布尔代数里的两个值，也对应集成电路里开关的通断。本节讨论不同进制下的表示及其关系，重点是计算机使用的二进制，并分析若干运算算法。

进制表示与进制转换

无论哪一种进制，整数都可以写成该进制底数的幂的线性组合。

定理进制展开定理

设 $b$ 是大于 $1$ 的整数。则每个正整数 $n$ 都可以唯一地写成

$$n=a_{k} b^{k}+a_{k-1} b^{k-1}+\cdots+a_{1} b+a_{0},$$

其中 $k$ 是非负整数，$a_0, a_1,\cdots, a_k$ 是小于 $b$ 的非负整数，且 $a_k \neq 0$。

证明

反复带余除法，得到 $n=bq_1+a_0$、$q_1=bq_2+a_1$ 等式，其中 $0\le a_i<b$。因为 $b\ge2$，正商严格递减，过程必终止。逐层代回便得到所写的展开，最后的非零商给出最高位。证明唯一性时，先模 $b$，两种展开的 $a_0$ 必相同；减去这个数字再除以 $b$，反复进行，所有位数及最高位都被唯一确定。零单独用数字零表示。

例如 $1024 = 1\times10^3+0\times10^2+2\times10^1+4\times10^0$。底数还限制每一位上能出现的数字：十进制里不能把 $10$ 写成一位，最大数字是 $9$。一般地，$b$ 进制里每一位最大是 $b-1$。因此二进制只有 $0$、$1$，八进制是 $0$ 到 $7$，十六进制是 $0$ 到 $15$。

标明进制时用下标。

记号进制下标

用 $_b$ 表示数的进制，其中 $b$ 是底数。

数本身不随写法改变。把 $121_{10}$ 换成任何别的进制，它仍然是十进制意义下的 $121$，只是数字串不同。

二进制、八进制与十六进制

二进制展开以 $2$ 为底，每一位是 $0$ 或 $1$。展开方式和上一小节相同。

例二进制转十进制

二进制展开为 $(101011111)_2$ 的整数，十进制是多少？

这个数有九位：

$$\begin{aligned} (101011111)_2 &= 1\times 2^8+0\times 2^7+1\times 2^6+0\times 2^5+1\times 2^4\\ &\qquad +1\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0 \\ &=351. \end{aligned}$$

八进制转十进制手续相同。十六进制需要十六个不同数字，通常用 $0$ 到 $9$ 以及 $A$ 到 $F$，其中 $A$ 到 $F$ 依次表示十进制的 $10$ 到 $15$。

例十六进制转十进制

求 $(2AE0B)_{16}$ 的十进制展开。

字母只是把两位十进制数塞进一位：

$$(2AE0B)_{16} = 2\times 16^4 + 10\times 16^3 + 14\times 16^2 + 0 \times 16^1 + 11 \times 16^0=175627.$$

每一位十六进制数字对应四位二进制。例如 $(1110\,0101)_2 = (E5)_{16}$，因为 $(1110)_2 = (E)_{16}$、$(0101)_2 = (5)_{16}$。一个字节是八位比特串，因此可以用两位十六进制写出。

进制转换

整数的进制转换

已经会在不同进制下写数，怎样从一种进制转到另一种？通用办法是先转回十进制，再转到目标进制。可以做得更直接：构造 $n$ 的 $b$ 进制展开时，反复用 $b$ 去除。先做

$$n = bq_{0} + a_{0},\qquad 0\le a_{0}<b.$$

余数 $a_0$ 就是 $n$ 在 $b$ 进制下最右边的一位。再用 $b$ 去除 $q_0$：

$$q_0 = bq_{1} + a_{1},\qquad 0\le a_{1}<b.$$

$a_1$ 是从右数第二位。一直做到商为零。数字从右到左依次出现。

例十进制转十六进制

求 $(177130)_{10}$ 的十六进制展开。

$$\begin{aligned} 177130 &= 16 \cdot 11070 + 10,\\ 11070 &= 16 \cdot 691 + 14,\\ 691 &= 16 \cdot 43 + 3,\\ 43 &= 16 \cdot 2 + 11,\\ 2 &= 16 \cdot 0 + 2. \end{aligned}$$

因此 $(177130)_{10} = (2B3EA)_{16}$。

对应伪代码如下。

算法 1 整数进制转换

Require: 非负整数 $n$ 与底数 $b>1$

Ensure: $n$ 在 $b$ 进制下的各位数字

1:$\text{digits} \gets$ 空列表

2:while $n > 0$ do

3:$\text{remainder} \gets n \bmod b$

4:把 $\text{remainder}$ 追加到 $\text{digits}$

5:$n \gets \left\lfloor n / b \right\rfloor$

6:end while

7:把 $\text{digits}$ 反转

8:return $\text{digits}$

小数的进制转换

上一算法只处理整数，小数部分要另做。把十进制浮点数转到 $b$ 进制的算法如下。

算法 2 浮点进制转换

Require: 非负实数 $\text{number}$ 与目标底数 $b>1$

Ensure: $\text{number}$ 的 $b$ 进制表示

1:$\text{integerPart} \gets \lfloor \text{number} \rfloor$

2:$\text{fractionalPart} \gets \text{number} - \text{integerPart}$

3:$\text{baseInteger} \gets$ $\text{integerPart}$ 的 $b$ 进制表示

4:$\text{baseFraction} \gets$ 空串

5:while $\text{fractionalPart} > 0$ do

6:$\text{fractionalPart} \gets \text{fractionalPart} \times b$

7:把 $\lfloor \text{fractionalPart} \rfloor$ 追加到 $\text{baseFraction}$

8:$\text{fractionalPart} \gets \text{fractionalPart} - \lfloor \text{fractionalPart} \rfloor$

9:end while

10:return $\text{baseInteger}$ 后接 $\text{baseFraction}$

例把 $12.375$ 转到二进制

把十进制浮点数 $12.375$ 转到二进制。

• 整数部分：$12_{10}=1100_2$。
• 小数部分：

$$\begin{aligned} 0.375 \times 2 &= 0.75 \rightarrow \text{整数部分为 }0, \\ 0.75 \times 2 &= 1.5 \rightarrow \text{整数部分为 }1, \\ 0.5 \times 2 &= 1 \rightarrow \text{整数部分为 }1. \end{aligned}$$

• 小数部分的二进制是 $.011$。

因此 $12.375_{10}$ 等于 $1100.011_{2}$。

一个数同时有整数和小数时，两部分分开转换，再拼回去。习题里会见到这类题。

二、八、十六进制之间的转换

二进制、八进制、十六进制之间的转换特别直接。

原因是这些底数都是 $2$ 的幂：$8=2^3$，$16=2^4$。

• 每位八进制数字对应三位二进制，因为 $8=2^3$。
• 每位十六进制数字对应四位二进制，因为 $16=2^4$。

因此只要按三位或四位分组，不必做复杂的除法。

例二进制与八、十六进制互转

求 $(11\,1110\,1011\,1100)_2$ 的八进制和十六进制展开，以及 $(765)_{8}$ 和 $(A8D)_{16}$ 的二进制展开。

把 $(11\,1110\,1011\,1100)_2$ 转成八进制时，从右往左每三位一组，最左边一组若不够三位就在前面补零。各组是 $011$、$111$、$010$、$111$、$100$，对应 $3$、$7$、$2$、$7$、$4$。因此 $(11\,1110\,1011\,1100)_2 = (37274)_8$。

十六进制同样处理，每四位一组：$0011$、$1110$、$1011$、$1100$，对应 $3$、$E$、$B$、$C$。因此 $(11\,1110\,1011\,1100)_2 = (3EBC)_{16}$。

反过来手续相同。二进制与十六进制互转时，若位数不是 $4$ 的倍数，用 $0$ 补齐。

进制转换本质上就是刚刚学过的除法与模运算。一般转换算法可以写成下面这个反复取余的版本，其中 $n$ 是待转换的数，$b$ 是目标底数。

算法 3 反复除法求进制展开

Require: 非负整数 $n$ 与底数 $b>1$

Ensure: 数字 $a_{k-1},\ldots,a_0$ 使得 $n=(a_{k-1}\ldots a_0)_b$

1:$q \gets n$

2:$k \gets 0$

3:while $q > 0$ do

4:$a_k \gets q \bmod b$

5:$q \gets \left\lfloor q / b \right\rfloor$

6:$k \gets k+1$

7:end while

8:return $(a_{k-1},\ldots,a_1,a_0)$

运算算法

下面讨论二进制下基本运算的算法。把两个 $n$ 位二进制整数写成

$$a=(a_{n-1}a_{n-2}\ldots a_1a_0)_2,\qquad b=(b_{n-1}b_{n-2}\ldots b_1b_0)_2.$$

加法算法

二进制加法可以模仿竖式：对应位与进位一起加。先加最右两位：

$$a_0 + b_0 = c_0 \cdot 2 + s_0,$$

其中 $s_0$ 是和的最右一位，$c_0$ 是进位，取值 $0$ 或 $1$。再加下一位和进位：

$$a_1 + b_1 + c_0 = c_1 \cdot 2 + s_1.$$

如此直到最后，$a_{n-1}+b_{n-1}+c_{n-2}$ 给出 $c_{n-1}\cdot 2+s_{n-1}$，和的最高位是 $s_n=c_{n-1}$。于是 $a+b=(s_n s_{n-1}\ldots s_1 s_0)_2$。以 $1011_2$ 加 $1101_2$ 为例，竖式为

$$\begin{array}{r} 1011_2 \\ +\,1101_2 \\ \hline 11000_2 \end{array}$$

逐步如下。

1. 最右位：$1+1=10_2$，写下 $0$，进位 $1$。
2. 下一位：$1+0+1=10_2$，写下 $0$，进位 $1$。
3. 再下一位：$0+1+1=10_2$，写下 $0$，进位 $1$。
4. 最高位：$1+1+1=11_2$，写下 $1$，再向左进位 $1$。
5. 把最后的进位写下。

结果是 $11000_2$。

伪代码如下。

算法 4 二进制加法

Require: $n$ 位整数 $a$ 与 $b$

Ensure: $a+b$ 的二进制展开

1:$c \gets 0$

2:for $j \gets 0$ to $n-1$ do

3:$d \gets \left\lfloor (a_j+b_j+c)/2 \right\rfloor$

4:$s_j \gets a_j+b_j+c-2d$

5:$c \gets d$

6:end for

7:$s_n \gets c$

8:return $(s_ns_{n-1}\ldots s_1s_0)_2$

时间复杂度为 $O(n)$，其中 $n$ 是输入的二进制位数。

证明

算法只有一层循环，迭代 $n$ 次，$n$ 是两个加数的位数。循环体内对每一位做常数次运算：把第 $j$ 位 $a_j+b_j$ 与进位 $c$ 相加，除以 $2$ 得到新进位 $d$，再减去 $2d$ 得到和的第 $j$ 位，最后把 $c$ 更新为 $d$。这些运算都是常数时间，每位执行一次，故整段循环对位数线性，总复杂度 $O(n)$。这里假定基本算术（加、除以 $2$、减）都是常数时间。

乘法算法

沿用同样的二进制写法，乘法是

$$\begin{aligned} a b & =a\left(b_{0} 2^{0}+b_{1} 2^{1}+\cdots+b_{n-1} 2^{n-1}\right) \\ & =a\left(b_{0} 2^{0}\right)+a\left(b_{1} 2^{1}\right)+\cdots+a\left(b_{n-1} 2^{n-1}\right). \end{aligned}$$

手续类似竖式：用第二个数的每一位去乘第一个数，再按位次左移后相加。

算法 5 二进制乘法

Require: $n$ 位整数 $a$ 与 $b$

Ensure: 乘积 $ab$

1:$\text{product} \gets 0$

2:for $j \gets 0$ to $n-1$ do

3:if $b_j = 1$ then

4:$\text{product} \gets \text{product} + a\cdot 2^j$

5:end if

6:end for

7:return $\text{product}$

例$(110)_2$ 乘 $(101)_2$

求 $a = (110)_2$ 与 $b = (101)_2$ 的乘积。先算

$$\begin{aligned} a \cdot b_0 \cdot 2^0 &= (110)_2 \cdot 1 \cdot 2^0 = (110)_2, \\ a \cdot b_1 \cdot 2^1 &= (110)_2 \cdot 0 \cdot 2^1 = (0000)_2, \\ a \cdot b_2 \cdot 2^2 &= (110)_2 \cdot 1 \cdot 2^2 = (11000)_2. \end{aligned}$$

把 $(110)_2$、$(0000)_2$、$(11000)_2$ 相加（位数不够时在前面补零），得到 $ab=(11110)_2$。

时间复杂度为 $O(n^2)$：$n$ 位与 $n$ 位相乘，每一位都要和另一数的每一位打交道，共 $n$ 组、每组 $n$ 次。

商与余数算法

下面的算法求 $a\div b$ 的商和余数，也能处理 $a$ 为负的情形。

算法 6 带余除法

Require: 整数 $a$ 与正整数 $b$

Ensure: 整数 $(q,r)$ 使得 $a=bq+r$ 且 $0\le r<b$

1:$q \gets \left\lfloor a/b \right\rfloor$

2:$r \gets a-bq$

3:return $(q,r)$

模幂算法

模运算的一个重要应用是高效计算 $b^n \bmod m$，密码学里经常需要。直接算 $b^n$ 可能大到不可接受，所以要用快速方法。把指数写成二进制 $n=(a_{k-1}\ldots a_1a_0)_2$，则

$$b^n=b^{a_{k-1}\cdot2^{k-1}+\cdots+a_1\cdot2+a_0}=b^{a_{k-1}\cdot2^{k-1}}\cdots b^{a_1\cdot2}\cdot b^{a_0}.$$

因此只需依次算出 $b$、$b^2$、$(b^2)^2=b^4$、$(b^4)^2=b^8$、$\ldots$、$b^{2^k}$，再把 $a_j=1$ 的那些 $b^{2^j}$ 乘起来。为了省时间和空间，每乘一次就模 $m$ 一次。

例计算 $4^9$

计算 $4^9$。注意 $9=(1001)_2$，故 $4^9=4^8\cdot 4^1$。连续平方：$4^2=16$，$4^4=16^2=256$，$4^8=(256)^2=65536$。于是 $4^9=4^8\cdot 4^1=65536\cdot 4=262144$。

有了求 $b^n$ 的骨架，就可以写求 $b^n\bmod m$ 的算法。

算法 7 快速模幂

Require: 整数 $b,n,m$，其中 $n\ge 0$、$m>0$

Ensure: $b^n \bmod m$

1:$x \gets 1$

2:$\text{power} \gets b \bmod m$

3:$\text{exponent} \gets n$

4:while $\text{exponent} > 0$ do

5:if $\text{exponent} \bmod 2 = 1$ then

6:$x \gets (x\cdot \text{power}) \bmod m$

7:end if

8:$\text{power} \gets (\text{power}\cdot \text{power}) \bmod m$

9:$\text{exponent} \gets \left\lfloor \text{exponent}/2 \right\rfloor$

10:end while

11:return $x$

例用算法求 $3^{644}\bmod 645$

用上述算法求 $3^{644} \bmod 645$。

算法先令 $x=1$、$power=3\bmod 645=3$，再反复平方并模 $645$，得到 $3^{2^j}\bmod 645$（$j=1,2,\ldots,9$）。当 $644$ 的二进制 $(1010000100)_2$ 的第 $j$ 位为 $1$ 时，把当前 $x$ 乘上 $3^{2^j}\bmod 645$ 再模 $645$。逐步如下。

步	计算
$i = 0$	$a_0 = 0$，故 $x = 1$，$power = 3^2 \bmod 645 = 9$
$i = 1$	$a_1 = 0$，故 $x = 1$，$power = 9^2 \bmod 645 = 81$
$i = 2$	$a_2 = 1$，故 $x = 1 \cdot 81 \bmod 645 = 81$，$power = 81^2 \bmod 645 = 111$
$i = 3$	$a_3 = 0$，故 $x = 81$，$power = 111^2 \bmod 645 = 66$
$i = 4$	$a_4 = 0$，故 $x = 81$，$power = 66^2 \bmod 645 = 486$
$i = 5$	$a_5 = 0$，故 $x = 81$，$power = 486^2 \bmod 645 = 126$
$i = 6$	$a_6 = 0$，故 $x = 81$，$power = 126^2 \bmod 645 = 396$
$i = 7$	$a_7 = 1$，故 $x = (81 \cdot 396) \bmod 645 = 471$，$power = 396^2 \bmod 645 = 81$
$i = 8$	$a_8 = 0$，故 $x = 471$，$power = 81^2 \bmod 645 = 111$
$i = 9$	$a_9 = 1$，故 $x = (471 \cdot 111) \bmod 645 = 36$

因此 $3^{644} \bmod 645 = 36$。

模幂算法的时间复杂度

循环次数等于指数 $n$ 的二进制位数。每轮做常数次模乘和模平方，故复杂度为 $O(\log n)$。朴素模幂是 $O(n)$，对数级改进在 RSA 这类指数很大的密码算法里至关重要。

证明

设指数为 $n$，其二进制位数为 $k$，即

$$n = \sum_{i=0}^{k-1} a_i \cdot 2^i,\qquad a_i \in \{0, 1\}.$$

算法从低位到高位扫描这些比特。每轮：若 $a_i=1$，就做一次模乘更新 $x$；无论 $a_i$ 是什么，都做一次模平方更新 $power$。模乘和模平方用模 $m$ 的常数次算术即可完成，视为 $O(1)$。总共 $k$ 轮，故时间与 $k$ 成正比。而 $k=\lfloor\log_2 n\rfloor+1=O(\log n)$，因此算法复杂度为 $O(\log n)$。

对数时间的快速模幂，比线性时间的朴素反复相乘高效得多。

素数与最大公因数

前面讲了整除、余数和模运算，这是数论最基础的一层。现在转向素数及其性质。素数并不陌生，幼儿园或小学就见过。下面讨论如何判定素数、如何分解，并进入素数的代数性质。这些都是密码学的地基。

素数及相关算法

先把定义写清楚。

定义素数

大于 $1$ 的整数 $p$，若其仅有的正因数是 $1$ 和 $p$，则称为素数。大于 $1$ 且不是素数的正整数称为合数。

按这个定义，$1$ 不是素数：它只有正因数 $1$。

素数令人着迷，是因为它有许多独特的性质，远不止定义本身。其中最核心的是算术基本定理。

定理算术基本定理

每个整数 $n>1$ 都可以唯一地分解成素数的乘积，不计因子次序。具体地，$n$ 可以写成

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k},$$

其中 $p_1 < p_2 < \ldots < p_k$ 是素数，$a_1, a_2, \ldots, a_k$ 是正整数。除次序外，这个分解唯一。

证明

分存在性和唯一性两部分。

存在性。 用数学归纳法证明每个大于 $1$ 的整数都能写成素数之积。

基础：$n=2$ 本身是素数。

归纳：假设命题对一切大于 $1$ 且小于 $n$ 的整数成立，考虑 $n$。若 $n$ 是素数，则它已经是素数之积。若 $n$ 不是素数，则可写成 $n=a\cdot b$，其中 $1<a,b<n$。由归纳假设，$a$ 与 $b$ 都能分解成素数之积，合在一起就得到 $n$ 的分解。存在性证完。

唯一性。 反设 $n$ 有两种不同的素因子分解：

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k} = q_1^{b_1} \cdot q_2^{b_2} \cdot \ldots \cdot q_m^{b_m},$$

其中 $p_i$、$q_j$ 为素数，$a_i$、$b_j$ 为正整数。接下来需要欧几里得引理。

引理（欧几里得）。 设 $p$ 为素数。若 $p$ 整除乘积 $ab$，则 $p$ 整除 $a$ 或 $p$ 整除 $b$。

引理的证明。 设素数 $p$ 整除 $ab$ 但不整除 $a$，要证 $p$ 整除 $b$。由于 $p$ 不整除 $a$，$\gcd(a,p)=1$。由贝祖恒等式，存在整数 $x$、$y$ 使得

$$ax + py = 1.$$

两边乘 $b$：

$$abx + pby = b.$$

（若这一步暂时读不顺，可先看完线性组合与贝祖定理再回来。）

$p$ 整除 $ab$，故整除 $abx$；显然也整除 $pby$。于是 $p$ 整除二者之和，即整除 $b$。这就证明了：若 $p$ 整除 $ab$ 且不整除 $a$，则 $p$ 整除 $b$。

回到唯一性。由欧几里得引理，素数若整除两个数的积，必整除其中至少一个。因此 $p_1$ 必须整除右端某个 $q_j$。但 $q_j$ 是素数，故 $p_1=q_j$。对称地反复使用这一论证，两套素因子必须完全相同，与“两种不同分解”矛盾。

因此大于 $1$ 的整数的素因子分解在不计次序时唯一。

例$100$ 的素因子分解

$100 = 2\cdot 2\cdot 5\cdot 5 = 2^2\cdot 5^2$，其中 $2$ 和 $5$ 都是素数。

知道素数重要之后，怎样又对又快地找出它们？最朴素的办法是逐个试：要判断 $n$ 是不是素数，从 $2$ 除到 $n-1$，谁整除 $n$，$n$ 就不是素数。

试除法

其实不必除到 $n-1$。下面这条定理把上界降到平方根。

定理试除上界

若 $n$ 是合数，则 $n$ 有一个不超过 $\sqrt{n}$ 的素因数。

证明

$n$ 是合数，故有因数 $a$ 满足 $1<a<n$，从而 $n=ab$，其中 $b>1$。下面说明 $a\le\sqrt{n}$ 或 $b\le\sqrt{n}$。若二者都大于 $\sqrt{n}$，则 $ab>\sqrt{n}\cdot\sqrt{n}=n$，矛盾。故 $n$ 有一个不超过 $\sqrt{n}$ 的正因数。这个因数要么本身是素数，要么（由算术基本定理）有更小的素因数。无论哪种，$n$ 都有不超过 $\sqrt{n}$ 的素因数。

判定手续的伪代码如下。

算法 8 试除素性判定

Require: 整数 $n>1$

Ensure: $n$ 是否为素数

1:if $n=2$ then

2:return true

3:end if

4:$d \gets 2$

5:while $d \le \sqrt n$ do

6:if $n \bmod d = 0$ then

7:return false

8:end if

9:$d \gets d+1$

10:end while

11:return true

例证明 $101$ 是素数

证明 $101$ 是素数。

不超过 $\sqrt{101}$ 的素数是 $2$、$3$、$5$、$7$。$101$ 不被它们任何一个整除，因此不是合数，也就是素数。

还需要把给定整数分解成素因子。试除分解如下。

算法 9 试除素因子分解

Require: 整数 $n>1$

Ensure: $n$ 的素因子

1:$\text{factors} \gets$ 空列表

2:$p \gets 2$

3:while $p^2 \le n$ do

4:while $n \bmod p = 0$ do

5:把 $p$ 追加到 $\text{factors}$

6:$n \gets n/p$

7:end while

8:$p \gets p+1$

9:end while

10:if $n>1$ then

11:把 $n$ 追加到 $\text{factors}$

12:end if

13:return $\text{factors}$

例分解 $8964$

求 $8964$ 的素因子分解。

1. $8964$ 是偶数，先除以 $2$：$8964\div 2=4482$。
2. $4482$ 仍是偶数：$4482\div 2=2241$。
3. $2241$ 不能被 $2$ 整除。依次试 $3$、$5$、$7$、$11$ 等，直到 $31$。
4. $2241\div 31=71$，而 $71$ 是素数。

因此 $8964=2\times 2\times 31\times 71$，或写成 $2^2\times 31\times 71$。

还有其他找素数或判定素性的方法。愿意深挖的话可以看 埃拉托斯特尼筛 和 阿特金筛。这只是一小部分；后面解同余时会遇到费马小定理，概率论里还会遇到蒙特卡洛方法。

最大公因数与最小公倍数

再回到小学就见过的最大公因数和最小公倍数。先写定义。

定义最大公因数

设 $a$、$b$ 为不全为零的整数。同时整除 $a$ 和 $b$ 的最大整数 $d$ 称为它们的最大公因数，记作 $\gcd(a,b)$。

例计算两个 gcd

求 $\gcd(12,24)$ 和 $\gcd(17,22)$。

能同时整除 $12$ 和 $24$ 的最大正整数是 $6$，故 $\gcd(12,24)=6$。$17$ 与 $22$ 除 $1$ 外没有公因数，故 $\gcd(17,22)=1$。

$\gcd(17,22)=1$ 时，称这两个数互质。

可以把互质推广到两两互质。

定义两两互质

整数 $a_1,a_2,\ldots,a_n$ 称为两两互质，如果每当 $1\le i<j\le n$ 时都有 $\gcd(a_i,a_j)=1$。

例如 $9$、$16$、$23$ 两两互质，因为 $\gcd(9,16)=\gcd(9,23)=\gcd(16,23)=1$。一列整数两两互质，当且仅当任意两个不同项的最大公因数都是 $1$。

也可以用素因子分解求 gcd。设正整数 $a$、$b$ 的素因子分解为

$$a=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n},\qquad b=p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n},$$

其中指数是非负整数；某个素数若只出现在一边，另一边指数取 $0$。则

$$\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_n^{\min(a_n,b_n)},$$

其中 $\min(x,y)$ 表示 $x$ 与 $y$ 中较小的那个。右边这个整数整除 $a$ 也整除 $b$，因为每个素数的指数都不超过 $a$、$b$ 两边的指数；再增大任何一个指数，或加入新的素数，就会不再同时整除两边。因此它就是最大公因数。

例用分解求 $\gcd(100,250)$

$$\gcd(100,250)=2^{\min(2,1)}5^{\min(2,3)}=2\cdot5^2=50.$$

同一套素因子方法给出最小公倍数。算术基本定理保证每个大于 $1$ 的整数都有唯一的素因子分解。

定义最小公倍数

正整数 $a$、$b$ 的最小公倍数是同时被 $a$ 和 $b$ 整除的最小正整数，记作 $\operatorname{lcm}(a,b)$。

仍设

$$a = p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n},\qquad b = p_1^{b_1} p_2^{b_2} \ldots p_n^{b_n}.$$

乘积 $ab$ 的素因子分解是

$$ab = p_1^{a_1+b_1} p_2^{a_2+b_2} \ldots p_n^{a_n+b_n}.$$

任何公倍数在每个素数上的指数，都必须至少达到 $a$、$b$ 两边的较大者。因此

$$\operatorname{lcm}(a, b) = p_1^{\max(a_1,b_1)} p_2^{\max(a_2,b_2)} \ldots p_n^{\max(a_n,b_n)}.$$

它被 $a$ 和 $b$ 整除，而且是满足这一性质的最小正整数。

例求 $\operatorname{lcm}(120,500)$

$$\operatorname{lcm}(120,500)=2^{\max(2,3)}3^{\max(1,0)}5^{\max(1,3)} = 8\times 3 \times 125= 3000.$$

注意到 $ab$ 恰好等于 $\operatorname{lcm}(a,b)$ 与 $\gcd(a,b)$ 的乘积：在 $ab$ 的分解里每个指数都是两边指数之和，无论谁大谁小，都有 $\max+\min=$ 两边之和。对 $120$ 和 $500$，

$$ab = 120\times 500 = 60000 = \operatorname{lcm}(a,b)\times \gcd(a,b) = 3000\times 20.$$

定理gcd 与 lcm 的乘积恒等式

设 $a$、$b$ 为正整数。则 $ab= \gcd(a, b)\cdot\operatorname{lcm}(a, b)$。

证明

对每个素数 $p$，设它在 $a,b$ 中的指数为 $u,v$，允许为零。gcd 中的指数为 $\min(u,v)$，lcm 中为 $\max(u,v)$，两者之和为 $u+v$，恰为 $ab$ 中的指数。唯一素因子分解便证明乘积相等。

欧几里得算法

对整数 $a\ge b>0$，写 $a=qb+r$，其中 $0\le r<b$。正整数同时整除 $a,b$，当且仅当同时整除 $b,r$：一个方向用 $r=a-qb$，另一个方向用 $a=qb+r$。因此

$$\gcd(a,b)=\gcd(b,r).$$

反复更新 $(a,b)\leftarrow(b,r)$。只要还需下一次除法，非负余数就严格减小，故必终止。最后一对为 $(d,0)$，其 gcd 是 $d$；不变量保证这也是原来的 gcd。带符号输入先取绝对值，一项为零时直接返回另一项的绝对值。逐层反代这些除法等式，就把 $d$ 写成原始输入的整数线性组合，得到下一节的贝祖恒等式。

每次取余都保持最大公因数不变，最后一个非零余数就是答案。

作为线性组合的最大公因数

两个整数 $a$、$b$ 的最大公因数可以写成

$$sa + tb,$$

其中 $s$、$t$ 为整数。也就是说，$\gcd(a,b)$ 是 $a$ 与 $b$ 的整系数线性组合。这正是贝祖定理。

定理贝祖恒等式

设 $a$、$b$ 为不全为零的整数。存在整数 $x$、$y$ 使得

$$ax + by = \gcd(a, b).$$

$x$、$y$ 叫做贝祖系数，等式 $\gcd(a,b)=sa+tb$ 叫做贝祖恒等式。

证明

对非零整数 $a$、$b$，用 $b$ 除 $a$ 得到余数 $r_1$，满足 $0\le r_1<|b|$，且 $\gcd(a,b)=\gcd(b,r_1)$。反复做带余除法：

$$\begin{aligned} a&=bx_1+r_1,&& 0<r_1<|b|,\\ b&=r_1x_2+r_2,&& 0<r_2<r_1,\\ &\vdots\\ r_{n-1}&=r_n x_{n+1}+r_{n+1},&& 0<r_{n+1}<r_n,\\ r_n&=r_{n+1}x_{n+2}. \end{aligned}$$

$r_{n+1}$ 是最后一个非零余数。用倒数第二个等式把 $r_{n+1}$ 解成 $r_n$ 与 $r_{n-1}$ 的组合，再往回代，依次消掉中间余数，最终把 $r_{n+1}$ 写成 $a$ 与 $b$ 的线性组合。而最后一个非零余数正是 $\gcd(a,b)$，这就是贝祖恒等式。更细的写法见 贝祖引理。

注贝祖恒等式与丢番图方程

贝祖定理与线性丢番图方程关系密切，解线性同余时还会用到。

欧几里得算法是递归的：求 $\gcd(a,b)$ 要多次调用同一手续。下面用例子把步骤写开。

例用欧几里得算法求 $\gcd(1022,400)$

用欧几里得算法求 $1022$ 与 $400$ 的最大公因数。

$$\begin{aligned} 1022&=2\times400+222,\\ 400&=1\times 222+178,\\ 222&=1\times 178+44,\\ 178&=4\times 44+2,\\ 44&=22\times2+0. \end{aligned}$$

于是 $\gcd(1022,400)=2$。把这些式子逐步反代，就是扩展欧几里得算法。中间项都能用更前面的式子表示，最后得到 gcd 关于 $1022$ 与 $400$ 的线性组合：$2 = 23\times 400-9\times 1022$。

换一种问法：求整数 $a$、$b$ 使得 $\gcd(1022,400)=a\times 1022+b\times 400$。手续完全一样，立刻得到 $a=-9$、$b=23$。下一节解线性同余时，还会看到与这等价的第三种写法。

解同余方程

本章从整除出发，定义了除法、模运算和同余，并看到同余的许多代数性质几乎是在“抄”普通算术。学实数时，运算熟了就开始用字母代替具体数字，那就是代数。同余既然共享这么多基本性质，能不能也做方程？本节只解线性同余，而欧几里得算法会再次成为主要工具。

线性同余

定义线性同余

形如

$$ax \equiv b \pmod{m}$$

的同余叫做线性同余，其中 $a,b,m\in\mathbb{Z}^{+}$，$x$ 是未知数。为了解它，需要找到 $\bar{a}$，称为 $a$ 模 $m$ 的逆，满足 $a\bar{a}\equiv 1\pmod{m}$。

解会是什么样？同余有周期性，所以若有解，就会有无穷多个。

定理模逆的存在与唯一性

若 $a$ 与 $m$ 互质且 $m>1$，则 $a$ 模 $m$ 的逆存在，并且在模 $m$ 的意义下唯一。也就是说，存在唯一的正整数 $\bar{a}$ 是 $a$ 模 $m$ 的逆，而其余的逆都与 $\bar{a}$ 模 $m$ 同余。

证明

由贝祖定理，$\gcd(a,m)=1$ 给出整数 $s$、$t$ 使得 $sa+tm=1$。于是 $sa+tm\equiv 1\pmod{m}$。而 $tm\equiv 0\pmod{m}$，故 $sa\equiv 1\pmod{m}$，即 $s$ 是 $a$ 模 $m$ 的一个逆。

再证唯一性。设另有 $x$ 满足 $xa\equiv 1\pmod{m}$，且 $x\not\equiv s\pmod{m}$。则 $xa\equiv sa\pmod{m}$，故 $m\mid xa-sa$，即 $x-s$ 是 $m$ 的倍数，从而 $x\equiv s\pmod{m}$，与假设矛盾。因此在模 $m$ 下逆唯一。

例求 $101$ 模 $5000$ 的一个逆

求 $101$ 模 $5000$ 的一个逆。

先用欧几里得算法说明 $\gcd(101,5000)=1$，再反代求出贝祖系数 $a$、$b$ 使得 $101a+5000b=1$，则 $a$ 就是所求的逆。欧几里得步骤为

$$\begin{aligned} 5000 &= 49 \cdot 101 + 51, \\ 101 &= 1 \cdot 51 + 50, \\ 51 &= 1 \cdot 50 + 1, \\ 50 &= 50 \cdot 1. \end{aligned}$$

最后一个非零余数是 $1$，故 $\gcd(101,5000)=1$。往回代：

$$\begin{aligned} 1 &= 51 - 1 \cdot 50 \\ &= 51 - 1 \cdot (101 - 1 \cdot 51) \\ &= 2 \cdot 51 - 101 \\ &= 2 \cdot (5000 - 49 \cdot 101) - 101 \\ &= 2 \cdot 5000 - 99 \cdot 101. \end{aligned}$$

由 $-99\cdot 101 + 2\cdot 5000 = 1$ 可知 $-99$ 是 $101$ 模 $5000$ 的一个逆。

例解 $101x\equiv 3\pmod{5000}$

线性同余 $101x \equiv 3 \pmod {5000}$ 的解是什么？

已知 $-99$ 是 $101$ 模 $5000$ 的逆。两边同乘这个逆：

$$-99 \cdot 101x \equiv -99\cdot 3 \pmod {5000}.$$

左边 $\equiv x$，故 $x\equiv -99\cdot 3 \pmod{5000}$。解不是单个数，而是一整类：$x=-297,-5293,4703,\ldots$。通解写成 $x=x_0+km$，其中 $k$ 为任意整数，$x_0$ 是任何一个特解。

到此，只要同余可解（存在逆），线性同余都能解。前面一直假定 $\gcd(a,m)=1$。不互质时会怎样？

线性同余其实是更大一类方程的特例：丢番图方程。

定义丢番图方程

丢番图方程是要求未知数取整数的多项式方程或方程组，以亚历山大的丢番图命名。一般可以写成

$$a_{1}x_{1}^{b_{1}}+a_{2}x_{2}^{b_{2}}+\cdots+a_{n}x_{n}^{b_{n}}=c,$$

其中系数、指数、未知数和右端都在整数里。

一般的丢番图方程很难，解往往无穷多。最简单的线性情形是

$$ax+by=c.$$

这正是贝祖定理里出现的形状。求一对整数与它们 gcd 的线性关系，和解线性同余是同一件事：后者是前者的子问题。

下面给出通解。考虑

$$ax + by = c,$$

其中 $a$、$b$、$c$ 已知，$x$、$y$ 待求。

第一步：特解。 由扩展欧几里得算法，存在 $x_0$、$y_0$ 使得 $ax_0+by_0=\gcd(a,b)$。

第二步：通解形状。 若 $c$ 是 $\gcd(a,b)$ 的倍数，设 $c=k\cdot\gcd(a,b)$，则 $ax_0k+by_0k=c$ 给出一个特解。对任意整数 $t$，

$$a\bigl(x_0k + t b/d\bigr) + b\bigl(y_0k - t a/d\bigr) = c,$$

其中 $d=\gcd(a,b)$。加在 $x$ 上的 $b/d$ 倍与减在 $y$ 上的 $a/d$ 倍，乘上 $a$、$b$ 后恰好抵消。

第三步：通解。

$$x = kx_0 + t\left(\frac{b}{d}\right),\qquad y = ky_0 - t\left(\frac{a}{d}\right),$$

其中 $t$ 为任意整数，$d=\gcd(a,b)$。若 $a$、$b$ 互质，解集仍然无穷。

推论线性丢番图方程何时有解

若 $\gcd(a,b)=1$，则方程对任意整数 $c$ 都有整数解，因为 $1$ 整除一切整数。若 $c$ 不是 $\gcd(a,b)$ 的倍数，则没有整数解。一般地，当 $\gcd(a,b)\mid c$ 时有整数解。

有了丢番图方程，线性同余可以立刻对上。

命题把线性同余化成丢番图方程

解线性同余是解线性丢番图方程的子问题。求 $c=sa+tb$ 等价于解这个丢番图方程，也等价于求 $ax\equiv c\pmod{b}$。

证明

$ax\equiv c\pmod{b}$ 表示 $ax\bmod b=c\bmod b$。由带余除法，$ax=q_1b+r$、$c=q_2b+r$，于是 $c-q_2b=ax-q_1b$，即 $c=ax+(q_2-q_1)b$，其中 $q_2-q_1\in\mathbb{Z}$。因此解线性同余就是解一个丢番图方程。

例解 $400z\equiv 8\pmod{1022}$

解 $400z\equiv 8 \pmod{1022}$。

直接当成丢番图方程 $8=400x+1022y$。先用扩展欧几里得算法求 gcd：

$$\begin{aligned} 1022&=2\times400+222,\\ 400&=1\times 222+178,\\ 222&=1\times 178+44,\\ 178&=4\times 44+2,\\ 44&=22\times2+0. \end{aligned}$$

由贝祖定理反代得到 $2=23\times 400-9\times 1022$。$8$ 是 $2$ 的倍数，故 $8=-36\times 1022+92\times 400$，特解为 $x=92$、$y=-36$。通解为

$$\begin{aligned} x&=k\cdot 92+t\left(\frac{1022}{\gcd(400,1022)}\right),\\ y&=k\cdot(-36)+t\left(\frac{400}{\gcd(400,1022)}\right). \end{aligned}$$

中国剩余定理

上一小节把线性同余对应到单个线性方程。现在对应到方程组。回忆：线性方程组是关于同一批未知数的若干线性方程。

定义线性方程组

在实数里，$n$ 个未知数 $x_1,x_2,\ldots,x_n$ 的 $n$ 个线性方程可以写成

$$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2 \\ \vdots &\\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &= b_n, \end{aligned}$$

其中 $a_{ij}$、$b_i$ 为实数。

注“线性”指什么

“线性”是指多项式次数不超过 $1$。

定义线性同余方程组

类似地，线性同余方程组是同一批未知数上、在不同模下的若干线性同余。$n$ 个未知数的 $n$ 个线性同余可以写成

$$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\equiv b_1 \pmod{m_1} \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\equiv b_2 \pmod{m_2} \\ \vdots &\\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &\equiv b_n \pmod{m_n}, \end{aligned}$$

其中 $a_{ij}$、$b_i$、$m_i$ 为整数。目标是同时满足所有方程或同余的未知数取值。

一般情形需要矩阵和线性代数。和丢番图方程一样，这里只处理一种基本形状，对应的定理就是中国剩余定理。公元一世纪，孙子问：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

写成同余组就是

$$\begin{aligned} x&\equiv2\pmod{3},\\ x&\equiv3\pmod{5},\\ x&\equiv2\pmod{7}. \end{aligned}$$

求这种组的解的算法，就是中国剩余定理。

定理中国剩余定理

设 $m_1,m_2,\ldots,m_n$ 是大于 $1$ 且两两互质的正整数，$a_1,a_2,\ldots,a_n$ 是任意整数。则方程组

$$\begin{aligned} x&\equiv a_1\pmod{m_1}\\ x&\equiv a_2 \pmod{m_2}\\ \vdots&\\ x&\equiv a_n \pmod{m_n} \end{aligned}$$

模 $M=m_1m_2\cdots m_n$ 有唯一解。也就是说，存在解 $x$ 满足 $0\le x<M$，而其余解都与这个解模 $M$ 同余。

证明

需要证明解存在，并且模 $M$ 唯一。存在性通过构造给出。

存在性。 对 $k=1,2,\ldots,n$，令

$$M_k = \frac{M}{m_k} = m_1m_2 \cdots m_{k-1}m_{k+1} \cdots m_n,$$

即除 $m_k$ 以外所有模的乘积。当 $i\neq k$ 时 $m_i$ 与 $m_k$ 没有大于 $1$ 的公因数，故 $\gcd(m_k,M_k)=1$。由贝祖恒等式，存在 $y_k$、$z_k$ 使得 $M_ky_k+m_kz_k=1$，从而 $M_ky_k\equiv 1\pmod{m_k}$，$y_k$ 是 $M_k$ 模 $m_k$ 的逆。构造

$$x = a_1M_1y_1 + a_2M_2y_2 + \cdots + a_nM_ny_n.$$

当 $j\neq k$ 时 $M_j\equiv 0\pmod{m_k}$，故和式中除第 $k$ 项外都模 $m_k$ 同余于 $0$。又 $M_ky_k\equiv 1\pmod{m_k}$，于是

$$x \equiv a_kM_ky_k \equiv a_k \pmod{m_k},\qquad k=1,2,\ldots,n.$$

因此 $x$ 同时满足全部 $n$ 个同余。

模 $M$ 的唯一性。 设 $x$ 与 $x'$ 都是解。则对每个 $k$，$x\equiv a_k\pmod{m_k}$ 且 $x'\equiv a_k\pmod{m_k}$，从而 $x\equiv x'\pmod{m_k}$。因为 $m_1,\ldots,m_n$ 两两互质，故 $x\equiv x'\pmod{M}$，其中 $M=m_1m_2\cdots m_n$。

例用公式解孙子问题

解

$$\begin{aligned} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{5} \\ x &\equiv 2 \pmod{7}, \end{aligned}$$

其中 $m_1=3$、$m_2=5$、$m_3=7$ 两两互质。

由中国剩余定理，

$$x \equiv a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3 \pmod{m_1m_2m_3},$$

其中 $M_i=m_1m_2m_3/m_i$，且 $M_iy_i\equiv 1\pmod{m_i}$。计算得

$$\begin{aligned} x&\equiv a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+a_{3}M_{3}y_{3}\\ & =2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1 \\ &=233\equiv23\pmod{105}. \end{aligned}$$

$x\equiv 23\pmod{105}$ 是最小的正整数，被 $3$ 除余 $2$，被 $5$ 除余 $3$，被 $7$ 除余 $2$。

这是一般公式，但求模逆并不总是轻松，规模一大计算也不理想。下面用回代作为捷径。

例用回代解同一组同余

仍解

$$\begin{aligned} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{5} \\ x &\equiv 2 \pmod{7}. \end{aligned}$$

由同余定义，$x\equiv 2\pmod{3}$ 即 $x=3i+2$。代入第二条：$3i+2\equiv 3\pmod{5}$，两边减 $2$ 得 $3i\equiv 1\pmod{5}$。于是 $i$ 是 $3$ 模 $5$ 的逆，最小正整数解是 $i=2$，即 $i\equiv 2\pmod{5}$。再写 $i=5j+2$，代入 $x=3i+2$ 得 $x=15j+8$。再代入第三条：$15j+8\equiv 2\pmod{7}$。因为 $8\equiv 1\pmod{7}$，故 $15j\equiv 1\pmod{7}$。于是 $j$ 是 $15$ 模 $7$ 的逆，最小正整数是 $1$，即 $j\equiv 1\pmod{7}$。再写 $j=7k+1$，代入 $x=15j+8$ 得 $x=15(7k+1)+8$，即

$$x = 105k + 23,$$

也就是 $x\equiv 23\pmod{105}$。这正是该同余组的解。

注回代为什么可行

回代的关键是：用系数的模逆去乘线性同余的两边，把未知数单独留下，再模 $m$ 读出它的值。

费马小定理

费马小定理以法国数学家皮埃尔·德·费马命名，他在 $1640$ 年陈述了这一结果。它是数论的基本定理，在密码学、计算机科学和其他领域都有大量应用：把很大的幂先模一个素数再算，往往能把计算量压下来。

定理费马小定理

设 $p$ 为素数，$a$ 为不被 $p$ 整除的整数。则

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

也就是说，把 $a$ 的 $p-1$ 次幂除以 $p$，余数总是 $1$。

前面用快速模幂计算 $b^n\bmod m$。费马小定理提供另一条路，有时更快。

证明

设 $p$ 为素数，$a$ 不被 $p$ 整除。考虑集合 $\{1,2,\ldots,p-1\}$，把每个元素乘以 $a$ 再模 $p$。这个操作是该集合的一个置换：若 $ax\equiv ay\pmod{p}$，则 $a(x-y)\equiv 0\pmod{p}$，而 $p$ 不整除 $a$，故 $x\equiv y\pmod{p}$。

因此 $\{a\cdot 1,a\cdot 2,\ldots,a\cdot(p-1)\}$ 模 $p$ 后正好是 $\{1,2,\ldots,p-1\}$ 的重排。两边所有元素相乘：

$$\prod_{i=1}^{p-1} (a \cdot i) \equiv \prod_{i=1}^{p-1} i \pmod{p},$$

即

$$a^{p-1} \prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1} i \pmod{p}.$$

$\prod_{i=1}^{p-1} i$ 不被 $p$ 整除，可以约掉，得到 $a^{p-1}\equiv 1\pmod{p}$。

下表帮助看清定理在说什么。取 $p=7$，表中行号是 $a$，列号是指数 $b$，格中是 $a^b\bmod 7$。每隔 $6$ 列就会出现整列都满足 $a^b\equiv 1\pmod{7}$ 的情形，而 $6=p-1$。

$a \backslash b$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$2$	$1$	$2$	$4$	$1$	$2$	$4$	$1$
$3$	$1$	$3$	$2$	$6$	$4$	$5$	$1$
$4$	$1$	$4$	$2$	$1$	$4$	$2$	$1$
$5$	$1$	$5$	$4$	$6$	$2$	$3$	$1$
$6$	$1$	$6$	$1$	$6$	$1$	$6$	$1$

例用费马小定理计算 $3^{100}\bmod 7$

用费马小定理计算 $3^{100} \pmod{7}$。

解先降指数再算余数

先核对条件：$7$ 是素数，$3$ 不被 $7$ 整除。由费马小定理，$3^{7-1}\equiv 1\pmod{7}$，即 $3^6\equiv 1\pmod{7}$。于是

$$\begin{aligned} 3^{100} &= (3^6)^{16} \cdot 3^4 \\ &\equiv 1^{16} \cdot 3^4 \pmod{7} \\ &\equiv 1 \cdot 81 \pmod{7} \\ &\equiv 4 \pmod{7}. \end{aligned}$$

因此 $3^{100}\equiv 4\pmod{7}$。

步骤可以再拆开：$7$ 是素数且 $7\nmid 3$，故 $3^6\equiv 1\pmod{7}$。把指数写成 $100=6\cdot 16+4$，于是 $3^{100}=(3^6)^{16}\cdot 3^4$。前一段变成 $1^{16}=1$，后一段 $81\equiv 4\pmod{7}$，相乘仍得 $4$。

练习gcd 与两个线性同余是否可解

用欧几里得算法求 $504$ 与 $385$ 的最大公因数，并考虑：

• 是否存在整数 $y$ 使得 $504y \equiv 10 \pmod{385}$？若存在，找出一个；若不存在，说明原因。
• 是否存在整数 $z$ 使得 $504z \equiv 7 \pmod{385}$？若存在，找出一个；若不存在，说明原因。

解扩展欧几里得算法

$$\begin{aligned} 504 & =1\times 385+119,\\ 385 & =3\times 119+28,\\ 119 & =4\times 28+7,\\ 28 & =4\times 7+0. \end{aligned}$$

故 $\gcd(504,385)=7$。解线性同余等价于解线性丢番图方程，即求

$$\begin{aligned} 10 &=504x+385y,\\ 7 &= 504x+385y. \end{aligned}$$

同余 $504z \equiv 7 \pmod{385}$ 可先换成 $119z \equiv 7 \pmod{385}$，因为 $504\equiv 119\pmod{385}$。$\gcd(119,385)=7$ 整除 $7$，故有解。两边除以 $7$ 得 $17z\equiv 1\pmod{55}$。试验 $17$ 的倍数，发现 $17\cdot 13\equiv 1\pmod{55}$，故 $z=13$ 是一个解。

第一个方程没有整数解，因为 $7\nmid 10$。

通解仍用前面的公式：

$$\begin{cases} x = k \times x_0 + t \bigl(385/\gcd(504,385)\bigr),\\ y = k \times y_0 + t \bigl(504/\gcd(504,385)\bigr), \end{cases}$$

其中 $x_0$、$y_0$ 是一组特解。把扩展欧几里得的各行反代，得到 $\gcd(504,385)=13\times 504-17\times 385$。于是当方程有解时，

$$\begin{cases} x = k \times 13 + t \bigl(385/\gcd(504,385)\bigr),\\ y = k \times (-17) + t \bigl(504/\gcd(504,385)\bigr) \end{cases}$$

就是通解。