數論簡介
歡迎來到數論 (Number Theory)！這一章節屬於進階純數學 (Additional Pure Mathematics)模組，通常被稱為「數學中的女王」。儘管大家從小就開始接觸數字，但現在我們將深入「引擎蓋下」，看看數字究竟是如何運作的、它們如何進行除法，以及它們如何在不同的系統中互動。這可是現代電腦安全與密碼學的基石！
如果有些符號剛開始看起來很陌生，別擔心。數論是非常講究邏輯的，一旦你掌握了「時鐘算術」和整除規則，它絕對會成為進階數學中最令你感到滿足的部分之一。
1. 整除性與除法演算法
在數論中，我們主要探討的是整數 (\(\mathbb{Z}\))。如果 \(b\) 是 \(a\) 的倍數，我們就說 \(a\) 整除 \(b\)（記作 \(a | b\)）。例如，\(3 | 12\) 是正確的，但 \(5 | 12\) 則不然。
除法演算法 (The Division Algorithm)
這聽起來很花俏，但其實你從小學開始就一直在做！它僅僅指出，對於任何兩個正整數 \(a\) 和 \(b\)，你可以寫成：
\(a = bq + r\)
其中：
- \(q\) 是商 (quotient)（即包含多少個 \(b\)）。
- \(r\) 是餘數 (remainder)（即剩下的部分）。
- 重要的一點是，\(0 \le r < b\)。餘數永遠必須小於除數。
快速回顧： 如果 \(a = 17\) 且 \(b = 5\)，那麼 \(17 = 5(3) + 2\)。這裡，\(q=3\)，而 \(r=2\)。
整除性的性質
你需要了解並運用的一個關鍵結論是：
如果 \(a | b\) 且 \(a | c\)，那麼對於任何整數 \(x\) 和 \(y\)，都有 \(a | (bx + cy)\)。
類比： 如果一把尺可以精準測量出 10cm 和 20cm，那麼它一定也能測量出它們的任何線性組合（例如 \(2 \times 10 + 3 \times 20 = 80cm\)）。
2. 質數與歐幾里得引理
質數 (Prime numbers) 是所有整數的構件。每個大於 1 的整數要麼是質數，要麼是合數 (composite number)（由質數相乘而成）。
歐幾里得引理 (Euclid’s Lemma)
這是證明題中極其重要的工具。它指出：
如果 \(a | rs\) 且最大公因數 \(\text{hcf}(a, r) = 1\)（意思是它們互質 (coprime)），那麼 \(a | s\)。
例子： 如果 \(3 | (7 \times s)\)，因為 3 不能整除 7，所以它必須能整除 \(s\)。
重點總結： 如果一個數能整除一個乘積，且與乘積的第一部分沒有共同因數，那麼它一定能整除第二部分。
3. 進位制 (Number Bases)
我們通常使用十進位 (Base 10)，但我們可以使用任何整數 \(n \ge 2\) 作為基數。在 \(n\) 進位中，我們使用從 \(0\) 到 \(n-1\) 的數字。
如果基數大於 10，我們就使用字母：
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15
理解記數法
像 \(2013_n\) 這樣的數字代表：
\(2n^3 + 0n^2 + 1n^1 + 3n^0\)
例子：將 \(23_5\) 轉換為十進位
\(2(5^1) + 3(5^0) = 10 + 3 = 13\)。
常見錯誤： 忘記「個位數」欄位永遠是 \(n^0\)，也就是 1，無論基數是多少！
4. 整除性判別法
你應該掌握這些「捷徑」，以便在不做長除法的情況下判斷一個數是否能被某些整數整除。
- 2： 最後一位數字是偶數。
- 3： 數字之和能被 3 整除。
- 4： 最後兩位數字組成的數能被 4 整除。
- 5： 最後一位數字是 0 或 5。
- 8： 最後三位數字組成的數能被 8 整除。
- 9： 數字之和能被 9 整除。
- 11： 數字的交錯和（加、減、加...）能被 11 整除。
你知道嗎？ 若要測試一個合數（如 6），你只需測試其互質因數（2 和 3）。如果兩者都通過，那它就能被 6 整除！
5. 同餘算術（有限算術）
同餘算術通常被稱為「時鐘算術」。如果 \(a\) 和 \(b\) 除以 \(n\) 後有相同的餘數，我們就說 \(a \equiv b \pmod{n}\)。
線性同餘 (Linear Congruences)
線性同餘方程式長這樣：\(ax \equiv b \pmod{n}\)。
要解這些方程式，我們嘗試找出一個 \(x\) 值使該語句成立。與一般的代數不同，這裡可能無解、只有一個解，或者有多個解！
例子：解 \(3x \equiv 1 \pmod{5}\)
試試 \(x\) 的值：
- \(x=1 \implies 3 \equiv 3 \pmod{5}\) (錯誤)
- \(x=2 \implies 6 \equiv 1 \pmod{5}\) (正確！ 因為 \(6 \div 5 = 1\) 餘 \(1\))
聯立同餘
有時候你會遇到包含兩個或三個同餘式的系統。雖然中國剩餘定理 (Chinese Remainder Theorem) 是解決它們的正式方法，但對於本課程大綱，你通常可以透過代入法，或者先列出最大模數 (modulus) 的可能性來解決。
6. 費馬小定理 (Fermat’s Little Theorem, FLT)
這是一個非常強大的「次方縮減器」，能幫助我們輕鬆計算巨大的指數。如果 \(p\) 是一個質數：
- \(a^{p-1} \equiv 1 \pmod{p}\)（前提是 \(a\) 不是 \(p\) 的倍數）
- \(a^p \equiv a \pmod{p}\)（對於任何 \(a\) 永遠成立）
記憶小撇步： 把指數 \(p-1\) 想成是一個「重置按鈕」，可以將該數字變成 1。
例子：求 \(2^{100} \pmod{3}\)
因為 3 是質數，根據費馬小定理：\(2^{3-1} \equiv 2^2 \equiv 1 \pmod{3}\)。
現在，\(2^{100} = (2^2)^{50} = (1)^{50} = 1\)。
所以，\(2^{100} \equiv 1 \pmod{3}\)。簡直是魔法！
7. \(a\) 模 \(p\) 的階 (Order)
\(a\) 模 \(p\) 的階 (order) 是使下式成立的最小正整數 \(k\)：
\(a^k \equiv 1 \pmod{p}\)
重要規則： 階 \(k\) 必須是 \(p-1\) 的因數。
如果你要尋找一個數模 7 的階，你只需要檢查 6 的因數（即 1, 2, 3 或 6）。
重點總結： 費馬小定理指出 \(a^{p-1} \equiv 1\)，但可能存在一個更小的次方數也能先達到 1。那個最小的次方數就是「階」。
快速回顧欄
記號： \(a | b\) 代表 \(a\) 整除 \(b\)。
除法： \(a = bq + r\)。
費馬小定理： 若 \(p\) 為質數，則 \(a^{p-1} \equiv 1 \pmod{p}\)。
互質： \(\text{hcf}(a,b) = 1\)。
進位制： \(A=10, B=11, \dots, F=15\)。