一 同餘, 剩餘類與剩餘系 (a) 同餘的性質 : (1) a b (mod m),c d (mod m), 則 a ± c b ± d (mod m) 且 ac bd (mod m) (2) a b (mod m),c N, 則 ac bc (mod cm) (3) a b (mod m),n N 且 n m, 則 a b (mod n) (4) 若 a b (mod m), 則 (a,m)=(b,m) (5) 整數 a,b, 則 ab 1 (mod m) ff (a,m)=1 (b) 剩餘類 : m 為正整數, 將全體整數按照對模 m 的餘數進行分類, 餘數為 r ( 0 r m 1) 的所有整數歸為一類, 記為 K r (r=0,1,..,m-1), 每一類 K r 均稱為模 m 的剩餘類 ( 同餘類 ) 剩餘類 K r 是數集 K r ={mq+r m 是模,r 是餘數,q Z}={a a Z 且 a r (mod m) }, 它是一個以 m 為公差的 ( 雙邊無窮 ) 等差數集並具有如下的性質 : (1) Z = K 0 K1 K 2 L K m 1 且 K K = ( j ) j (2) 對於任意的 n Z, 有唯一的 r 0 使 n K r 0 (3) 對於任意的 a b Z,a b K r a b(mod m) (c) 完全剩餘系 : 設 K 0,K 1,,K m-1 是模 m 的全部剩餘類, 從每個 K r 中取任取一個數 a r, 這 m 個數 a 0,a 1,,a m-1 組成的一個數組稱為模 m 的一個完全剩餘系 (d) 簡化剩餘系 : 如果一個模 m 的剩餘類 K r 中任一數都與 m 互質, 就稱 K r 是一個與模 m 互質的剩餘 類在與模 m 互質的每個剩餘類中, 任取一個數 ( 共 ϕ (m) 個 ) 所組成的數組, 稱為 模 m 的一個簡化剩餘系 Page 1
Page 2
( 二 ) 高觀點 : 同餘類環 (rng) 1. 等價關係 : 給集合 S 中一個關係 ~ S 中元素有此關係便記為 a ~ b 我們希望把 S 中所有的元素分成一些更小的子集 S 1,S 2, 使得同一子集中任何兩個元素都有此關係, 而不同子集中的任何兩個元素都沒有此關係 對於集合 S, ~ 是定義在 S 中的一種關係, 若此關係滿足 : (1) 自反性 (Reflexve): a S,a ~ a (2) 對稱性 (Symmetrc): 若 a ~ b, 則 b ~ a (3) 傳遞性 (Transtve): 若 a ~ b 且 b ~ c, 則 a ~ c 則此種關係稱為等價關係 例如 : = 是等價關係 ; > 不是等價關係 模 m 同餘 是整數集合中的一個等價關係 2. 同餘類 : 所有模 m 彼此同餘的整數組成一類, 稱為整數的一個模 m 同餘類整數 a 所在的同餘類記為 [a] (1) 對任意整數 a 與 b, [a]=[b] ff a b (mod m) (2) Z m ={[0],[1],,[m-1]} 完全剩餘系 : 在 m 個同餘類中每個同餘類取一個整數, 這 m 個整數稱為完全剩餘系, 簡稱 ( 模 m 的 ) 完系例如 :Z 3 ={-1,0,1}={0,2,4} 引理 (1) 若 {a 1,a 2,,a n } 是模 m 完系,b N 且 (b,m)=1, 則 {ba 1,ba 2,,ba n } 也是模 m 完系 (2) m n N 且 (m,n)=1, 若 {a 1,a 2,,a n } 和 {b 1,b 2,,b n } 分別為模 m 和模 n 的完系, 則 {na +mb j (1 m,1 j n)} 是模 mn 的完系 3. 環 : 一個包含有加 減 乘三種運算並且滿足結合律, 分配律, 交換律的集合 由同餘式的性質我們可以定義 : [a]+[b]=[a+b] ; [a]-[b]=[a-b] ; [ a] [ b] = [ a b] Page 3
所以 Z m 中可以自然的進行加 減 乘三種運算, 稱為 ( 模 m) 同餘類環 性質 Z m 中, 每個元素的 m 倍均為零 n[a]=[a]+[a]+ +[a]=[na], 則 m[a]=[ma]=[0] 4. Z m 中的除法運算 : 由性質 (2): 對於在環 Z m 中的元素 [a], 存在 [b] 使得 [ a ] [ b] = [1] ff (a,m)=1我們把 [b] 記為 [a] -1, 稱為元素 [a] 的逆元素,[a] 稱為可逆元素我們可以用可逆元素去除 Z m 中的任何元素 : 若 [a] 可逆,[a][x]=[b], 則 [a] -1 [a][x]=[a] -1 [b], 所以 [x]=[a] -1 [ b] [b]= [ a ] 5. 域 : 一個包含有加 減 乘 除四則運算的集合當 p 為質數,Z p ={[0],[1],,[p-1]}, 除了 [0] 以外, 其餘 p-1 個元素都是可逆元素 ( 1,2,,(p-1) 均與 p 互質 ), 所以 Z p 中的每個非零元素都可以作為分母去除其他元素, 即 Z p 中的元素可以作四則運算 ( 只是 0 不能為分母 ), 我們稱為 p 元有限域 例 1 Fermat 小定理 : 當 p 為質數時, 若 (a,p)=1,a p 1 1 (mod p) ϕ ( ) 例 2 Euler 定理 :a Z,m N, 設 (a,m)=1, 則有 a m 1 (mod m) 例 3 (1) a Z,(a,m)=1, 則必存在 n N, 使得 a n 1 (mod m) (2) 設 n 是滿足 (1) 中的最小正整數, 則對於每個 r N, a r 1 (mod m) ff n r 例 4 p 為質數且 p=4k+1 若且唯若存在一個整數 a, 使得 a 2 1 (mod p) Page 4
二 幾個著名定理 定理一 : Euler 定理 a Z,m N, 設 (a,m)=1, 則有 ϕ ( ) a m 1 (mod m) 定理二 : Fermat 小定理 當 p 為質數時, 對任意 a 有 a p a (mod p); 特別的, 若 (a,p)=1,a p 1 1 (mod p) 定理三 : Wlson 定理 設 p 為質數, 則 (p 1)! 1 (mod p) Wlson 定理的逆命題 若 n 為大於 5 的合成數, 則 (n 1)! 0 (mod n) 定理四 : 中國剩餘定理 設 m,n 是互質的正整數 ;a,b 為整數, 則同餘式 x a (mod m) 有共同解 x 0 ; x b (mod n) 且所有的共同整數解 x 也是一個同餘式 :x x 0 (mod nm) 設 m 1,m 2,,m k 是兩兩互質的正整數, 則對於任意整數 c 1,c 2,,c k, 存在整數 x 使得 x c (mod m ), 1 k 同時成立並且在模 m 1 m 2 m k 的意義下, 上述的同餘方程組的解是唯一的, 可表示為 x x 0 (mod m 1 m 2 m k ) m1m2 Lmk 其中 x 0 可以這樣確定 : 令 M =, M 1 是 M 關於模 m 的數論倒數, 則 m x k 1 0 = M M c = 1 定理五 : Lagrange 定理設 p 是質數, 多項式 f(x)=a n x n +a n-1 x n-1 + +a 1 x+a 0 是一個模 p 為 n 次的整係數多項式 ( 即 p 不整除 a n ), 則同餘方程 f(x) 0 (mod p) 至多有 n 個解 ( 在模 p 的意義下 ) 設 p 是質數, 設 f(x) (x+1)(x+2) (x+p-1) x p-1 +A 1 x p-2 + +A p-2 x+a p-1 則 A 1 A 2... A p-1 皆可為 p 整除 Page 5
n p 1 例題 1: 設 p 為奇質數,a n 為正整數, 且 p a 1, 證明 : p n a 1又問 : 當 p=2 時, 命題是否依然成立? 證明 : 注 此題綜合運用了二項式定理 代數式變形和費馬小定理, 其中利用費馬小定理確定 a 與 p 的關係是關鍵的第一步 例題 2: 對正整數 n, 如果對任意的正整數 a, 只要 n n a 2 1, 就有 n n a 1, 則稱 n 具有 性質 P 證明: (1) 每個質數都具有性質 P; (2) 存在無窮多個合數具有性質 P 證明 : Page 6
例題 3: 證明 : 不存在非負整數 k 與 m, 使得 : k!+48=48(k+1) m 證明 : 例題 4: 設 a,b N,p 為奇質數, 且 p>a>b>1 求最大的整數 c, 使得對於所有滿足上述 c ap a n( n 1) L( n k + 1) 條件的 a b p, 都有 p Cbp Cb, 此處的 C n k = k! 證明 : 注 此題將 A 中各乘積式展開後, 容易證明 p 2 A, 為了證明 p 3 A, 先用 Lagrange 定 理推出 α 1 α 2... α p 2 皆為 p 的倍數, 進而 p 2 α1 是解決該題的關鍵 Page 7
練習 第一部分 :( 大黃 ) 1. 設 p 為奇質數, 求證 :2 p 1 有 2kp+1 形式的質因數 2. 設 p 為奇質數, 證明 :1 2 3 2 (p 2) 2 2 ( 1) p+ 1 (mod p) 3. 設 p 為質數,a p b p (mod p) 求證:a p b p (mod p 2 ) 4. 設 p 為奇質數,x,y 為互質的整數且 p x 2 +y 2 證明 :(1) 存在整數 n 使得 p 1+n 2 (2)p 1 (mod 4) Hnt:(x 2 +y 2 )(a 2 +b 2 )=(ax+by) 2 +(ay bx) 2 5. 設 p 為奇質數求證 : 在 1,2,3, p 1 中恰有 第二部分 : p 1 個關於模 p 與一個平方數 2 1. 設 n 是大於 1 的正整數, 證明 :n 為質數 ff 則 (n 1)! 1 (mod n) 2. 設 p 為質數, 證明 : 數列 {2 n n n N } 中有無窮多項為 p 的倍數 3. 設正整數 a,d 互質, 證明 : 在等差數列 {a+kd k = 0,1,2, }, 中有無窮多項具有相同的 質因子 4. 2( 1) 設 p,q 為奇質數,2p=q+1,x N, 且 (x,2pq)=1, 證明 : x p 1 (mod16 pq) 5. ( ) ( ) 設 m,n N, 且 (m,n)=1, 證明 : m m n + n 1 (mod mn) 6. p p q q ( 5 2 )(5 2 ) 求所有的質數 p,q, 使得是一個整數 pq 7. 設 p 為質數,a,n N, 證明 : 若 2 p +3 p =a n, 則 n=1 8. 求一個自然數 n, 使得 n,n+1,,n+20 中的每一個數都與 3030 有大於 1 的公因數 9. 設 m,n N,p 為質數, 且對於任意的 k N, 均有 (pk-1,m)=(pk-1,n)證明: 存 在某個 t Z, 使得 m= p t n 10. 設 p>3,p 為質數, 且設 + 1 + + 1 r 1 L 2 p =,(r,s)=1,r,s N, ps 證明 : p 3 r s f ( n) 11. 設 f(n) 是使得和式 k 能被正整數 n 整除的最小正整數證明 : k = 1 f(n)=2n-1 ff n=2 m,m 為非負整數 12. 設 n>1,n 為奇數證明 : 對於任意的 m N,n 都無法整除 m n-1 +1 Page 8