数论 — 进位制、同余与定理
从进位制出发，探索同余、素数、定理与方程的奥秘——数论是数学皇冠上的明珠。
一、进位制
什么是进位制
进位制是一种记数方式。对底数为 b 的整数进位制（b ≥ 2），每一位使用 0,1,2,…,b−1 这些数字，并按位权表示非负整数。我们最熟悉的是十进制（逢十进一），但计算机科学中广泛使用二进制、八进制和十六进制。
进制表示法：
十进制数 1234 = 1×103 + 2×102 + 3×101 + 4×100
二进制数 1011(2) = 1×23 + 0×22 + 1×21 + 1×20 = 8 + 0 + 2 + 1 = 11
八进制数 17(8) = 1×81 + 7×80 = 8 + 7 = 15
十六进制数 1A(16) = 1×161 + 10×160 = 16 + 10 = 26
进制转换方法
例 1：将二进制 11010 转为十进制。
11010(2) = 1×24 + 1×23 + 0×22 + 1×21 + 0×20
= 16 + 8 + 0 + 2 + 0 = 26
例 2：将十进制 47 转为二进制。
用除 2 取余法：
47 ÷ 2 = 23 … 1（最低位）
23 ÷ 2 = 11 … 1
11 ÷ 2 = 5 … 1
5 ÷ 2 = 2 … 1
2 ÷ 2 = 1 … 0
1 ÷ 2 = 0 … 1（最高位）
从下往上读取余数：47 = 101111(2)
| 十进制 | 二进制 | 八进制 | 十六进制 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 2 |
| 3 | 11 | 3 | 3 |
| 4 | 100 | 4 | 4 |
| 5 | 101 | 5 | 5 |
| 6 | 110 | 6 | 6 |
| 7 | 111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
二、高斯函数
定义
高斯函数（又称取整函数、向下取整函数）记作 [x]，定义为：
[x] 表示不超过 x 的最大整数
[x] ≤ x < [x] + 1
基本性质
- 性质 1：[x] ≤ x < [x] + 1
- 性质 2：若 x 为整数，则 [x] = x
- 性质 3：[x] + [y] ≤ [x + y] ≤ [x] + [y] + 1
- 性质 4：[-x] = −[x] − 1（当 x 不是整数时）
例：计算以下各值：
[3.7] = 3（不超过 3.7 的最大整数是 3）
[−1.2] = −2（不超过 −1.2 的最大整数是 −2，因为 −2 ≤ −1.2 < −1）
[5] = 5（整数取整等于自身）
[π] = 3（π ≈ 3.14159…）
例如 [−1.2] = −2，而 −1.2 四舍五入是 −1。
三、格点问题
格点的概念
在平面直角坐标系中，横、纵坐标都是整数的点称为格点（也称整点）。例如 (0,0)、(1,2)、(3,4) 都是格点，而 (1.5,2) 不是格点。
皮克定理
皮克定理（Pick's Theorem）给出了顶点为格点的多边形的面积与内部和边界上的格点数量之间的关系。
皮克定理：
S = I + B/2 − 1
其中 S 为多边形面积，I 为多边形内部的格点数，B 为多边形边界上的格点数
例：以下格点三角形的三个顶点为 (0,0)、(4,0)、(0,3)。
边界格点数 B：底边有 (0,0)(1,0)(2,0)(3,0)(4,0) 共 5 个；右边从 (4,0) 到 (0,3) 只有端点（因 gcd(4,3)=1）；左边有 (0,0)(0,1)(0,2)(0,3) 共 4 个。去重后 B = 5 + 1 + 2 = 8。
内部格点数 I：格点 (1,1)(2,1)(1,2) 共 3 个（直接数或用公式 I = S − B/2 + 1 算）。
面积 S = (4 × 3) / 2 = 6。
验证皮克定理：S = I + B/2 − 1 = 3 + 8/2 − 1 = 3 + 4 − 1 = 6。成立！
四、素数与算术基本定理
素数（质数）与合数
一个大于 1 的自然数，如果除了 1 和它自身外，不能被其他自然数整除，则称为素数（或质数）；否则称为合数。注意：1 既不是素数也不是合数。
前 20 个素数：
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
例：判断下列各数是否为素数。
29：只需检查不超过 √29 ≈ 5.38 的素数 2、3、5；均不能整除 29，所以 29 是素数。✓
39：39 ÷ 3 = 13，是合数（3×13）。✗
57：57 ÷ 3 = 19，是合数（3×19）。✗
97：只需检查不超过 √97 ≈ 9.85 的素数 2、3、5、7；均不能整除 97，所以 97 是素数。✓
算术基本定理
算术基本定理（也称唯一分解定理）是数论中最重要的定理之一：
算术基本定理：
每个大于 1 的自然数，都可以唯一地分解为有限个素数的乘积（不计因子的顺序）。
n = p1α1 · p2α2 · … · pkαk
其中 p1, p2, …, pk 是互不相同的素数，α1, α2, …, αk 是正整数。
例：分解质因数。
12 = 22 × 3
84 = 22 × 3 × 7
360 = 23 × 32 × 5
1001 = 7 × 11 × 13
五、费马小定理
同余的概念
在介绍费马小定理之前，先引入同余的概念：若两个整数 a、b 除以正整数 m 有相同的余数，则称 a 与 b 模 m 同余，记作
a ≡ b (mod m)
等价于 m | (a − b)
费马小定理
费马小定理是数论中关于素数的一个基本定理：
费马小定理：
若 p 是素数，a 是整数且 p ∤ a（即 p 不能整除 a），则
ap−1 ≡ 1 (mod p)
例 1：计算 26 mod 7。
由于 7 是素数，且 7 ∤ 2，根据费马小定理：
27−1 = 26 ≡ 1 (mod 7)
验证：26 = 64，64 ÷ 7 = 9 … 1。✓
例 2：计算 3100 mod 101。
101 是素数，且 101 ∤ 3，由费马小定理：
3100 ≡ 1 (mod 101)
本题直接使用定理即得结果，无需进行大量计算。
六、欧拉函数
定义
欧拉函数 φ(n) 定义为正整数 n 的范围内，满足 1 ≤ k ≤ n 且与 n 互质的正整数 k 的个数。
φ(n) = |{ k | 1 ≤ k ≤ n, gcd(k, n) = 1 }|
基本性质
- 性质 1：若 p 是素数，则 φ(p) = p − 1
- 性质 2：若 p 是素数，k 为正整数，则 φ(pk) = pk − pk−1
- 性质 3：若 m、n 互质，则 φ(mn) = φ(m) · φ(n)（积性函数）
例 1：计算 φ(12)。
方法一（枚举）：12 以内与 12 互质的数：1, 5, 7, 11，共 4 个。所以 φ(12) = 4。
方法二（公式）：12 = 22 × 3，由积性性质：φ(12) = φ(22) · φ(3) = (4 − 2) × (3 − 1) = 2 × 2 = 4。
方法三（公式进阶）：φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4。
例 2：计算 φ(100)。
100 = 22 × 52
φ(100) = 100 × (1 − 1/2) × (1 − 1/5) = 100 × 1/2 × 4/5 = 40
验证：小于 100 且与 100 互质的数有 40 个。
七、中国剩余定理
一次同余方程组
中国剩余定理（Chinese Remainder Theorem）解决的是这样一类问题：
一次同余方程组：
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
⋮
x ≡ ak (mod mk)
其中 m1, m2, …, mk 是两两互质的正整数。
定理的表述
中国剩余定理：
设正整数 m1, m2, …, mk 两两互质，则对任意整数 a1, a2, …, ak，同余方程组在模 M = m1m2…mk 下有唯一的剩余类解（任意两个整数解相差 M 的倍数）。
求解方法步骤
以两个方程的情况为例，设 x ≡ a (mod m), x ≡ b (mod n)，其中 gcd(m, n) = 1。
例：解同余方程组：x ≡ 2 (mod 3), x ≡ 3 (mod 5)。
步骤 1：设 x = 3k + 2（由第一个方程）。
步骤 2：代入第二个方程：3k + 2 ≡ 3 (mod 5)
即 3k ≡ 1 (mod 5)，两边乘以 3 的逆元 2（因为 3×2=6≡1 mod 5）：
k ≡ 2 (mod 5)，即 k = 5t + 2
步骤 3：回代：x = 3(5t + 2) + 2 = 15t + 8
所以 x ≡ 8 (mod 15)。验算：8 mod 3 = 2 ✓，8 mod 5 = 3 ✓。
另一个经典问题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"
即方程组：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
根据中国剩余定理，最小正整数解为 23。
八、勾股方程
勾股方程的定义
勾股方程是指形如 x2 + y2 = z2 的三元二次不定方程，其中 x、y、z 为正整数。满足勾股方程的正整数三元组 (x, y, z) 称为勾股数（或毕达哥拉斯三元组）。
x2 + y2 = z2
经典的勾股数：
(3, 4, 5)：32 + 42 = 9 + 16 = 25 = 52 ✓
(5, 12, 13)：52 + 122 = 25 + 144 = 169 = 132 ✓
(8, 15, 17)：82 + 152 = 64 + 225 = 289 = 172 ✓
(7, 24, 25)：72 + 242 = 49 + 576 = 625 = 252 ✓
本原勾股数
若 gcd(x, y, z) = 1，则 (x, y, z) 称为本原勾股数。所有本原勾股数（交换两条直角边后视为同一类）可以用以下参数形式生成：
本原勾股数的参数形式：
x = m2 − n2
y = 2mn
z = m2 + n2
其中 m > n > 0，gcd(m, n) = 1，且 m、n 一奇一偶；所得的 x、y 两式也可以互换。
例：取 m = 2, n = 1：
x = 22 − 12 = 3
y = 2 × 2 × 1 = 4
z = 22 + 12 = 5
得到本原勾股数 (3, 4, 5)。
九、完全平方数与平方剩余
完全平方数
一个非负整数若能写成某个整数的平方，则称其为完全平方数。例如 0, 1, 4, 9, 16, 25, 36, … 都是完全平方数。
- 十进制完全平方数的个位只能是 0, 1, 4, 5, 6, 9
- 奇完全平方数除以 4 余 1，偶完全平方数能被 4 整除
- 每个正的完全平方数有奇数个正因数（0 不适用此说法）
平方剩余
在模 m（m ≥ 2）的意义下，若存在整数 x 使得 x2 ≡ a (mod m)，则称 a 为模 m 的平方剩余（二次剩余）；否则称为平方非剩余。按此定义，允许 x = 0，因此 0 也是平方剩余；在讨论勒让德符号时另行区分非零平方剩余。
平方剩余的定义：
若存在整数 x 使 x2 ≡ a (mod m)，则 a 是模 m 的平方剩余。
例：求模 7 的所有平方剩余。
计算 02 到 62 模 7 的值：
02 ≡ 0 (mod 7)
12 = 1 ≡ 1 (mod 7)
22 = 4 ≡ 4 (mod 7)
32 = 9 ≡ 2 (mod 7)
42 = 16 ≡ 2 (mod 7)
52 = 25 ≡ 4 (mod 7)
62 = 36 ≡ 1 (mod 7)
所以模 7 的平方剩余为：0, 1, 2, 4（共 4 个）；其中非零平方剩余为 1, 2, 4，平方非剩余为：3, 5, 6。