數論簡介
歡迎來到數學中最迷人的分支之一！數論 (Number Theory) 常被稱為「數學中的女王」。它研究的是整數（我們日常生活中使用的整數）的性質。雖然它看起來很抽象，但數論其實是現代科技背後的隱形語言。例如，每當你進行網上購物時，數論（特別是模算術 Modular Arithmetic）就在幕後運作，將你的信用卡資料加密，確保其安全性！
在本章中，我們將探索數字之間如何整除、如何使用一個古老而強大的算法來找出「最大公因數」，以及如何利用同餘概念進行「時鐘算術」。別擔心，這聽起來可能很複雜，我們會一步一步來拆解。
1. 除法定理與歐幾里得算法
除法定理 (Division Theorem) 的核心其實就是用數學形式表達除法的過程。如果你有兩個整數 \(a\) 和 \(b\)，你可以將其寫成：
\(a = bq + r\)
其中：
- \(q\) 是商 (quotient)（即除得的次數）。
- \(r\) 是餘數 (remainder)，且 \(0 \le r < b\)。
歐幾里得算法 (Euclidean Algorithm)
這是一個非常巧妙的「循環」方法，用於找出兩個數字的最大公因數 (Highest Common Factor, HCF，又稱 Greatest Common Divisor, GCD)。與其逐一列出所有因數，我們利用餘數不斷縮小數字，直到最大公因數浮現出來。
步驟：
1. 用較大的數除以較小的數，並找出餘數。
2. 將較大的數替換為除數（原本較小的數），並將較小的數替換為剛才得到的餘數。
3. 重複上述步驟，直到餘數為零。最後一個非零的餘數就是你的最大公因數！
例子：求 HCF(126, 45)
\(126 = 2 \times 45 + 36\)
\(45 = 1 \times 36 + 9\)
\(36 = 4 \times 9 + 0\)
餘數現在變為零，所以最大公因數 (HCF) 是 9。
重點提示：歐幾里得算法就像是一個「數字粉碎機」——它不斷將數字分解為較小的餘數，直到只剩下最大公因數為止。
2. 貝祖等式 (Bezout's Identity)
貝祖等式指出，兩個數字 \(a\) 和 \(b\) 的最大公因數可以寫成這兩個數字的「線性組合」。簡單來說，你一定能找到整數 \(x\) 和 \(y\)，使得：
\(ax + by = \text{HCF}(a, b)\)
要找到 \(x\) 和 \(y\)，我們使用逆向代入法 (back substitution)。我們採用歐幾里得算法的步驟，從最後一行最大公因數的算式開始，向後推導。
快速回顧：
- 使用歐幾里得算法向前推導以找出最大公因數。
- 使用貝祖等式向後推導以找出係數 \(x\) 和 \(y\)。
3. 模算術與同餘 (Modular Arithmetic and Congruences)
將模算術想像成「時鐘算術」。在 12 小時制的時鐘上，如果現在是 10 點，過了 5 小時後，並不是 15 點，而是 3 點。我們記作 \(15 \equiv 3 \pmod{12}\)。
關鍵詞：我們稱 \(a \equiv b \pmod n\)（讀作「\(a\) 同餘於 \(b\)，模 \(n\)」），如果 \(a\) 和 \(b\) 除以 \(n\) 時有相同的餘數。這也意味著 \(a - b\) 能被 \(n\) 完全整除。
同餘的性質
同餘的好處在於它們的操作方式與普通方程式非常相似。如果 \(a \equiv b \pmod n\)，那麼：
1. 加法/減法： \(a \pm k \equiv b \pm k \pmod n\)
2. 乘法： \(ak \equiv bk \pmod n\)
3. 冪次： \(a^k \equiv b^k \pmod n\)
你知道嗎？這個冪次規則簡直是救星！如果你想求 \(11^{100} \div 10\) 的餘數，只需留意 \(11 \equiv 1 \pmod{10}\)。因此，\(11^{100} \equiv 1^{100} \equiv 1 \pmod{10}\)。答案直接就是 1！
常見錯誤：進行除法時要小心！除非你除以的數字與模數 \(n\) 互質 (coprime)，否則不能直接將同餘式兩邊同時除以同一個數。通常，使用乘法逆元 (multiplicative inverses) 會更安全。
4. 費馬小定理 (Fermat's Little Theorem)
這是一個非常具體且強大的規則，用於在模數為質數 (prime number) \(p\) 時簡化巨大的指數運算。
如果 \(p\) 是質數，那麼對於任何整數 \(a\)：
\(a^p \equiv a \pmod p\)
或者，如果 \(a\) 不能被 \(p\) 整除：
\(a^{p-1} \equiv 1 \pmod p\)
例子：求 \(4^{20} \pmod 7\)
因為 7 是質數，根據費馬小定理，\(4^{7-1} \equiv 4^6 \equiv 1 \pmod 7\)。
我們可以將 \(4^{20}\) 分解為：\(4^{20} = (4^6)^3 \times 4^2\)。
這變成了：\(1^3 \times 16 \pmod 7\)。
因為 \(16 \div 7\) 的餘數為 2，所以答案是 2。
重點提示：使用費馬小定理將巨大的指數「削減」成較小且容易處理的數字。
5. 整除性測試 (Divisibility Tests)
有時候你只需一眼就能判斷一個數是否能被另一個數整除。以下是你考試時需要掌握的測試方法：
- 被 2 整除： 末位數是 0, 2, 4, 6, 8（偶數）。
- 被 3 整除： 所有位數之和能被 3 整除。
- 被 4 整除： 末兩位數組成的數能被 4 整除。
- 被 5 整除： 末位數是 0 或 5。
- 被 6 整除： 同時能被 2 和 3 整除。
- 被 9 整除： 所有位數之和能被 9 整除。
- 被 10 整除： 末位數是 0。
- 被 11 整除： 位數交替相減（加、減、加、減...）的結果為 0 或能被 11 整除。
11 的例子：1,331 能被 11 整除嗎？
\(1 - 3 + 3 - 1 = 0\)。是的，可以！
6. 同餘方程式的解法
同餘方程式的形式為 \(ax \equiv b \pmod n\)。解這個方程式就像代數中的解 \(x\)，但我們尋找的是整數值。
乘法逆元 (Multiplicative Inverses)
要解 \(ax \equiv 1 \pmod n\)，我們需要 \(a\) 的乘法逆元。這是一個整數 \(x\)，使得它與 \(a\) 相乘後，餘數為 1。我們可以利用歐幾里得算法和貝祖等式來找到它。
存在規則：同餘方程式 \(ax \equiv b \pmod n\) 有解的充要條件是 \(a\) 和 \(n\) 的最大公因數能整除 \(b\)。
- 如果 HCF(\(a, n\)) = 1，則有唯一解（模 \(n\)）。
- 如果 HCF(\(a, n\)) 不能整除 \(b\)，則無解。
7. 組合數學：計數、排列與組合
組合數學是關於計算可能性的數學。
基本原則
- 乘法原理 (AND)： 如果完成一件事有 \(m\) 種方法，而完成另一件事有 \(n\) 種方法，那麼同時完成這兩件事就有 \(m \times n\) 種方法。
- 加法原理 (OR)： 如果各項任務互斥，則將可能性相加。
排列與組合
這是計數中最關鍵的區別：
1. 排列 (\(^nP_r\))：考慮順序。
想像一場比賽，決出金、銀、銅牌。完成比賽的順序不同，結果就不同。
\(^nP_r = \frac{n!}{(n-r)!}\)
2. 組合 (\(^nC_r\))：不考慮順序。
想像從 21 人的隊伍中選出 11 名球員組成球隊。你是第一個被選中還是第五個並不重要；只要你進了隊伍就行！
\(^nC_r = \frac{n!}{r!(n-r)!}\)
集合符號與子集
集合 (set) 是元素的集合。
- 你知道嗎？ 如果一個集合有 \(n\) 個元素，它擁有的子集 (subsets) 數量為 \(2^n\)。這包括空集和集合本身！
重點提示：在解決計數問題之前，先問自己：「順序重要嗎？」
- 是 \(\rightarrow\) 使用排列。
- 否 \(\rightarrow\) 使用組合。
如果起初覺得棘手，不用擔心！數論的核心在於模式。一旦你練習過幾次歐幾里得算法並習慣了「時鐘算術」，你就會開始在各處看到這些模式。