跳轉到

07.1 整除與同餘：Gauss 算術研究 1801 開創的整數世界#

0. 導言：為什麼「餘數」值得寫成一本書#

1801 年，24 歲的 Carl Friedrich Gauss 出版了《算術研究》（Disquisitiones Arithmeticae）。在這本書的第三節，他引進了一個看似平凡的記號：

\[a \equiv b \pmod{m}\]

這個記號的力量在於：它把「無限的整數世界」壓縮成「有限的剩餘類世界」，使得原本零散的整除性質，搖身一變成為一套有加法、有乘法、有結構的代數系統。可以說，同餘是離散數學通往抽象代數的第一座橋。本章的前因是第 3 章的整數歸納法與良序原理，後果則是 07.2 的尤拉定理，以及 07.3 的現代公開金鑰密碼學。

歷史驅動關係：Gauss 為了證明二次互反律而發展同餘語言 → 同餘催生有限群、有限體 → Galois（1832）用這些結構解開五次方程之謎 → 這些結構在 1976–1977 年被 Diffie–Hellman 與 RSA 拿來加密網路時代的訊息。

1. 整除性：一切的起點#

定義 1.1（整除）#

設 \(a, b \in \mathbb{Z}\) ， \(a \neq 0\) 。若存在整數 \(q\) 使得 \(b = qa\) ，則稱 ** \(a\) 整除 \(b\) **，記作 \(a \mid b\) ；否則記作 \(a \nmid b\) 。

定理 1.2（帶餘除法，Division Algorithm）#

設 \(a \in \mathbb{Z}\) ， \(d \in \mathbb{Z}^+\) ，則存在唯一的整數 \(q, r\) 使得

\[a = qd + r, \qquad 0 \le r < d.\]

