一、考前复习

【1/3 题型说明】

填空题 10道，每道 2 分，共 20 分；
计算题 5 道，每道 8 分，共 40 分；
证明题 5 道，每道 8 分，共 40 分；

【2/3 复习题】

【3/3 往年真题】

二、学习笔记

第一章整数的可除性

整除，欧几里得除法

整数的表示

b 进制：n = a(k-1)b^(k-1) + a(k-2)b^(k-2) + ... + a₁b¹ + a₀b⁰
例如，把十六进制 ABC8 转为十进制
(ABC8)₁₆ = 10·16³ + 11·16² + 12·16¹ + 8·16⁰ = (43796)₁₀

最大公因数，广义欧几里得除法

A）最大公因数
所有公因数中最大的那个整数，记作 ( a1，...，an )

B）广义欧几里得除法

最小公倍数，整除的进一步性质

A）最小公倍数
所有公倍数中最小的那个正整数，记作 [ a1，...，an ]
B）整除的进一步性质
① 若 c | ab、(a，c) = 1，则 c | b
② 若 p 是素数，p | ab，则 p | a 或 p | b
③ 若 a₁，a₂，...，an 是 D 的公倍数，则 D | [ a1，...，an ]

整数分解

A）真因数
不包括这个数本身的所有因数，例如 6 的真因数是 1、2、3
B）整数分解定理
若 n | a² - b²，n 不整除 a+b、a-b
则 (n，a+b)、(n，a-b) 是 n 的真因数

素数的算术基本定理

任一大于 1 的整数可表示为素数的乘积，且表达式唯一
① 写出 45、49、100、128 的因数分解式
45 = 3 · 3 · 9，49 = 7 · 7，100 = 2 · 2 · 5 · 5，128 = 2 · 2 · 2 · 2 · 2 · 2 · 2
② 写出 45、49、100、128 的标准分解式
45 = 3² · 9，49 = 7²，100 = 2² · 5²，128 = 2⁷

素数定理

A）π (x)
表示不超过 x 的素数个数，例如 π (2) = 1，π (10) = 4
B）素数定理
lim(x->∞) π(x) / x / lnx = 1

第二章同余

同余

剩余类，完全剩余系

A）剩余类，剩余
Ca = { c | c∈Z，c ≡ a (mod m) }
Ca 叫做模 m 的剩余类，c 叫做该类的剩余
例如：a = 2，m = 10
Ca = { c | c∈Z，c ≡ 2 (mod 10) } 是剩余类，12、22、32 ... 都是该类的剩余
B）完全剩余系
① r0，r1，... ，rm-1 是模 m 的完全剩余系充要条件：r 的模 m 两两不同余

② k 遍历模 m 的完全剩余系，若 (a, m) = 1，则 ak +b 也遍历
例：m = 10，a = 7，b = 5
因为 1，2，... ，9 遍历完全剩余系，则 5，12，... ，68 也是模 m 的完全剩余系
C）两个模的完全剩余系
(m1, m2) = 1，若 k1、k2 遍历模 m1、m2 的完全剩余系
则 k1·m2 + k2·m1 也遍历模 m1、m2 的完全剩余系
D）多个模的完全剩余系
(m1, ... , mx) = 1，若 ki 遍历模 mi 的完全剩余系
则 k1(m2m3...mx) + k2(m1m3...mx) + ... + kx(m1m2...mx-1) 也遍历模 mi 的完全剩余系

欧拉函数，简化剩余系

A）欧拉函数
整数 1, 2, ... , m-1 中与 m 互素的个数叫做欧拉函数，记作：φ(m)
例如：m = 10，则 1, 3, 7, 9 与 10 互素，φ(m) = 4
B）简化剩余类，简化剩余系
① Ca = { c | c∈Z，c ≡ a (mod m) }，且 (a, m) = 1
Ca 叫做模 m 的简化剩余类，则 c 叫做该类的简化剩余
例如：a = 3，m = 10，因为 (3, 10) = 1
所以 Ca = { c | c∈Z，c ≡ 3 (mod 10) } 是简化剩余类，13、23 ... 都是该类的简化剩余

② 若 r1, r2 都是模 m 的剩余，则 r1 与 m 互素的充要条件：r2 与 m 互素
③ 两个简化剩余的乘积，仍是简化剩余
④ (a, m) = 1，若 k 遍历模 m 的简化剩余系，则 a·k 也遍历
例如：(7, 30) = 1，1, 7, ... , 29 遍历模 30 的简化剩余系，则 7, 49, ... , 203 也遍历
⑤ 若 (a, m) = 1，则存在唯一 s、t 使得：sa + tm = 1，即 a·s ≡ 1 (mod m)
例如：a = 635, m = 737, 由广义欧几里得除法得 s = -224, t = 193
所以 636·(-224) + 193·737 = 1，使得 636·(-224) ≡ 1 (mod 737)
C）两个模的简化剩余系
(m1, m2) = 1，若 k1、k2 遍历模 m1、m2 的简化剩余系
则 k1·m2 + k2·m1 也遍历模 m1、m2 的简化剩余系
D）欧拉函数的性质
① φ(mn) = φ(m) φ(n)
② 若 m = p1^α1 ... pk^αk，则 φ(m) = n (1 - 1/p1) ... (1 - 1/pk)
例如：m = 49 = 7²，则 φ(49) = 7² (1 - 1/7) = 42
③ 若 p、q 是素数，则 φ(pq) = pq - p - q + 1

欧拉定理，费马小定理，Wilson 定理

