一、考前復(fù)習(xí)

【1/3 題型說明】

填空題 10道，每道 2 分，共 20 分；
計(jì)算題 5 道，每道 8 分，共 40 分；
證明題 5 道，每道 8 分，共 40 分；

【2/3 復(fù)習(xí)題】

【3/3 往年真題】

二、學(xué)習(xí)筆記

第一章 整數(shù)的可除性

• 整除，歐幾里得除法

• 整數(shù)的表示

b 進(jìn)制：n = a(k-1)b^(k-1) + a(k-2)b^(k-2) + ... + a?b1 + a?b?
例如，把十六進(jìn)制 ABC8 轉(zhuǎn)為十進(jìn)制
(ABC8)?? = 10·163 + 11·162 + 12·161 + 8·16? = (43796)??

• 最大公因數(shù)，廣義歐幾里得除法

A）最大公因數(shù)
所有公因數(shù)中最大的那個(gè)整數(shù)，記作 ( a1，...，an )

B）廣義歐幾里得除法

• 最小公倍數(shù)，整除的進(jìn)一步性質(zhì)

A）最小公倍數(shù)
所有公倍數(shù)中最小的那個(gè)正整數(shù)，記作 [ a1，...，an ]
B）整除的進(jìn)一步性質(zhì)
① 若 c | ab、(a，c) = 1，則 c | b
② 若 p 是素?cái)?shù)，p | ab，則 p | a 或 p | b
③ 若 a?，a?，...，an 是 D 的公倍數(shù)，則 D | [ a1，...，an ]

• 整數(shù)分解

A）真因數(shù)
不包括這個(gè)數(shù)本身的所有因數(shù)，例如 6 的真因數(shù)是 1、2、3
B）整數(shù)分解定理
若 n | a2 - b2，n 不整除 a+b、a-b
則 (n，a+b)、(n，a-b) 是 n 的真因數(shù)

• 素?cái)?shù)的算術(shù)基本定理

任一大于 1 的整數(shù)可表示為素?cái)?shù)的乘積，且表達(dá)式唯一
① 寫出 45、49、100、128 的因數(shù)分解式
45 = 3 · 3 · 9，49 = 7 · 7，100 = 2 · 2 · 5 · 5，128 = 2 · 2 · 2 · 2 · 2 · 2 · 2
② 寫出 45、49、100、128 的標(biāo)準(zhǔn)分解式
45 = 32 · 9，49 = 72，100 = 22 · 52，128 = 2?

• 素?cái)?shù)定理

A）π (x)
表示不超過 x 的素?cái)?shù)個(gè)數(shù)，例如 π (2) = 1，π (10) = 4
B）素?cái)?shù)定理
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
因?yàn)?1，2，... ，9 遍歷完全剩余系，則 5，12，... ，68 也是模 m 的完全剩余系
C）兩個(gè)模的完全剩余系
(m1, m2) = 1，若 k1、k2 遍歷模 m1、m2 的完全剩余系
則 k1·m2 + k2·m1 也遍歷模 m1、m2 的完全剩余系
D）多個(gè)模的完全剩余系
(m1, ... , mx) = 1，若 ki 遍歷模 mi 的完全剩余系
則 k1(m2m3...mx) + k2(m1m3...mx) + ... + kx(m1m2...mx-1) 也遍歷模 mi 的完全剩余系

• 歐拉函數(shù)，簡(jiǎn)化剩余系

A）歐拉函數(shù)
整數(shù) 1, 2, ... , m-1 中與 m 互素的個(gè)數(shù)叫做歐拉函數(shù)，記作：φ(m)
例如：m = 10，則 1, 3, 7, 9 與 10 互素，φ(m) = 4
B）簡(jiǎn)化剩余類，簡(jiǎn)化剩余系
① Ca = { c | c∈Z，c ≡ a (mod m) }，且 (a, m) = 1
Ca 叫做模 m 的簡(jiǎn)化剩余類，則 c 叫做該類的簡(jiǎn)化剩余
例如：a = 3，m = 10，因?yàn)?(3, 10) = 1
所以 Ca = { c | c∈Z，c ≡ 3 (mod 10) } 是簡(jiǎn)化剩余類，13、23 ... 都是該類的簡(jiǎn)化剩余

② 若 r1, r2 都是模 m 的剩余，則 r1 與 m 互素的充要條件：r2 與 m 互素
③ 兩個(gè)簡(jiǎn)化剩余的乘積，仍是簡(jiǎn)化剩余
④ (a, m) = 1，若 k 遍歷模 m 的簡(jiǎn)化剩余系，則 a·k 也遍歷
例如：(7, 30) = 1，1, 7, ... , 29 遍歷模 30 的簡(jiǎn)化剩余系，則 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）兩個(gè)模的簡(jiǎn)化剩余系
(m1, m2) = 1，若 k1、k2 遍歷模 m1、m2 的簡(jiǎn)化剩余系
則 k1·m2 + k2·m1 也遍歷模 m1、m2 的簡(jiǎn)化剩余系
D）歐拉函數(shù)的性質(zhì)
① φ(mn) = φ(m) φ(n)
② 若 m = p1^α1 ... pk^αk，則 φ(m) = n (1 - 1/p1) ... (1 - 1/pk)
例如：m = 49 = 72，則 φ(49) = 72 (1 - 1/7) = 42
③ 若 p、q 是素?cái)?shù)，則 φ(pq) = pq - p - q + 1

