数论简介
欢迎来到数论 (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\)。