剩余类与剩余系

《剩余类与剩余系》由会员分享，可在线阅读，更多相关《剩余类与剩余系（8页珍藏版）》请在金锄头文库上搜索。

1、Page 1一、同餘，剩餘類與剩餘系(a) 同餘的性質：(1) ab (mod m)，cd (mod m)，則 a cb d (mod m) 且 acbd (mod m )。(2) ab (mod m)，c N， 則 acbc (mod cm )。(3) ab (mod m)，n N 且 ， 則 ab (mod n)。(4) 若 ab (mod m)，則 (a，m)(b，m)。 (5) 整數 a，b，則 ab1 (mod m) iff (a，m)1。 (b) 剩餘類：m 為正整數，將全體整數按照對模 m 的餘數進行分類，餘數為 r ( ) 的10m所有整數歸為一類，記為 Kr (r=0,1,.

2、,m-1)，每一類 Kr 均稱為模 m 的剩餘類 (同餘類)。剩餘類 Kr 是數集 Kr=mq+r 是模，r 是餘數， qZa 且 ，aod它是一個以 m 為公差的(雙邊無窮)等差數集。 並具有如下的性質：(1) 且 ( )。1210mZLji ji(2) 對於任意的 ，有唯一的 r0 使 。Zn0rKn(3) 對於任意的 a、b ，a、b r)(odmba(c) 完全剩餘系：設 K0，K 1， ，K m-1 是模 m 的全部剩餘類，從每個 Kr 中取任取一個數 ar，這 m 個數 a0，a 1，a m-1 組成的一個數組稱為模 m 的一個完全剩餘系。(d) 簡化剩餘系：如果一個模 m 的剩餘

3、類 Kr 中任一數都與 m 互質，就稱 Kr 是一個與模 m 互質的剩餘類。在與模 m 互質的每個剩餘類中，任取一個數 (共 個) 所組成的數組，稱為模 m 的一個簡化剩餘系。Page 2(二) 高觀點： 同餘類環 (ring)1. 等價關係：給集合 S 中一個關係 ”。S 中元素有此關係便記為 a b。我們希望把 S 中所有的元素分成一些更小的子集 S1，S 2，使得同一子集中任何兩個元素都有此關係，而不同子集中的任何兩個元素都沒有此關係。對於集合 S， ” ” 是定義在 S 中的一種關係，若此關係滿足：(1) 自反性 (Reflexive)： ，a a 。(2) 對稱性 (Symmetri

4、c)：若 a b，則 b a。(3) 傳遞性 (Transitive)：若 a b 且 b c，則 a c。則此種關係稱為等價關係。例如：” 是等價關係； ”不是等價關係。“模 m 同餘” 是整數集合中的一個等價關係。2. 同餘類：所有模 m 彼此同餘的整數組成一類，稱為整數的一個模 m 同餘類。整數 a 所在的同餘類記為a。(1) 對任意整數 a 與 b，ab iff ab (mod m)(2) Zm0 ，1，m1完全剩餘系：在 m 個同餘類中每個同餘類取一個整數，這 m 個整數稱為完全剩餘系，簡稱 (模 m 的)完系。例如：Z 31，0，1 0，2，4【引理】(1) 若 a1，a 2，a

5、n 是模 m 完系， b N 且(b，m)1，則 ba1， ba2，ba n 也是模 m 完系。(2) m、n N 且 (m，n)1，若 a1，a 2，a n和b 1，b 2，b n分別為模 m 和模 n 的完系，則 naimb j (1 i m，1 j n)是模 mn 的完系。3. 環：一個包含有加、減、乘三種運算並且滿足結合律，分配律，交換律的集合。由同餘式的性質我們可以定義：ab ab ； ab ab ； 。ba所以 Zm 中可以自然的進行加、減、乘三種運算，稱為 (模 m) 同餘類環。Page 3【性質】Z m 中，每個元素的 m 倍均為零。na a aana，則 ma ma0。4.

6、Zm 中的除法運算：由性質(2)：對於在環 Zm 中的元素 a，存在 b 使得 iff (a，m)1。ba我們把 b 記為 a-1，稱為元素 a的逆元素，a稱為可逆元素。我們可以用可逆元素去除 Zm 中的任何元素：若a可逆，ax=b，則a -1ax a-1b，所以 x a-1b5. 域：一個包含有加、減、乘、除四則運算的集合。當 p 為質數，Z p0，1，p1，除了0以外，其餘 p1 個元素都是可逆元素 ( 1,2,(p-1) 均與 p 互質)，所以 Zp 中的每個非零元素都可以作為分母去除其他元素，即 Zp 中的元素可以作四則運算 (只是 0 不能為分母) ，我們稱為 p 元有限域。【例 1

7、】 Fermat 小定理：當 p 為質數時，若(a,p)=1，a p11 (mod p)。【例 2】 Euler 定理：a Z， m N，設 (a,m)=1，則有 。(mod)(a【例 3】 (1) a Z，(a，m)1，則必存在 n N，使得 n(2) 設 n 是滿足 (1)中的最小正整數，則對於每個 r N， iff 。)(od1arrn【例 4】 p 為質數且 p4k+1 若且唯若 存在一個整數 a，使得 a21 (mod p)。Page 4二、幾個著名定理定理一： Euler 定理 a Z， m N，設 (a,m)=1，則有 。)(mod1)(a定理二： Fermat 小定理當 p 為

8、質數時，對任意 a 有 apa (mod p)；特別的，若(a,p)=1，a p11 (mod p)。定理三： Wilson 定理設 p 為質數，則 (p1)!1 (mod p) 。Wilson 定理的逆命題若 n 為大於 5 的合成數，則 (n1)!0 (mod n)定理四： 中國剩餘定理設 m,n 是互質的正整數；a,b 為整數，則同餘式 有共同解 x0；)(modnbxa且所有的共同整數解 x 也是一個同餘式：xx 0 (mod nm) 。設 m1,m2，m k 是兩兩互質的正整數，則對於任意整數 c1,c2，c k，存在整數 x 使得 ， )(odiicki1同時成立。並且在模 m1m

9、2mk 的意義下，上述的同餘方程組的解是唯一的，可表示為 xx0 (mod m1m2mk) 。其中 x0 可以這樣確定：令 ， 是 Mi 關於模 mi 的數論倒數，則ikiML211i。kiiic110定理五： Lagrange 定理設 p 是質數，多項式 f(x)a nxna n-1xn-1a 1xa 0 是一個模 p 為 n 次的整係數多項式 (即 p 不整除 an)，則同餘方程 f(x)0 (mod p) 至多有 n 個解(在模 p 的意義下)。設 p 是質數，設 f(x)(x1)( x2)(xp1) x p-1A 1 xp-2A p-2 xA p-1則 A1、A 2、.、A p-1 皆

10、可為 p 整除。Page 5例題 1： 設 p 為奇質數，a、n 為正整數，且 ，證明： 。1pna1apn又問：當 p=2 時，命題是否依然成立？證明： 【注】此題綜合運用了二項式定理、代數式變形和費馬小定理，其中利用費馬小定理確定 a與 p 的關係是關鍵的第一步。例題 2： 對正整數 n，如果對任意的正整數 a，只要 ，就有 ，則稱 n 具有1n12na性質 P。證明： (1) 每個質數都具有性質 P； (2) 存在無窮多個合數具有性質 P。證明： Page 6例題 3： 證明：不存在非負整數 k 與 m，使得： k!4848(k1) m 。 證明： 例題 4： 設 a，b N，p 為奇質

11、數，且 pab1。求最大的整數 c，使得對於所有滿足上述條件的 a、b、p，都有 ，此處的 。 cC!)1()knnkL證明： 【注】此題將 A 中各乘積式展開後，容易證明 ，為了證明 ，先用 Lagrange 定Ap2Ap3理推出 、 、.、 皆為 p 的倍數，進而 是解決該題的關鍵。122p 12Page 7【練習】第一部分：(大黃)1. 設 p 為奇質數，求證：2 p1 有 2kp+1 形式的質因數。2. 設 p 為奇質數，證明：1 232(p2)2 (mod p)21)p3. 設 p 為質數，a pbp (mod p)。求證：a pbp (mod p2)。4. 設 p 為奇質數，x ,

