Number Theory

簡介：歡迎來到數論的世界！

歡迎來到數論 (Number Theory)！雖然大部分數學都聚焦於函數、圖形或數據，但數論就像是一個「數學偵探」遊戲。我們將回歸最基礎的部分，研究整數 (integers) 以及它們之間如何互動。
你可能會想：「我從小學就學過除法了。」但這裡我們探討的是除法、餘數和質數背後的隱藏規律。這些概念不僅僅是為了數學謎題；它們是現代電腦安全和加密技術的基石。如果一開始覺得抽象也不用擔心——一旦你看出了其中的規律，這就像學會了一種秘密代碼！

1. 進位制 (數字的語言)

我們通常使用十進制 (Base 10) 來計算，這大概是因為我們有十根手指。但數字其實可以用任何進位制來表示！

理解 \(n\) 進位制

在 \(n\) 進位制中，每個位數的價值取決於它的位置，並乘以 \(n\) 的冪次。
課程大綱使用 \(2013_n\) 這樣的標記法。要找出它在十進制中的數值，我們可以這樣展開：
\(2013_n = (2 \times n^3) + (0 \times n^2) + (1 \times n^1) + (3 \times n^0)\)

處理大於 10 的進位制

如果進位制大於 10（例如 16 進位制，或稱十六進制 Hexadecimal），單個位數就不夠用了。我們使用大寫字母來表示 10 到 15 的數字：
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15。
例子：十六進制中的 \(1A_n\) 會是 \((1 \times 16^1) + (10 \times 16^0) = 16 + 10 = 26。\)

快速回顧：要將數字從 \(n\) 進位制轉換為十進制，請從右邊開始寫出 \(n\) 的冪次（從 \(n^0\) 開始），並將它們與對應的數字相乘。

2. 整除性與除法演算法

在數論中，我們使用一個特殊的符號來表示整除：\(a|b\)。
這讀作「\(a\) 整除 \(b\)」。意思是 \(b\) 除以 \(a\) 的結果是一個整數，且沒有餘數（例如：\(3|12\) 是正確的，但 \(3|10\) 是錯誤的）。

除法演算法 (The Division Algorithm)

對於任意兩個正整數 \(a\) 和 \(b\)，我們總是可以寫成：
\(a = bq + r\)
其中：
- \(q\) 是商 (quotient)（即 \(b\) 可以整除 \(a\) 的次數）。
- \(r\) 是餘數 (remainder)（剩餘的部分）。
重要規則：餘數 \(r\) 必須小於除數 \(b\) (\(0 \le r < b\))。

常見錯誤：忘記餘數必須小於 \(b\)。如果你在除以 5，你的餘數必須是 0、1、2、3 或 4。如果你算出餘數是 6，那就代表還沒除完！

3. 整除性判別法

你需要學會如何不使用計算機，快速判斷一個數是否能被某些整數整除。

標準判別法：

• 2： 最後一位數是偶數。
• 3： 所有數位之和能被 3 整除。
• 4： 最後兩位數組成的數字能被 4 整除。
• 5： 最後一位數是 0 或 5。
• 8： 最後三位數組成的數字能被 8 整除。
• 9： 所有數位之和能被 9 整除。
• 11： 將數字進行交替求和（加一個，減一個……）。如果結果為 0 或能被 11 整除，那麼該整數就能被 11 整除。例子：1331，\(1 - 3 + 3 - 1 = 0\)，所以 1331 能被 11 整除。

複合與質數判別法：

如果一個數是複合數 (composite)（例如 6），你可以透過檢查它的因數來測試（例如，一個數如果能同時通過 2 和 3 的判別法，它就能被 6 整除）。
對於其他小於 50 的質數，你可能需要發展一套演算法測試，通常涉及處理最後一位數並將其從剩餘的數中減去。

重點總結：整除性不僅僅是關於除法，更是關於數字本身的性質！

4. 質數、最高公因數 (HCF) 與互質

質數 (Prime numbers) 是數字世界的「原子」。它們只有兩個因數：1 和它們自己。

最高公因數 (HCF) 與互質

HCF（也稱為 GCD）是能整除兩個數字的最大整數。
如果 hcf(a, b) = 1，我們稱 \(a\) 和 \(b\) 為互質 (coprime)（或相對質數）。這意味著除了 1 之外，它們沒有其他共同的因數。
例子：8 和 9 是互質，因為 8 的因數是 {1, 2, 4, 8}，9 的因數是 {1, 3, 9}。唯一的共同因數只有 1。

重要性質：

• 線性組合： 如果 \(a|b\) 且 \(a|c\)，那麼 \(a\) 也必定能整除它們的任何「組合」：\(a|(bx + cy)\)，其中 \(x\) 和 \(y\) 為任意整數。
  比喻：如果你有兩疊 5 元鈔票，你無論從這些鈔票中加減多少張，總金額仍然是 5 的倍數。
• 歐幾里得引理 (Euclid’s Lemma)： 如果 \(a|rs\) 且 hcf(a, r) = 1，那麼 \(a|s\)。
  簡單來說，如果 \(a\) 能整除一個乘積，但與乘積的第一部分毫無關係，那麼它一定能整除第二部分。

5. 有限算術 (模運算 Modular Arithmetic)

這通常被稱為「時鐘算術」。在模 \(n\) 中，我們只關心一個數除以 \(n\) 後的餘數。

符號表示

\(a \equiv b \pmod n\)
這意味著「\(a\) 在模 \(n\) 下與 \(b\) 同餘」。它基本上告訴我們，\(a\) 和 \(b\) 除以 \(n\) 後的餘數相同。
例子：\(17 \equiv 2 \pmod 5\)。因為 17 和 2 除以 5 後的餘數都是 2。

解線性同餘方程

你將會遇到類似這樣的方程：\(ax \equiv b \pmod n\)。
要解這些方程，你要尋找一個能使陳述成立的整數 \(x\)。
分步方法：
1. 檢查是否有解：若 hcf(a, n) 能整除 \(b\)，則有解。
2. 如有可能，簡化同餘式。
3. 測試數值或利用模運算的性質來分離 \(x\)。

你知道嗎？模運算正是保護你信用卡資訊安全的方法！加密技術使用巨大的質數和模運算將數據打亂，只有擁有「密鑰」的人才能解開同餘方程並讀取訊息。

總結清單

• 你能否在 \(n\) 進位制和十進制之間轉換數字？
• 你是否記住了十六進制中 A-F 對應的數字？
• 你能否寫出除法演算法 \(a = bq + r\)？
• 你是否知道 3、4、9 和 11 的整除性判別法？
• 你是否理解互質意味著 HCF 為 1？
• 你能否將歐幾里得引理應用於整除性問題？
• 你能否解出簡單的線性同餘方程，例如 \(3x \equiv 1 \pmod 5\)？

如果一開始覺得很難也不要擔心！數論是一種不同的思考方式。繼續練習「時鐘算術」和整除規則，你很快就能掌握其中的規律！