數系與數論初步（進階）：在時鐘上重新發明算術——環、單位與二次剩餘

當「除法」失去意義：在時鐘上重新發明算術

入門篇裡，我們從數羊一路走到守護密碼的質數。但有一件事被刻意輕輕帶過：當我們說「$7$ 在模 $12$ 之下等於 $7$，而 $19$ 也等於 $7$」時，我們其實已經偷偷拋棄了整個整數系統，改用一套全新的數來運算。這套新的數不是「比較小的整數」，而是整數的等價類（equivalence class）。

這個轉變看似只是換個說法，卻是整個近代數論的引擎。一旦我們認真看待「模 $n$ 之下的世界」這個物件——數學家寫成 $\mathbb{Z}/n\mathbb{Z}$——許多在入門篇只能「觀察到」的現象，會突然有了結構性的解釋。為什麼某些 $n$ 之下每個非零元素都能做除法，某些卻不能？為什麼費馬小定理（Fermat's little theorem）長那個樣子？RSA 為什麼真的能解密回去？這些問題的答案，全都藏在「模 $n$ 的世界長什麼形狀」裡。

這篇進階文章，我們就把入門篇沒拆開的引擎蓋掀開來看。

模 $n$ 的世界是一個「環」

先把語言定下來。固定一個正整數 $n$。我們說兩個整數 $a, b$ 同餘（congruent）模 $n$，記作

$$a \equiv b \pmod{n} \iff n \mid (a - b).$$

這個關係把所有整數分成 $n$ 個互不相交的「桶子」：餘數為 $0$ 的、餘數為 $1$ 的、……、餘數為 $n-1$ 的。每個桶子是一個剩餘類（residue class），記作 $\overline{a}$ 或 $[a]_n$。全部 $n$ 個桶子的集合就是

$$\mathbb{Z}/n\mathbb{Z} = \{\overline{0}, \overline{1}, \dots, \overline{n-1}\}.$$

關鍵在於：加法與乘法可以「下放」到桶子之間。如果 $a \equiv a'$ 且 $b \equiv b'$，那麼必然 $a+b \equiv a'+b'$ 且 $ab \equiv a'b'$。這個性質叫做良定義（well-defined），它讓我們可以直接寫 $\overline{a} + \overline{b} = \overline{a+b}$ 而不必擔心選了哪個代表元。

帶著這兩個運算，$\mathbb{Z}/n\mathbb{Z}$ 成為一個交換環（commutative ring）：有加法、有乘法、有 $0$ 與 $1$、加法可逆、乘法滿足分配律。這是入門篇沒明說的事——「模算術」不只是一個技巧，它是一個完整的代數系統。

誰能做除法？單位、零因子與 $\gcd$

在普通整數裡，除法幾乎總是失敗（$3 \div 2$ 不是整數）。在 $\mathbb{Z}/n\mathbb{Z}$ 裡，情況反而更微妙也更有趣：有些元素能除，有些不能，而且有明確的判準。

我們說 $\overline{a}$ 是一個單位（unit），如果存在 $\overline{x}$ 使得 $\overline{a}\,\overline{x} = \overline{1}$，也就是 $\overline{x}$ 是 $\overline{a}$ 的乘法反元素。「能除以 $\overline{a}$」精確地就是「$\overline{a}$ 是單位」。

判準非常乾淨：

$$\overline{a} \text{ 是單位} \iff \gcd(a, n) = 1.$$

證明的核心是入門篇可能提過的裴蜀定理（Bézout's identity）：$\gcd(a,n)=1$ 當且僅當存在整數 $u, v$ 使得 $au + nv = 1$。把這個式子模 $n$ 看，$nv$ 消失，剩下 $au \equiv 1 \pmod n$，於是 $\overline{u}$ 就是 $\overline{a}$ 的反元素。反過來，若 $au \equiv 1$，則 $au - 1 = nv$，逼出 $\gcd(a,n) \mid 1$。

