§1
数论研究整数的结构，是离散数学中最古老也最"实用"的分支：现代密码学、哈希函数、校验码、随机数生成，底层几乎都是同余运算。本章从带余除法出发，经欧几里得算法与裴蜀定理建立最大公约数理论，再进入同余的代数世界，最后给出费马小定理与中国剩余定理两件利器。
一、整除与带余除法
定义（整除）. 设 $a,b$ 为整数且 $a\ne0$。若存在整数 $q$ 使 $b=aq$，称 $a$ 整除 $b$，记 $a\mid b$，此时 $a$ 是 $b$ 的因子。基本性质：若 $a\mid b$ 且 $a\mid c$，则对任意整数 $x,y$ 有 $a\mid(bx+cy)$；整除具有传递性。
定理（带余除法）. 对任意整数 $a$ 与正整数 $b$，存在唯一的一对整数 $q,r$ 使
$$a=bq+r,\qquad 0\le r $q$ 称为商，$r$ 称为余数，记 $r=a\bmod b$。存在性来自取 $q=\lfloor a/b\rfloor$；唯一性用反证：若 $bq_{1}+r_{1}=bq_{2}+r_{2}$ 且两余数都在 $[0,b)$ 内，则 $b\mid(r_{1}-r_{2})$，而 $\lvert r_{1}-r_{2}\rvert
二、最大公约数与欧几里得算法
定义. 不全为零的整数 $a,b$ 的公因子中最大者称最大公约数，记 $\gcd(a,b)$。若 $\gcd(a,b)=1$，称 $a,b$ 互素。
关键引理. 若 $a=bq+r$，则 $\gcd(a,b)=\gcd(b,r)$。
证明：任一 $b,r$ 的公因子整除 $bq+r=a$，故是 $a,b$ 的公因子；反之任一 $a,b$ 的公因子整除 $a-bq=r$。两组公因子集合相同，最大者自然相同。
欧几里得算法. 反复用上式把问题规模缩小，直到余数为零：
$$\gcd(a,b)\to\gcd(b,\ a\bmod b)\to\cdots\to\gcd(d,0)=d.$$
余数严格递减且非负，故算法必然终止；步数为 $O(\log\min(a,b))$，最坏情形出现在相邻斐波那契数。
裴蜀定理. 存在整数 $s,t$ 使 $\gcd(a,b)=sa+tb$。把欧几里得算法的每一步余数逐层回代即可求出 $s,t$，这称为扩展欧几里得算法。推论：$a,b$ 互素当且仅当存在 $s,t$ 使 $sa+tb=1$，这也是求模逆元的方法。
三、同余
定义. 设 $m$ 为正整数。若 $m\mid(a-b)$，称 $a$ 与 $b$ 模 $m$ 同余，记 $a\equiv b\pmod m$。由关系一章已知这是等价关系，把 $\mathbb{Z}$ 划分为 $m$ 个剩余类 $[0],[1],\dots,[m-1]$。
运算性质. 若 $a\equiv b$ 且 $c\equiv d\pmod m$，则
$$a+c\equiv b+d,\qquad a-c\equiv b-d,\qquad ac\equiv bd\pmod m.$$
于是可在运算的任何中间步骤取模，这是快速幂能高效工作的根本原因。
消去律要小心. 由 $ac\equiv bc\pmod m$ 一般不能推出 $a\equiv b$；只有 $\gcd(c,m)=1$ 时才可消去。例如 $2\cdot3\equiv2\cdot0\pmod 6$，但 $3\not\equiv0\pmod 6$。若 $\gcd(a,m)=1$，由裴蜀定理存在 $s$ 使 $sa\equiv1\pmod m$，称 $s$ 为 $a$ 的模逆元。
四、费马小定理与欧拉定理
费马小定理. 设 $p$ 为素数，$a$ 为不被 $p$ 整除的整数，则
$$a^{p-1}\equiv1\pmod p.$$
证明思路. 考虑 $a,2a,\dots,(p-1)a$ 模 $p$ 的余数。由 $\gcd(a,p)=1$ 与消去律，这 $p-1$ 个余数两两不同且都非零，故恰是 $1,2,\dots,p-1$ 的一个排列。两边连乘得 $a^{p-1}(p-1)!\equiv(p-1)!\pmod p$，因 $\gcd((p-1)!,p)=1$，消去即得结论。
欧拉定理（推广）. 若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv1\pmod m$，其中 $\varphi(m)$ 是不超过 $m$ 且与 $m$ 互素的正整数个数。$m=p$ 时 $\varphi(p)=p-1$，退回费马小定理。RSA 加密的正确性正建立在此。
五、中国剩余定理（简述）
定理. 设 $m_{1},\dots,m_{k}$ 两两互素，$M=m_{1}m_{2}\cdots m_{k}$，则同余方程组
$$x\equiv a_{1}\pmod{m_{1}},\quad\dots,\quad x\equiv a_{k}\pmod{m_{k}}$$
在模 $M$ 意义下有唯一解。构造法：令 $M_{i}=M/m_{i}$，取 $M_{i}$ 的模 $m_{i}$ 逆元 $t_{i}$，则
$$x\equiv\sum_{i=1}^{k}a_{i}M_{i}t_{i}\pmod M.$$
因为 $m_{j}\mid M_{i}$（$j\ne i$），求和式模 $m_{i}$ 时只剩第 $i$ 项 $a_{i}M_{i}t_{i}\equiv a_{i}$，逐个条件均满足。
| 定理 | 条件 | 结论 | 典型用途 |
|---|---|---|---|
| 带余除法 | $b>0$ | $q,r$ 唯一 | 一切算法的基础 |
| 裴蜀定理 | $a,b$ 不全为零 | $\gcd=sa+tb$ | 求模逆元 |
| 费马小定理 | $p$ 素数，$p\nmid a$ | $a^{p-1}\equiv1$ | 快速幂化简、素性测试 |
| 中国剩余定理 | 模两两互素 | 模 $M$ 唯一解 | 并行计算、大数分解 |
六、例题与解答
例题1（欧几里得算法）
用欧几里得算法求 $\gcd(1071,462)$，并写成 $1071s+462t$ 的形式。
解： 反复带余除法：
| 步骤 | 算式 | 余数 |
|---|---|---|
| 1 | $1071=2\times462+147$ | $147$ |
| 2 | $462=3\times147+21$ | $21$ |
| 3 | $147=7\times21+0$ | $0$ |
余数为零时的除数即答案：$\gcd(1071,462)=21$。回代求裴蜀系数：
$$ \begin{align*} 21&=462-3\times147\\ &=462-3\times(1071-2\times462)\\ &=7\times462-3\times1071. \end{align*} $$
验证：$7\times462=3234$，$3\times1071=3213$，差为 $21$。✓ 故 $s=-3,\ t=7$。
例题2（费马小定理算幂）
计算 $3^{100}\bmod 7$。
解： $7$ 为素数且 $7\nmid3$，由费马小定理 $3^{6}\equiv1\pmod 7$。把指数按 $6$ 作带余除法得 $100=6\times16+4$，于是
$$3^{100}=(3^{6})^{16}\cdot3^{4}\equiv1^{16}\cdot3^{4}=81\equiv4\pmod 7,$$
最后一步用 $81=7\times11+4$。直接验证小指数：$3^{1}\equiv3,\ 3^{2}\equiv2,\ 3^{3}\equiv6,\ 3^{4}\equiv4,\ 3^{5}\equiv5,\ 3^{6}\equiv1$，周期确为 $6$，第 $4$ 项为 $4$。✓ 若硬算 $3^{100}$ 是一个 $48$ 位大数，可见定理把指数从 $100$ 降到 $4$ 的威力。
例题3（中国剩余定理）
解方程组 $x\equiv2\pmod 3$，$x\equiv3\pmod 5$，$x\equiv2\pmod 7$。
解： 模两两互素，$M=105$，$M_{1}=35,\ M_{2}=21,\ M_{3}=15$。求逆元：$35\equiv2\pmod 3$ 而 $2\times2\equiv1$，故 $t_{1}=2$；$21\equiv1\pmod 5$，$t_{2}=1$；$15\equiv1\pmod 7$，$t_{3}=1$。代入
$$x\equiv2\times35\times2+3\times21\times1+2\times15\times1=140+63+30=233\pmod{105},$$
而 $233=2\times105+23$，故 $x\equiv23\pmod{105}$。验证：$23=3\times7+2$、$23=5\times4+3$、$23=7\times3+2$，三条同余全部满足。✓
练习
1. 用欧几里得算法求 $\gcd(252,198)$，并求 $5$ 在模 $12$ 下的逆元。
2. 计算 $2^{50}\bmod 11$。
3. 说明为什么 $ac\equiv bc\pmod m$ 不能随意消去 $c$；再解方程组 $x\equiv1\pmod 4$，$x\equiv2\pmod 5$。
参考答案.
1. $252=1\times198+54$；$198=3\times54+36$；$54=1\times36+18$；$36=2\times18+0$，故 $\gcd=18$。又 $\gcd(5,12)=1$，$5\times5=25=2\times12+1$，故 $5^{-1}\equiv5\pmod{12}$。
2. $11$ 为素数，$2^{10}\equiv1\pmod{11}$。$50=10\times5$，故 $2^{50}\equiv1^{5}=1\pmod{11}$。
3. 因为 $c$ 与 $m$ 可能有公因子，此时 $c$ 在模 $m$ 下不可逆；可消去的充要条件是 $\gcd(c,m)=1$，一般只能推出 $a\equiv b\pmod{m/\gcd(c,m)}$。方程组：$M=20$，$M_{1}=5,\ M_{2}=4$，$t_{1}=1$（$5\equiv1\bmod4$），$t_{2}=4$（$4\times4=16\equiv1\bmod5$），$x\equiv5+32=37\equiv17\pmod{20}$，验证 $17=4\times4+1$、$17=5\times3+2$。
本章小结
- 带余除法 $a=bq+r$（$0\le r
- 欧几里得算法基于 $\gcd(a,b)=\gcd(b,a\bmod b)$，步数为对数级。
- 裴蜀定理 $\gcd(a,b)=sa+tb$ 由扩展欧几里得给出，可用来求模逆元。
- 同余是等价关系，加减乘可保持，消去律仅在 $\gcd(c,m)=1$ 时成立。
- 费马小定理 $a^{p-1}\equiv1\pmod p$ 把大指数降为小指数；欧拉定理是其一般形式。
- 中国剩余定理在模两两互素时给出模 $M$ 的唯一解，构造式由各模的逆元拼装。
本章互动演示见页面底部交互图（欧几里得算法步骤演示 euclidViz）。
互动演示
拖动下方控件观察动态过程。