證明（良序原理）。 考慮集合 \(S = \{a - qd \mid q \in \mathbb{Z},\ a - qd \ge 0\}\) 。取 \(q = a\) （ \(d \ge 1\) 時 \(a - ad = a(1-d) \ge 0\) 當 \(a \ge 0\) ； \(a < 0\) 時取 \(q\) 為某夠小的整數），可知 \(S \neq \varnothing\) 。由良序原理， \(S\) 有最小元素 \(r\) ，即 \(r = a - qd \ge 0\) 。若 \(r \ge d\) ，則 \(a - (q+1)d = r - d \ge 0\) 且更小，矛盾。故 \(0 \le r < d\) 。唯一性：若 \(a = qd + r = q'd + r'\) ，則 \((q - q')d = r' - r\) ，右邊絕對值小於 \(d\) ，故 \(q = q'\) 、 \(r = r'\) 。 \(\blacksquare\)

要點：這是「前因後果」的第一環——良序原理（前因）→ 帶餘除法（本節）→ 同餘的良定義性（後果）。

範例 1.3#

Python 中 % 就是帶餘除法的餘數（注意：Python 對負數取餘的符號跟隨除數，與數學慣例一致）：

def divmod_check(a, d):
    q, r = divmod(a, d)          # 帶餘除法
    assert a == q * d + r and 0 <= r < d
    return q, r

print(divmod_check( 17, 5))   # (3, 2)
print(divmod_check(-17, 5))   # (-4, 3)  ← 注意不是 (-3, -2)

整除的基本性質#

設 \(a \mid b\) 且 \(a \mid c\) ，則：

  1. \(a \mid (bx + cy)\) 對任意 \(x, y \in \mathbb{Z}\) （線性組合）。
  2. 若 \(b \mid c\) 則 \(a \mid c\) （傳遞性）。
  3. 若 \(a \mid b\) 且 \(b \mid a\) ，則 \(a = \pm b\) 。

定理 1.4（Bézout 恆等式）#

設 \(a, b \in \mathbb{Z}\) 不全為零， \(g = \gcd(a, b)\) ，則存在 \(x, y \in \mathbb{Z}\) 使

\[ax + by = g.\]

證明（輾轉相除 + 擴展）。 由帶餘除法反覆執行：

\[a = q_1 b + r_1,\quad b = q_2 r_1 + r_2,\quad \dots,\quad r_{n-2} = q_n r_{n-1} + r_n,\quad r_{n-1} = q_{n+1} r_n.\]

則 \(r_n = \gcd(a, b)\) 。且每個 \(r_i\) 都是 \(a, b\) 的線性組合（對 \(i\) 歸納： \(r_1 = a - q_1 b\) ；若 \(r_{i-2}, r_{i-1}\) 皆為線性組合，則 \(r_i = r_{i-2} - q_i r_{i-1}\) 也是）。 \(\blacksquare\)

Bézout 恆等式是「可逆性」的來源： \(\gcd(a, m) = 1 \iff\) 存在 \(x\) 使 \(ax \equiv 1 \pmod m\) 。這正是 07.3 中 RSA 私鑰 \(d\) 存在的原因。

def ext_gcd(a, b):
    """回傳 (g, x, y) 使 a*x + b*y = g = gcd(a, b)"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

g, x, y = ext_gcd(240, 46)
print(f"240*({x}) + 46*({y}) = {240*x + 46*y}")   # 240*(-9) + 46*(47) = 2

2. 同餘：Gauss 的壓縮技術#

定義 2.1（同餘）#

設 \(m \in \mathbb{Z}^+\) 。若 \(m \mid (a - b)\) ，則稱 \(a\) 與 \(b\) 模 \(m\) 同餘，記作 \(a \equiv b \pmod m\) 。

定理 2.2（同餘是等價關係）#

對任意 \(a, b, c \in \mathbb{Z}\) 與 \(m \in \mathbb{Z}^+\) ：

  1. 反身性： \(a \equiv a \pmod m\) ；
  2. 對稱性： \(a \equiv b \Rightarrow b \equiv a\) ；
  3. 傳遞性： \(a \equiv b,\ b \equiv c \Rightarrow a \equiv c\) 。

證明：三者皆直接由 \(m \mid (a-b)\) 的整除性質推出。例如傳遞性： \(m \mid (a-b)\) 、 \(m \mid (b-c)\) ，故 \(m \mid (a-b)+(b-c) = a-c\) 。 \(\blacksquare\)

定理 2.3（同餘的代數運算）#

若 \(a \equiv b \pmod m\) 且 \(c \equiv d \pmod m\) ，則

\[a + c \equiv b + d, \qquad ac \equiv bd \pmod m.\]

證明： \(a = b + sm\) 、 \(c = d + tm\) （ \(s, t \in \mathbb{Z}\) ）。則 \(a + c = (b+d) + (s+t)m\) ； \(ac = bd + (td + bs + stm)m\) 。 \(\blacksquare\)

警告：同餘對除法不封閉。由 \(6 \equiv 12 \pmod{3}\) 不能約掉 6 得 \(1 \equiv 2\) 。正確的約分法則是：

定理 2.4（消去律）#

若 \(ac \equiv bc \pmod m\) 且 \(\gcd(c, m) = 1\) ，則 \(a \equiv b \pmod m\) 。

證明： \(m \mid c(a - b)\) 且 \(\gcd(c, m) = 1\) 。由 Bézout，存在 \(x, y\) 使 \(cx + my = 1\) ，兩邊乘 \((a-b)\) 得 \(c(a-b)x \equiv 0\) ，即 \(m \mid (a-b)\) 。 \(\blacksquare\)

剩餘類與 \(\mathbb{Z}_m\)#

由定理 2.2，同餘把 \(\mathbb{Z}\) 劃分成 \(m\) 個等價類（剩餘類）：

\[[0], [1], \dots, [m-1], \qquad [a] = \{a + km \mid k \in \mathbb{Z}\}.\]

令 \(\mathbb{Z}_m = \{[0], \dots, [m-1]\}\) ，並定義 \([a] + [b] = [a+b]\) 、 \([a] \cdot [b] = [ab]\) 。由定理 2.3，這兩個運算是良定義的——不會因為代表元的選擇而改變結果。這個小小的驗證，正是抽象代數中「商結構」的第一個範例（見 08.1）。

# Z_m 的加法與乘法表（m = 6）
def z_m_tables(m):
    add = {(i, j): (i + j) % m for i in range(m) for j in range(m)}
    mul = {(i, j): (i * j) % m for i in range(m) for j in range(m)}
    return add, mul

add, mul = z_m_tables(6)
# 哪些元素有乘法反元素？（ units ）
units = [a for a in range(6) if any((a*b) % 6 == 1 for b in range(6))]
print(units)   # [1, 5]  → 恰好是與 6 互質的數！這就是 φ(6) = 2

3. 同餘方程：中國剩餘定理與線性方程#

定理 3.1（線性同餘方程解的存在性）#

方程 \(ax \equiv b \pmod m\) 有解 \(\iff \gcd(a, m) \mid b\) ；有解時恰有 \(\gcd(a, m)\) 個模 \(m\) 的解。

證明（⇒ 的關鍵方向）：若 \(x\) 是解， \(m \mid (ax - b)\) ，設 \(ax - b = km\) ，則 \(b = ax - km\) 是 \(a\) 與 \(m\) 的線性組合，由 Bézout 可知 \(\gcd(a,m) \mid b\) 。（⇐）由 Bézout 直接構造。解的個數由模 \(m/\gcd\) 的消去律可得。 \(\blacksquare\)

定理 3.2（中國剩餘定理，CRT）#

設 \(m_1, m_2, \dots, m_k\) 兩兩互質，則系統

\[x \equiv a_1 \pmod{m_1},\ \dots,\ x \equiv a_k \pmod{m_k}\]

在模 \(M = m_1 m_2 \cdots m_k\) 下有唯一解。

證明（構造式）：令 \(M_i = M / m_i\) ， \(y_i = M_i^{-1} \pmod{m_i}\) （存在，因 \(\gcd(M_i, m_i) = 1\) ）。則

\[x = \sum_{i=1}^{k} a_i M_i y_i \pmod M.\]

代入第 \(j\) 個模數檢驗：所有 \(i \neq j\) 的項因 \(m_j \mid M_i\) 而消失，剩下 \(a_j M_j y_j \equiv a_j \pmod{m_j}\) 。唯一性：若 \(x \equiv x'\) 對所有 \(m_i\) 成立，則 \(M \mid (x - x')\) 。 \(\blacksquare\)

歷史：此問題最早見於《孫子算經》（約 4 世紀）「物不知數」：今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？答曰二十三。

def crt(pairs):
    """pairs = [(a1, m1), (a2, m2), ...]，m_i 兩兩互質"""
    M = 1
    for _, m in pairs:
        M *= m
    x = 0
    for a, m in pairs:
        Mi = M // m
        yi = pow(Mi, -1, m)      # Python 3.8+ 支援模反元素
        x = (x + a * Mi * yi) % M
    return x

print(crt([(2, 3), (3, 5), (2, 7)]))   # 23  ← 孫子算經的答案

4. 素數：整數世界的原子#

定義 4.1#

整數 \(p > 1\) 為素數（質數），若其正因數只有 \(1\) 與 \(p\) 。

定理 4.2（歐幾里得，約 BC 300：素數無窮多）#

證明（反證）：設素數只有 \(p_1, \dots, p_n\) 。令 \(N = p_1 p_2 \cdots p_n + 1\) 。則 \(N\) 除以任何 \(p_i\) 都餘 1，故其素因數不在表中，矛盾。 \(\blacksquare\)

定理 4.3（算術基本定理，Gauss《算術研究》中首次嚴格證明）#

每個大於 1 的整數都能唯一地寫成素數的乘積（不計次序）。

存在性由強歸納法；唯一性依賴歐幾里得引理： \(p \mid ab \Rightarrow p \mid a\) 或 \(p \mid b\) ，而此引理又依賴 Bézout 恆等式（若 \(p \nmid a\) ，則 \(\gcd(p, a) = 1\) ，存在 \(px + ay = 1\) ，兩邊乘 \(b\) ： \(pbx + aby = b\) ，左邊兩項都被 \(p\) 整除，故 \(p \mid b\) ）。

因果鏈：良序 → 帶餘除法 → Bézout → 歐幾里得引理 → 算術基本定理。沒有任何一步可以跳過。

素數的分佈（素數定理： \(\pi(x) \sim x / \ln x\) ）保證了 07.3 中「隨機找大素數」是可行的：

import random

def is_probable_prime(n, k=20):
    """Miller-Rabin 機率式素數測試（利用 Fermat 小定理，見 07.2）"""
    if n < 2: return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0: return n == p
    d, r = n - 1, 0
    while d % 2 == 0:
        d, r = d // 2, r + 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else:
            return False
    return True

def gen_prime(bits):
    while True:
        n = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(n):
            return n

print(gen_prime(64))   # 一個 64 位元的（機率）素數

5. 章末小結#

概念 角色 下游影響
帶餘除法 同餘的基礎 歐幾里得演算法、Bézout
同餘 \(\mathbb{Z}_m\) 有限代數系統 群、環、體（08.1）、Galois 理論
中國剩餘定理 拆解與重組 RSA-CRT 加速、多項式插值
算術基本定理 整數的原子論 因數分解難度 = RSA 安全性
歐幾里得演算法 \(O(\log)\) 求反元素 Diffie–Hellman、ElGamal

核心因果鏈：良序原理 → 帶餘除法 → Bézout → 消去律與唯一分解 → 模運算成為「可計算的有限世界」。

6. 下一步#

本章建立了模運算的加法與乘法，但還沒回答指數的問題： \(a^{100} \bmod 13\) 要不要真的乘 100 次？尤拉 \(\varphi\) 函數如何讓指數「繞圈回到原點」？這就是 07.2 尤拉定理與費馬小定理的主題——而它們正是 RSA 能解密的數學根據。再往後，07.3 將看到 Gauss 的抽象結構如何變成 1976 年 Diffie–Hellman 金鑰交換與 1977 年 Rivest–Shamir–Adleman 的公開金鑰密碼學。