同余与运算的良定义性

代数常把若干旧对象视为等价，借此构造新对象。只有运算不依赖暗中选择的代表元时，这种构造才有效。整数同余类为学习这种证明技巧提供了具体场所，再将其用于抽象商结构。

1 等价类

集合上的关系 $\sim$ 若自反、对称且传递，则称为等价关系。类 $[a]$ 包含所有与 $a$ 等价的元素。两个类要么相同，要么不相交：若有共同元素，传递性便连接两个代表元。因此等价类划分原集合。

固定整数 $n\ge2$。当 $n$ 整除 $a-b$ 时，定义 $a\equiv b\pmod n$。该关系自反，因为 $n\mid0$；对称，因为整除性在取负后保持；传递，因为整除性在相加后保持。带余除法说明恰有 $n$ 个类，由 $0,\ldots,n-1$ 表示。类的集合是 $\mathbb Z/n\mathbb Z$。

定义 $[a]+[b]=[a+b]$ 和 $[a][b]=[ab]$。这需要证明定义良好。若 $a'=a+rn$、$b'=b+sn$，则 $a'+b'-(a+b)=n(r+s)$，且

$$a'b'-ab=n(rb+sa+rsn).$$

两个差都被 $n$ 整除，因此所得类不依赖代表元。对非负整数次幂反复相乘，也可知幂运算保持同余。

相比之下，拟议的运算 $[a]/[b]=[a/b]$ 在没有额外条件时没有意义：$a/b$ 未必是整数，分母类也未必可逆。

2 一个例子中的群、整环与域

在加法下，这些类构成阿贝尔群：零为单位元，$[-a]$ 是逆元，结合律从整数加法继承。配上乘法，它们构成含单位元 $[1]$ 的交换环。非零类可以是零因子，即与另一个非零类相乘得到零。在 $\mathbb Z/8\mathbb Z$ 中，$[2][4]=[0]$。

单位是有乘法逆元的类。

单位判据。 模 $n$ 的 $[a]$ 是单位当且仅当 $\gcd(a,n)=1$。

证明。 若最大公因数为 1，Bézout 等式给出整数 $u,v$ 满足 $ua+vn=1$，故 $[u][a]=[1]$。反之若 $[u][a]=[1]$，则 $ua-1$ 被 $n$ 整除，所以 $a,n$ 的每个公因数都整除 1。$\square$

Bézout 等式本身来自欧几里得算法：反复除法保持整数线性组合的集合，回代将最后一个非零余数，即最大公因数，表示为这样的组合。

例如 $1=3\cdot7-2\cdot10$，所以模 10 下 $[7]^{-1}=[3]$。模素数 $p$ 时，每个非零类与 $p$ 互素，因此都是单位：$\mathbb Z/p\mathbb Z$ 是域。合数模数则不然：若 $n=ab$ 且 $1<a,b<n$，非零类 $[a],[b]$ 相乘为零。

3 求解一次同余式

同余式 $ax\equiv b\pmod n$ 可解当且仅当 $d=\gcd(a,n)$ 整除 $b$。必要性来自 $ax-b=kn$ 蕴含 $d\mid b$。充分性则将 Bézout 等式 $ua+vn=d$ 乘以 $b/d$ 得到一个解。

若一个解为 $x_0$，则所有解模 $n$ 相差 $n/d$ 的倍数。事实上，$a(x-x_0)$ 被 $n$ 整除当且仅当 $(a/d)(x-x_0)$ 被 $n/d$ 整除；互素性允许消去。模 $n$ 恰有 $d$ 个解类。

对于 $6x\equiv8\pmod{14}$，$d=2$ 整除 8。约去得 $3x\equiv4\pmod7$，而 3 模 7 的逆元为 5，故 $x\equiv6\pmod7$。模 14 的两个类为 6 和 13，直接代入可验证。

同余论证所复用的完整整数证明

在此整数证明中，$\mathbb N$ 表示 $\{0,1,2,\ldots\}$。下面的除法、最大公因数不变性、终止性及系数更新论证给出上文所用的 Bézout 结论，并包含带符号及零输入情形。

定理

除法算法

设 $a,b\in\mathbb Z$ 且 $b\ne0$。则存在唯一整数 $q,r$ 使得

$$a=bq+r,\qquad 0\le r\lt|b|.$$

$q$ 称为商，$r$ 称为余数。

条件 $0\le r\lt|b|$ 不是附加装饰，而是唯一性的核心。例如

$$17=5\cdot3+2$$

符合除法算法；但

$$17=5\cdot2+7$$

不符合，因为余数 $7$ 不小于 $5$。

先证明存在性。设 $a\ge0$、$b>0$，考虑

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}.$$

