简介：欢迎来到数论的世界！
欢迎来到数论 (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。
例子：十六进制中的 \(1\text{A}_{16}\) 会是 \((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\))。
你也可以在其他进位制（例如 \(n\) 进位制）中使用除法算法，通过在该进位制中进行算术运算来找出商和余数。
常见错误：忘记余数必须小于 \(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）是能整除两个数字的最大整数。
如果 \(\text{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\) 且 \(\text{hcf}(a, r) = 1\)，那么 \(a|s\)。
简单来说，如果 \(a\) 能整除一个乘积，但与乘积的第一部分毫无关系，那么它一定能整除第二部分。
5. 有限算术 (模运算 Modular Arithmetic)
这通常被称为「时钟算术」。在模 \(n\) 中，我们只关心一个数除以 \(n\) 后的余数。
符号表示
\(a \equiv b \pmod n\)
这意味着「\(a\) 在模 \(n\) 下与 \(b\) 同余」。它表示 \(n | (a - b)\)，即 \(a\) 和 \(b\) 除以 \(n\) 后具有相同的余数。
例子：\(17 \equiv 2 \pmod 5\)。因为 17 和 2 除以 5 后的余数都是 2。
解线性同余方程
你将会遇到类似这样的方程：\(ax \equiv b \pmod n\)。
要解这些方程，寻找 \(x\) 的整数解：
1. 解的存在性： 当且仅当 \(d = \text{hcf}(a, n)\) 能整除 \(b\) 时，方程有解。
2. 解的个数： 若 \(d \mid b\)，则在模 \(n\) 下恰好有 \(d\) 个不同（不同余）的解。
3. 通解形式： 若 \(x_0\) 是一个特解，则在模 \(n\) 下的完整解集为：
\(x \equiv x_0 + k\left(\frac{n}{d}\right) \pmod n\)，其中 \(k = 0, 1, \dots, d - 1\)。
你知道吗？模运算正是保护你信用卡信息安全的方法！加密技术使用巨大的质数和模运算将数据打乱，只有拥有「密钥」的人才能解开同余方程并读取信息。
总结清单
- 你能否在 \(n\) 进位制和十进制之间转换数字？
- 你是否记住了十六进制中 A-F 对应的数字？
- 你能否写出除法算法 \(a = bq + r\)？
- 你是否知道 3、4、9 和 11 的整除性判别法？
- 你是否理解互质意味着 \(\text{hcf}(a, b) = 1\)？
- 你能否将欧几里得引理应用于整除性问题？
- 你能否找出线性同余方程 \(ax \equiv b \pmod n\) 的所有解？
如果一开始觉得很难也不要担心！数论是一种不同的思考方式。继续练习「时钟算术」和整除规则，你很快就能掌握其中的规律！