那些不是單位的非零元素，命運更慘——它們是零因子（zero divisor）。例如在 $\mathbb{Z}/12\mathbb{Z}$ 裡，$\overline{3} \cdot \overline{4} = \overline{12} = \overline{0}$，但 $\overline{3}, \overline{4}$ 都不是零。零因子的存在正是「模 $12$ 不是個好世界」的根源：你不能放心地約分，因為 $\overline{3}\,\overline{x} = \overline{3}\,\overline{y}$ 不能推出 $\overline{x} = \overline{y}$。

這就回答了一個結構性問題：$\mathbb{Z}/n\mathbb{Z}$ 是一個體（field，每個非零元素都可逆）若且唯若 $n$ 是質數。 因為質數 $p$ 與所有 $1 \le a \le p-1$ 都互質，所以每個非零剩餘類都是單位。這個體記作 $\mathbb{F}_p$，是有限體（finite field）最基本的例子，也是橢圓曲線密碼學、編碼理論、雜湊設計的地基。

看一個例子：在 $\mathbb{Z}/26\mathbb{Z}$ 裡解密

考慮一個玩具型仿射密碼（affine cipher），加密是 $E(x) = 5x + 8 \pmod{26}$。要解密，必須對 $5$ 求模 $26$ 的反元素。

用擴展歐幾里得演算法（extended Euclidean algorithm）：

$$26 = 5 \cdot 5 + 1 \implies 1 = 26 - 5 \cdot 5.$$

模 $26$ 之下，$1 \equiv -5 \cdot 5 \equiv 21 \cdot 5 \pmod{26}$，所以 $5^{-1} \equiv 21 \pmod{26}$（驗證：$5 \cdot 21 = 105 = 4 \cdot 26 + 1$）。於是解密函數是

$$D(y) = 21\,(y - 8) \pmod{26}.$$

注意：如果有人不小心把乘數選成 $13$（而 $\gcd(13,26)=13 \ne 1$），那麼 $13$ 在 $\mathbb{Z}/26\mathbb{Z}$ 裡是零因子，根本沒有反元素，密碼會把不同明文壓到同一個密文上，無法解密。判準 $\gcd(a,n)=1$ 在這裡不是抽象條件，而是「這套密碼能不能用」的生死線。

歐拉函數與費馬—歐拉定理

單位的個數有個專屬名字：歐拉函數（Euler's totient）

$$\varphi(n) = \#\{\,1 \le a \le n : \gcd(a, n) = 1\,\}.$$

這些單位在乘法下構成一個群，記作 $(\mathbb{Z}/n\mathbb{Z})^\times$，階為 $\varphi(n)$。

歐拉函數有漂亮的乘性結構。若 $n = p_1^{e_1} \cdots p_k^{e_k}$ 是質因數分解，則

$$\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right).$$

例如 $\varphi(60) = 60 \cdot (1-\tfrac12)(1-\tfrac13)(1-\tfrac15) = 60 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 16.$

接下來是整個 RSA 的心臟——歐拉定理：若 $\gcd(a,n)=1$，則

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

它是費馬小定理 $a^{p-1} \equiv 1 \pmod p$（當 $p \nmid a$）的推廣。為什麼成立？因為 $\overline{a}$ 是有限群 $(\mathbb{Z}/n\mathbb{Z})^\times$ 中的一個元素，而拉格朗日定理（Lagrange's theorem）保證：任何元素的階（order，即使 $\overline{a}^k = \overline{1}$ 成立的最小 $k$）都整除群的階 $\varphi(n)$。設這個階為 $d$，則 $d \mid \varphi(n)$，於是 $a^{\varphi(n)} = (a^d)^{\varphi(n)/d} \equiv 1$。

這正是入門篇「RSA 解密真的會解回去」那句話背後缺的那一塊推導。在 RSA 中，$n = pq$，$\varphi(n) = (p-1)(q-1)$，公鑰 $e$ 與私鑰 $d$ 滿足 $ed \equiv 1 \pmod{\varphi(n)}$，於是

$$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod n.$$

（嚴格說，$\gcd(m,n)\ne 1$ 的少數情形要靠中國剩餘定理另外處理，結論仍成立。）

