数论简介
欢迎来到数学中最迷人的分支之一！数论 (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\) 使用组合。
如果起初觉得棘手，不用担心！数论的核心在于模式。一旦你练习过几次欧几里得算法并习惯了“时钟算术”，你就会开始在各处看到这些模式。