因为 $a\in S$，良序原理给出最小成员 $r=a-bq$。若 $r\ge b$， 则 $r-b=a-b(q+1)$ 是更小的非负成员，矛盾。因此 $0\le r\lt b$。 若 $a\lt0$、$b>0$，则 $A=a+(-a)b=(-a)(b-1)$ 非负。 用已证情形写成 $A=bQ+r$，整理得 $a=b(Q+a)+r$，余数范围不变。 若 $b\lt0$，先用正除数 $B=|b|$，再把商 $Q$ 换成 $-Q$。 所有符号情形都不需要负余数。

再证明唯一性。设 $a=bq+r=bq'+r'$，两个余数都在规定范围内。 于是 $b(q-q')=r'-r$，但 $|r'-r|\lt|b|$。$b$ 的非零整数倍 绝对值至少是 $|b|$，故 $r'=r$。再由 $b\ne0$ 得 $q'=q$。 严格上界保证唯一性；仅要求余数非负并不足够。

定理

最大公因数的一步不变性

若 $a=bq+r$，则

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

证明: 保留整个共同因数集合

目标是证明两个最大公因数相等。先证明更强的中间命题，论证会更直接： 整数 $h$ 同时整除 $a,b$，当且仅当它同时整除 $b,r$。 正向用 $r=a-bq$，反向用 $a=bq+r$，两者都用整数线性组合的整除性质。

输入不同时为零时，两个因数集合相同，所以最大元素相同。若 $a=b=0$， 则 $r=0$，两边按约定都是 $0$。这个恒等式本身不要求余数范围； 余数范围的作用是保证算法向前推进。

概念视角算法

不变量与递减计算

每次替换 $(a,b)\mapsto(b,r)$，最大公因数保持不变，余数则变小。 两者各有作用：不变性保证最后答案就是原本的最大公因数，严格递减则保证 计算会结束。先取输入的绝对值，把较大的正数放在前面；若另一输入是零， 立即停止。其余每次带余除法都使用正除数。

算法必然停止，因为余数形成严格递减的非负整数列：

$$r_1>r_2>r_3>\cdots\ge0.$$

非负整数不可能无限地严格递减。

倒代也可整理成向前更新的系数。对正输入设 $r_0=a$、$r_1=b$， 保存 $r_k=s_ka+t_kb$，初始系数为 $(s_0,t_0)=(1,0)$、 $(s_1,t_1)=(0,1)$。若 $r_{k+2}=r_k-q_{k+1}r_{k+1}$，则

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

代入两个已知线性组合即可证明更新式。系数始终是整数，最后非零余数那一行 便给出最大公因数所需的系数。

定理

Bézout 恒等式

对任意整数 $a,b$，存在整数 $x,y$ 使得

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

对带符号的非零输入，先用 $|a|,|b|$ 计算，再把原本符号吸收到系数中。 若一项为零，用 $|a|=a\operatorname{sgn}(a)$ 或 $b$ 的对应等式； 若两项皆零，取 $x=y=0$。这样便证明恒等式的全部情形。

输入不同时为零时，最大公因数也是最小的正整数线性组合。恒等式保证它 确实是一个组合；其他正组合都是它的正倍数，不可能更小。若输入是 $(0,0)$， 则没有正组合。

4 分级练习

E1 基础。 列出模 12 的单位，并指出一个非零零因子。

E2 同余式。 求解 $4x\equiv6\pmod{10}$ 和 $4x\equiv5\pmod{10}$。

E3 良定义性。 $f([a]_6)=[a]_3$ 定义了函数吗？$g([a]_3)=[a]_6$ 呢？

E4 证明。 在整环中，证明 $ab=ac$ 且 $a\ne0$ 蕴含 $b=c$。解释为什么在 $\mathbb Z/8\mathbb Z$ 中消去律失效。

5 完整解答

S1. 单位是 $[1],[5],[7],[11]$，即与 12 互素的类。例如 $[3]$ 是零因子，因为 $[3][4]=[0]$ 且两个因子均非零。

S2. 第一个化为 $2x\equiv3\pmod5$，故 $x\equiv4\pmod5$：模 10 下为类 4 和 9。第二个无解，因为 $\gcd(4,10)=2$ 不整除 5。

S3. $f$ 是：被 6 整除的差也被 3 整除。$g$ 不是：$[0]_3=[3]_3$，但 $[0]_6\ne[3]_6$，所以一个输入会有两个输出。

S4. $a(b-c)=0$，没有零因子迫使 $b-c=0$。模 8 时，$[2][1]=[2][5]$，虽然 $[1]\ne[5]$，因为 $[2][4]=[0]$。在有零因子的环中，非零不足以保证乘法消去。

总结

等价类把代表元视为无法区分。其上的运算和映射必须检查良定义性。同余算术具体展示加法群、环、单位和域，而最大公因数控制逆元及一次同余式的可解性。