中國剩餘定理：把大世界拆成小世界

當 $n$ 不是質數時，$\mathbb{Z}/n\mathbb{Z}$ 看似混亂，但中國剩餘定理（Chinese Remainder Theorem, CRT）給了它一個分解結構。若 $n = n_1 n_2$ 且 $\gcd(n_1, n_2) = 1$，則有環同構

$$\mathbb{Z}/n\mathbb{Z} \;\cong\; \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z}.$$

意思是：在模 $n$ 之下算一個東西，等同於在模 $n_1$ 與模 $n_2$ 之下各算一份，再用 CRT 拼回去。這不只是理論優雅——RSA 的實作幾乎都用 CRT 加速解密，把對 $n=pq$ 的一次大冪運算，拆成模 $p$ 與模 $q$ 的兩次小冪運算，速度約快四倍。

動手試試：用 CRT 求解聯立同餘

找一個 $x$ 同時滿足

$$x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5, \qquad x \equiv 2 \pmod 7.$$

模數兩兩互質，$n = 3 \cdot 5 \cdot 7 = 105$。標準做法：

• 對第一式，$M_1 = 105/3 = 35$，求 $35^{-1} \pmod 3$。因 $35 \equiv 2 \pmod 3$，而 $2 \cdot 2 = 4 \equiv 1$，故反元素為 $2$。貢獻項 $2 \cdot 35 \cdot 2 = 140$。
• 對第二式，$M_2 = 105/5 = 21$，$21 \equiv 1 \pmod 5$，反元素 $1$。貢獻項 $3 \cdot 21 \cdot 1 = 63$。
• 對第三式，$M_3 = 105/7 = 15$，$15 \equiv 1 \pmod 7$，反元素 $1$。貢獻項 $2 \cdot 15 \cdot 1 = 30$。

加總 $140 + 63 + 30 = 233 \equiv 233 - 2\cdot105 = 23 \pmod{105}$。驗證：$23 = 7\cdot3+2$（餘 $2$）、$23 = 4\cdot5+3$（餘 $3$）、$23 = 3\cdot7+2$（餘 $2$），全部符合。答案是 $x \equiv 23 \pmod{105}$。

這個演算法的精神是：在每個小模數裡「只負責自己」，靠 $M_i$ 在其他模數下歸零來達到「互不干擾」。

哪些數開得了平方根？二次剩餘

進到一個入門篇通常不碰、但極其重要的主題：在模 $p$ 之下，方程式 $x^2 \equiv a \pmod p$ 何時有解？

我們稱有解的 $a$（且 $p \nmid a$）為模 $p$ 的二次剩餘（quadratic residue, QR），無解的為非二次剩餘。對奇質數 $p$，恰好有 $\frac{p-1}{2}$ 個 QR 與 $\frac{p-1}{2}$ 個非 QR。

勒讓德符號（Legendre symbol）把這件事編碼成 $\pm 1$：

$$\left(\frac{a}{p}\right) = \begin{cases} +1 & a \text{ 是 QR} \\ -1 & a \text{ 是非 QR} \\ 0 & p \mid a.\end{cases}$$

它可由歐拉判準（Euler's criterion）計算：

$$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.$$

理由再次是群論：$(\mathbb{Z}/p\mathbb{Z})^\times$ 是循環群（cyclic group），平方映射 $x \mapsto x^2$ 的像恰好是指數為偶數的元素，正好占一半，而 $a^{(p-1)/2}$ 是 $+1$ 還是 $-1$ 正好偵測這件事。

這個主題的皇冠是高斯（Gauss）的二次互反律（quadratic reciprocity）：對相異奇質數 $p, q$，

$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$

它的驚人之處在於：「$p$ 是不是模 $q$ 的平方」與「$q$ 是不是模 $p$ 的平方」這兩件表面無關的事，竟然被一條公式緊緊綁住。高斯一生給了八種證明，至今已知超過兩百種。

二次剩餘不是純粹的好奇心：它是 Rabin 密碼系統、二次篩法（quadratic sieve，目前大數分解的主力之一）、以及許多偽隨機數產生器的核心。