• 歐拉定理，費(fèi)馬小定理，Wilson 定理

A）歐拉定理
若 (a, m) = 1，φ(m) = x，則 a^x ≡ 1 (mod m)
B）費(fèi)馬小定理

若 p 是素?cái)?shù)，則 a^p ≡ a (mod p)

C）Wilson 定理
若 p 為素?cái)?shù)，則 (p-1) ! ≡ -1 (mod p)

• 模重復(fù)平方計(jì)算法

第三章 同余式

• 一次同余式

A）同余式
① f (x) = anx^n + ... + a1x + a0
同余式：f (x) ≡ 0 (mod m) 叫模 m 的同余式
n 次同余式：n ≠ 0，n 叫 f (x) 的次數(shù)，記為 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 的簡(jiǎn)化剩余充要條件：a 是模 m 的逆元
③ ax ≡ b (mod m) 有解的充要條件：(a, m) | b
當(dāng)其有解時(shí)，x ≡ x0 + t · m/(a,m) (mod m)，t = 0, 1 ... (a, m)-1

• 中國剩余定理

A）中國剩余定理

B）兩個(gè)方程
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）算法優(yōu)化

• 素?cái)?shù)模的同余式

A）多項(xiàng)式歐幾里得除法
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）素?cái)?shù)模同余式的簡(jiǎn)化
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）素?cái)?shù)模同余式的因式分解
① 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 個(gè)不同解
則 f (x) ≡ f_k (x) (x - a?) (x - a?) ... (x - a_k) (mod p)
其中 f_k (x) 是 n - k 次多項(xiàng)式，首項(xiàng)系數(shù)是 a_n
② p 是一個(gè)素?cái)?shù) ? x ^p-1 - 1 ≡ (x - 1) ... [ x - (p -1) ] (mod p)
③ p 是一個(gè)素?cái)?shù) ? (p - 1) ! + 1 ≡ 0 (mod p) ( Wilson 定理 )
D）素?cái)?shù)模同余式的解數(shù)估計(jì)
① 同余式 f (x) 的解數(shù) ≤ deg f (x)
其中 f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a?x + a? ≡ 0 (mod p)，p 是素?cái)?shù)
② 同余式 f(x) 有 n 個(gè)解 ? x^p - x 被 f(x) 除的余式系數(shù)都是 p 的倍數(shù)
其中 f (x) = xⁿ + x^n-1 ... + a?x + a? ≡ 0 (mod p)，p 是素?cái)?shù)
③ p 是素?cái)?shù)，則 d | p - 1 ? x^d - 1 (mod p) 有 d 個(gè)不同根

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

• 一般二次同余式

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

• 模為奇素?cái)?shù)

A）x 2 ≡ a (mod p) ，(a , p) = 1 ，p 是奇素?cái)?shù)
① 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 是奇素?cái)?shù)
① 若 a1 是模 p 的平方剩余、a2 是模 p 的平方剩余，則 a1 · a2 是模 p 的平方剩余
② 若 a1 是模 p 的平方剩余、a2 是模 p 的平方非剩余，則 a1 · a2 是模 p 的平方非剩余
③ 若 a1 是模 p 的平方非剩余、a2 是模 p 的平方非剩余，則 a1 · a2 是模 p 的平方剩余

• 勒讓德符號(hào)

A）p 是素?cái)?shù) ，(a / p) 是勒讓德符號(hào)
(a / p) = 0 ? a | p ? (a , p) ≠ 1
(a / p) = 1 ? a 是模 p 的平方剩余 ? x 2 ≡ a (mod p) 有解
(a / p) = -1 ? a 是模 p 的平方非剩余 ? x 2 ≡ a (mod p) 無解
B）p 是奇素?cái)?shù)
① (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) ^ (p2-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 ，則 (a2 / p) = 1
⑨ 若 a ≡ b (mod p) ，則 (a / p) = (b / p)
⑩ x ? ≡ -4（mod p) ? p ≡ 1（mod 4)

• 雅可比符號(hào)

• 模平方根

• x2 + y2 = p

若 p 是素?cái)?shù) ，則 x2 + y2 = p 有解 ? p = 2 或 p = 4k + 1

第五章 原根，指標(biāo)

A）指數(shù)
① 指數(shù)定義
若 (a,m) = 1，e 是滿足 a^e ≡ 1 (mod m) 的最小正整數(shù)
則 e 叫 a 對(duì)模 m 的指數(shù)，記作 ordm (a)
若 ordm (a) = φ(m)，則 a 叫模 m 的原根

② 指數(shù)性質(zhì)

③ 指數(shù)構(gòu)造

B）原根

C）指標(biāo)

第六章 素性檢驗(yàn)

• 偽素?cái)?shù)

第八章 群

• 群

< 思維導(dǎo)圖 >