12、y 為互質的整數且 p|x2+y2。證明：(1) 存在整數 n 使得 p|1+n2。(2)p1 (mod 4)。Hint：( x2+y2)(a2+b2)=(ax+by)2+(aybx)25. 設 p 為奇質數。求證：在 1,2,3, p1 中恰有 個關於模 p 與一個平方數。21第二部分：1. 設 n 是大於 1 的正整數，證明：n 為質數 iff 則 (n1)!1 (mod n) 。2. 設 p 為質數，證明：數列 2nn 中有無窮多項為 p 的倍數。 N3. 設正整數 a，d 互質，證明：在等差數列akd ，中有無窮多項具有相同0,2k的質因子。 4. 設 p，q 為奇質數，2pq1，x

13、N，且(x ，2 pq)1，證明： 。)16(mod)1(2pqxp5. 設 m，n N，且 (m，n)1，證明： (od)()( nnm6. 求所有的質數 p，q，使得 是一個整數。pq5(7. 設 p 為質數，a，n N，證明：若 2p3 pa n，則 n1。8. 求一個自然數 n，使得 n，n1，n20 中的每一個數都與 3030 有大於 1 的公因數。9. 設 m，n N，p 為質數，且對於任意的 k N，均有 (pk1，m )(pk1，n)。證明：存在某個 t Z，使得 m 。pt10. 設 p3，p 為質數，且設，(r，s)1，r，s N，21L證明： 。sr3Page 811. 設 f(n)是使得和式 能被正整數 n 整除的最小正整數。證明：)(1nfkf(n)2n1 iff n2 m， m 為非負整數。12. 設 n1，n 為奇數。證明：對於任意的 m N，n 都無法整除 mn-11。