同餘與運算的良定義性

代數常把若干舊對象視為等價，借此構造新對象。只有運算不依賴暗中選擇的代表元時，這種構造才有效。整數同餘類為學習這種證明技巧提供了具體場所，再將其用於抽象商結構。

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]$。在有零因子的環中，非零不足以保證乘法消去。

總結

等價類把代表元視為無法區分。其上的運算和映射必須檢查良定義性。同餘算術具體展示加法群、環、單位和域，而最大公因數控制逆元及一次同餘式的可解性。