A）欧拉定理
若 (a, m) = 1，φ(m) = x，则 a^x ≡ 1 (mod m)
B）费马小定理

若 p 是素数，则 a^p ≡ a (mod p)

C）Wilson 定理
若 p 为素数，则 (p-1) ! ≡ -1 (mod p)

模重复平方计算法

第三章同余式

一次同余式

A）同余式
① f (x) = anx^n + ... + a1x + a0
同余式：f (x) ≡ 0 (mod m) 叫模 m 的同余式
n 次同余式：n ≠ 0，n 叫 f (x) 的次数，记为 degf
② f (a) ≡ 0 (mod m)，则 x ≡ a (mod m) 叫同余式的解

B）一次同余式
① ax ≡ 1 (mod m) 有解且唯一的充要条件：(a, m) = 1
② 若 a a' = 1 (mod m)，则 a' 叫 a 的模 m 逆元
a 是模 m 的简化剩余充要条件：a 是模 m 的逆元
③ ax ≡ b (mod m) 有解的充要条件：(a, m) | b
当其有解时，x ≡ x0 + t · m/(a,m) (mod m)，t = 0, 1 ... (a, m)-1

中国剩余定理

A）中国剩余定理

B）两个方程
x ≡ b1 (mod m1)，x ≡ b2 (mod m2)，(m1, m2) = 1
① x ≡ b1·m2'·m2 + b2·m1'·m1 (mod m1·m2)
② x ≡ b1·s·m2 + b2·t·m1 (mod m1·m2)，且 s·m2 + t·m1 = 1

C）算法优化

素数模的同余式

A）多项式欧几里得除法
f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a₁x + a₀
g (x) = x^m + x^m-1 ... + b₁x + b₀
则 f (x) = q (x) · g (x) + r (x)，deg r(x) < deg g(x)
B）素数模同余式的简化
f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a₁x + a₀ ≡ 0 (mod p)，且 p 不整除 a_n
则 f (x) = q (x) ( x^p - x ) + r (x)
C）素数模同余式的因式分解
① f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a₁x + a₀ ≡ 0 (mod p)
若 x ≡ ai (mod p) , (i = 1, ... , k) 是同余式 f (x) 的 k 个不同解
则 f (x) ≡ f_k (x) (x - a₁) (x - a₂) ... (x - a_k) (mod p)
其中 f_k (x) 是 n - k 次多项式，首项系数是 a_n
② p 是一个素数 ⇔ x ^p-1 - 1 ≡ (x - 1) ... [ x - (p -1) ] (mod p)
③ p 是一个素数 ⇔ (p - 1) ! + 1 ≡ 0 (mod p) ( Wilson 定理 )
D）素数模同余式的解数估计
① 同余式 f (x) 的解数 ≤ deg f (x)
其中 f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a₁x + a₀ ≡ 0 (mod p)，p 是素数
② 同余式 f(x) 有 n 个解 ⇔ x^p - x 被 f(x) 除的余式系数都是 p 的倍数
其中 f (x) = xⁿ + x^n-1 ... + a₁x + a₀ ≡ 0 (mod p)，p 是素数
③ p 是素数，则 d | p - 1 ⇔ x^d - 1 (mod p) 有 d 个不同根

第四章二次同余式，平方剩余

一般二次同余式

x ² ≡ a (mod m) ，(a , m) = 1
若同余式有解，则 a 叫做模 m 的平方剩余，否则 a 叫做模 m 的平方非剩余

模为奇素数

A）x ² ≡ a (mod p) ，(a , p) = 1 ，p 是奇素数
① a ^ (p-1/2) ≡ 1 (mod p) ⇔ a 是模 p 的平方剩余，二解
② a ^ (p-1/2) ≡ -1 (mod p) ⇔ a 是模 p 的平方非剩余，无解
B）(a1 , p) = 1 ，(a2 , p) = 1 ，p 是奇素数
① 若 a1 是模 p 的平方剩余、a2 是模 p 的平方剩余，则 a1 · a2 是模 p 的平方剩余
② 若 a1 是模 p 的平方剩余、a2 是模 p 的平方非剩余，则 a1 · a2 是模 p 的平方非剩余
③ 若 a1 是模 p 的平方非剩余、a2 是模 p 的平方非剩余，则 a1 · a2 是模 p 的平方剩余

勒让德符号

A）p 是素数，(a / p) 是勒让德符号
(a / p) = 0 ⇔ a | p ⇔ (a , p) ≠ 1
(a / p) = 1 ⇔ a 是模 p 的平方剩余 ⇔ x ² ≡ a (mod p) 有解
(a / p) = -1 ⇔ a 是模 p 的平方非剩余 ⇔ x ² ≡ a (mod p) 无解
B）p 是奇素数
① (1 / p) = 1
② (-1 / p) = (-1) ^ (p-1 / 2)
若 p ≡ 1 (mod 4) ，则 (-1 / p) = 1
若 p ≡ 3 (mod 4) ，则 (-1 / p) = -1
③ (2 / p) = (-1) ^ (p²-1 / 8)
④ (q / p) = (-1) ^ (q-1 / 2) (p-1 / 2) * (p / q)
⑤ (a / p) ≡ a ^ (p-1 / 2) (mod p)
⑥ 周期性：(a+p / p) = (a / p)
⑦ 可乘性：(a·b / p) = (a / p) (b / p)
⑧ 若 (a , p) = 1 ，则 (a² / p) = 1
⑨ 若 a ≡ b (mod p) ，则 (a / p) = (b / p)
⑩ x ⁴ ≡ -4（mod p) ⇔ p ≡ 1（mod 4)