一怠晴、考前復(fù)習

【1/3 題型說明】

填空題 10道遥金，每道 2 分，共 20 分蒜田；
計算題 5 道稿械，每道 8 分，共 40 分冲粤；
證明題 5 道美莫，每道 8 分，共 40 分梯捕；

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

【3/3 往年真題】

二厢呵、學習筆記

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

• 整除，歐幾里得除法

• 整數(shù)的表示

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

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

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

B）廣義歐幾里得除法

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

A）最小公倍數(shù)
所有公倍數(shù)中最小的那個正整數(shù)错英，記作 [ a1入撒，...，an ]
B）整除的進一步性質(zhì)
① 若 c | ab椭岩、(a茅逮，c) = 1，則 c | b
② 若 p 是素數(shù)判哥，p | ab献雅，則 p | a 或 p | b
③ 若 a?，a?塌计，...挺身，an 是 D 的公倍數(shù)，則 D | [ a1锌仅，...章钾，an ]

• 整數(shù)分解

A）真因數(shù)
不包括這個數(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ù)

• 素數(shù)的算術(shù)基本定理

任一大于 1 的整數(shù)可表示為素數(shù)的乘積株搔，且表達式唯一
① 寫出 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 的標準分解式
45 = 32 · 9糊啡，49 = 72，100 = 22 · 52吁津，128 = 2?

• 素數(shù)定理

A）π (x)
表示不超過 x 的素數(shù)個數(shù)棚蓄，例如 π (2) = 1，π (10) = 4
B）素數(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
因為 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 的完全剩余系

• 歐拉函數(shù)沮趣，簡化剩余系

A）歐拉函數(shù)
整數(shù) 1, 2, ... , m-1 中與 m 互素的個數(shù)叫做歐拉函數(shù)，記作：φ(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）歐拉函數(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 是素數(shù)汪厨，則 φ(pq) = pq - p - q + 1

• 歐拉定理，費馬小定理愉择，Wilson 定理

A）歐拉定理
若 (a, m) = 1劫乱，φ(m) = x织中，則 a^x ≡ 1 (mod m)
B）費馬小定理

若 p 是素數(shù)，則 a^p ≡ a (mod p)

C）Wilson 定理
若 p 為素數(shù)衷戈，則 (p-1) ! ≡ -1 (mod p)

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

第三章 同余式

• 一次同余式

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 的簡化剩余充要條件：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）算法優(yōu)化

• 素數(shù)模的同余式

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）素數(shù)模同余式的簡化
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）素數(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 個不同解
則 f (x) ≡ f_k (x) (x - a?) (x - a?) ... (x - a_k) (mod p)
其中 f_k (x) 是 n - k 次多項式嫡纠，首項系數(shù)是 a_n
② p 是一個素數(shù) ? x ^p-1 - 1 ≡ (x - 1) ... [ x - (p -1) ] (mod p)
③ p 是一個素數(shù) ? (p - 1) ! + 1 ≡ 0 (mod p) ( Wilson 定理 )
D）素數(shù)模同余式的解數(shù)估計
① 同余式 f (x) 的解數(shù) ≤ deg f (x)
其中 f (x) = a_n xⁿ + a_n-1 x^n-1 ... + a?x + a? ≡ 0 (mod p)烦租，p 是素數(shù)
② 同余式 f(x) 有 n 個解 ? x^p - x 被 f(x) 除的余式系數(shù)都是 p 的倍數(shù)
其中 f (x) = xⁿ + x^n-1 ... + a?x + a? ≡ 0 (mod p)，p 是素數(shù)
③ p 是素數(shù)除盏，則 d | p - 1 ? x^d - 1 (mod p) 有 d 個不同根

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

• 一般二次同余式

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

• 模為奇素數(shù)

A）x 2 ≡ a (mod p) ，(a , p) = 1 踱侣，p 是奇素數(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 是奇素數(shù)
① 若 a1 是模 p 的平方剩余、a2 是模 p 的平方剩余待榔，則 a1 · a2 是模 p 的平方剩余
② 若 a1 是模 p 的平方剩余逞壁、a2 是模 p 的平方非剩余，則 a1 · a2 是模 p 的平方非剩余
③ 若 a1 是模 p 的平方非剩余锐锣、a2 是模 p 的平方非剩余腌闯，則 a1 · a2 是模 p 的平方剩余

• 勒讓德符號

A）p 是素數(shù) ，(a / p) 是勒讓德符號
(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 是奇素數(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)

• 雅可比符號

• 模平方根

• x2 + y2 = p

若 p 是素數(shù) 分瘦，則 x2 + y2 = p 有解 ? p = 2 或 p = 4k + 1

第五章 原根蘸泻，指標

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

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

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

B）原根

C）指標

第六章 素性檢驗

• 偽素數(shù)

第八章 群

• 群

< 思維導圖 >