重點回顧

• $\mathbb{Z}/n\mathbb{Z}$ 是一個環，其元素是整數的等價類，加法與乘法良定義；這是模算術的真正身分。
• $\overline{a}$ 可逆 $\iff \gcd(a,n)=1$；非單位的非零元素是零因子。$\mathbb{Z}/n\mathbb{Z}$ 是體 $\iff n$ 為質數。
• 歐拉定理 $a^{\varphi(n)}\equiv 1$ 來自拉格朗日定理（元素階整除群階），是費馬小定理的推廣，也是 RSA 正確性的基礎。
• 中國剩餘定理 把 $\mathbb{Z}/n\mathbb{Z}$ 分解為互質模數的乘積，既是理論工具也是 RSA 加速的實作關鍵。
• 二次剩餘與互反律 回答「誰開得了平方根」，由勒讓德符號與歐拉判準刻畫，是現代分解演算法與密碼系統的核心。

深入探討（研究所視角）

把視野拉到研究所層級，會發現以上一切都是更大圖景的「$\bmod\ p$ 切片」。

從有限到 $p$-adic。 我們做的是「模 $p$、模 $p^2$、模 $p^3$……」逐層逼近。把這些剩餘環沿著自然投影 $\mathbb{Z}/p^{k+1}\mathbb{Z} \to \mathbb{Z}/p^k\mathbb{Z}$ 取反極限（inverse limit），就得到 $p$-adic 整數環

$$\mathbb{Z}_p = \varprojlim_k \mathbb{Z}/p^k\mathbb{Z}.$$

在 $\mathbb{Z}_p$ 裡，「接近」的意思是「差被 $p$ 的高次方整除」，於是 $\mathbb{Z}$ 多了一種與實數完全不同的拓樸與絕對值 $|\cdot|_p$。奧斯特洛夫斯基定理（Ostrowski's theorem）告訴我們：$\mathbb{Q}$ 上本質不同的絕對值只有實數的那個與每個質數的 $p$-adic 那個——這是「為什麼質數這麼特別」的最深刻回答之一。亨澤爾引理（Hensel's lemma）則讓「模 $p$ 的解」能不能「升級」成 $\mathbb{Z}_p$ 的解，變成一個可機械檢查的條件，二次剩餘的層級結構在此一覽無遺。

從 $\mathbb{Z}/p\mathbb{Z}$ 到一般有限體。 $\mathbb{F}_p$ 只是有限體的起點。對每個質數冪 $q = p^k$，存在唯一（同構意義下）的 $q$ 元有限體 $\mathbb{F}_q$，它是 $\mathbb{F}_p$ 的代數擴張，乘法群 $\mathbb{F}_q^\times$ 仍是循環群。橢圓曲線密碼學（ECC）正是在 $\mathbb{F}_q$ 上的曲線點群裡運作——同樣的「離散對數困難」假設，但用更短的金鑰達到 RSA 等級的安全性。

結構抽象化：理想與商環。 $\mathbb{Z}/n\mathbb{Z}$ 其實是商環 $\mathbb{Z}/(n)$，其中 $(n)$ 是 $\mathbb{Z}$ 的一個理想（ideal）。「$n$ 是質數 $\iff$ 商是體」這件事，抽象化為「在主理想整環中，$(n)$ 是極大理想 $\iff$ 是質理想 $\iff n$ 不可約」。把整數換成數體中的整數環 $\mathcal{O}_K$（如 $\mathbb{Z}[i]$ 高斯整數），質因數分解可能失效，但理想的唯一分解仍成立——這正是代數數論（algebraic number theory）的起點，也是當年為解費馬最後定理而誕生的工具。費馬小定理、二次互反律、CRT，在這個框架下全都升級為更一般的定理（如類體論中的阿廷互反律）。

一句話收束：入門篇教你「整數可以模 $n$」，進階篇告訴你「模 $n$ 之後得到的是一個有形狀、有對稱、可分解的代數宇宙」，而研究所的工作，是去描繪這些宇宙彼此之間的地圖。