丟番圖方程與費馬小定理

要求整數解的方程

[[diophantine-equation|丟番圖方程]]是普通的方程，但我們堅持解必須是整數。最簡單而有趣的情形是線性的 ax + by = c。設想購物：如果鉛筆每支 4 枚硬幣、鋼筆每支 6 枚，你能恰好花掉 30 枚嗎？兩者都需為整數——半支鉛筆是不允許的。

這裡有一條簡潔的法則，直接源自裴蜀恆等式：ax + by = c 有整數解當且僅當 a 與 b 的最大公約數整除 c。GCD 是 a、b 所能湊出的最小正數，因此 c 必須是它的倍數。

Solve 4x + 6y = 30 in integers.

  gcd(4, 6) = 2, and 2 | 30 → solutions exist.
  Divide through by 2:  2x + 3y = 15.

One solution by inspection: x = 3, y = 3
  (since 2·3 + 3·3 = 6 + 9 = 15). ✓

General solution (k any integer):
  x = 3 + 3k,   y = 3 − 2k.
Check k = 1:  2(6) + 3(1) = 12 + 3 = 15. ✓

因為 gcd(4,6)=2 整除 30，故有解；一個特解可生成全部解。

費馬小定理

我們的壓軸是一顆 17 世紀的明珠。[[fermats-little-theorem|費馬小定理]]說：若 p 是質數且 a 不被 p 整除，則 a^(p−1) ≡ 1 (mod p)。把任意數提升到「比質數小 1」的冪，再取模，結果總會回到 1。一個對每個整數 a 都成立的便利形式是 a^p ≡ a (mod p)。

Check with p = 7, a = 3:
  3^(7−1) = 3^6 = 729
  729 = 7 · 104 + 1  →  3^6 ≡ 1 (mod 7) ✓

Now use it to find 3^100 (mod 7) the fast way:
  By Fermat, 3^6 ≡ 1 (mod 7).
  100 = 6·16 + 4, so
  3^100 = (3^6)^16 · 3^4 ≡ 1^16 · 3^4 (mod 7)
  3^4 = 81 = 7·11 + 4 ≡ 4 (mod 7)
  Therefore 3^100 ≡ 4 (mod 7).

費馬定理把一個 48 位的冪化為一行餘數計算。

請留意一切是如何串聯起來的：定理用模運算敘述，其前提（a 不被 p 整除）是一個互質條件，而我們透過帶餘除法把指數寫成 100 = 6·16 + 4 來加以利用。整條學習路徑一直在悄悄拼裝這些工具。

這些結果為何重要

這些並非博物館裡的陳列品。費馬小定理是快速質性檢驗和保護互聯網的 RSA 密碼系統的種子；線性丟番圖方程則支撐著排程、齒輪傳動比和找零。從「一個整數整除另一個整數」這個樸素想法出發，你已抵達現代數學的實用工具。