剩余类与剩余系.doc

一、同餘，剩餘類與剩餘系(a) 同餘的性質： (1) ab (mod m)，cd (mod m)，則 acbd (mod m) 且acbd (mod m)。 (2) ab (mod m)，cN，則 acbc (mod cm)。 (3) ab (mod m)，nN且 ，則 ab (mod n)。 (4) 若ab (mod m)，則 (a，m)(b，m)。 (輾轉相除原理) (5) 整數a，b，則 ab1 (mod m) iff (a，m)1。 (1)a0,a1,a(m-1) (b) 剩餘類：m為正整數，將全體整數按照對模m的餘數進行分類，餘數為r () 的所有整數歸為一類，記為Kr (r=0,1,.,m-1)，每一類Kr均稱為模m的剩餘類 (同餘類)。剩餘類Kr是數集Kr=mq+r是模，r是餘數，qZa且，它是一個以m為公差的(雙邊無窮)等差數集。 並具有如下的性質：(1) 且 ()。(2) 對於任意的，有唯一的r0使。(3) 對於任意的a、b，a、b (c) 完全剩餘系：設K0，K1，Km-1是模m的全部剩餘類，從每個Kr中取任取一個數ar，這m個數a0，a1，am-1組成的一個數組稱為模m的一個完全剩餘系。(d) 簡化剩餘系：如果一個模m的剩餘類Kr中任一數都與m互質，就稱Kr是一個與模m互質的剩餘類。在與模m互質的每個剩餘類中，任取一個數 (共個) 所組成的數組，稱為模m的一個簡化剩餘系。 (二) 高觀點：同餘類環 (ring)1. 等價關係：給集合S中一個關係 ”。S中元素有此關係便記為 a b。我們希望把S中所有的元素分成一些更小的子集S1，S2，使得同一子集中任何兩個元素都有此關係，而不同子集中的任何兩個元素都沒有此關係。對於集合S，” ” 是定義在S中的一種關係，若此關係滿足：(1) 自反性 (Reflexive)：，a a 。(2) 對稱性 (Symmetric)：若 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的)完系。例如：Z31，0，10，2，4【引理】(1) 若 a1，a2，an 是模m完系，bN且(b，m)1， 則 ba1，ba2，ban 也是模m完系。(2) m、nN且 (m，n)1，若 a1，a2，an和b1，b2，bn分別為 模m和模n的完系，則 naimbj (1im，1jn)是模mn的完系。3. 環：一個包含有加、減、乘三種運算並且滿足結合律，分配律，交換律的集合。由同餘式的性質我們可以定義： abab ； abab ； 。所以Zm中可以自然的進行加、減、乘三種運算，稱為 (模m) 同餘類環。【性質】Zm中，每個元素的m倍均為零。naaaana，則 mama0。4. Zm中的除法運算：由性質(2)：對於在環Zm中的元素 a，存在 b 使得 iff (a，m)1。我們把 b 記為 a-1，稱為元素a的逆元素，a稱為可逆元素。我們可以用可逆元素去除Zm中的任何元素：若a可逆，ax=b，則a-1axa-1b，所以 xa-1b5. 域：一個包含有加、減、乘、除四則運算的集合。當p為質數，Zp0，1，p1，除了0以外，其餘p1個元素都是可逆元素 ( 1,2,(p-1)均與p互質)，所以Zp中的每個非零元素都可以作為分母去除其他元素，即Zp中的元素可以作四則運算(只是0不能為分母)，我們稱為p元有限域。【例1】 Fermat小定理：當p為質數時，若(a,p)=1，ap-11 (mod p)。【例2】 Euler定理：aZ，mN，設 (a,m)=1，則有 。【例3】 (1) aZ，(a，m)1，則必存在nN，使得 (2) 設n是滿足(1)中的最小正整數，則對於每個rN， iff 。【例4】 p為質數且p4k+1 若且唯若 存在一個整數a，使得 a2-1 (mod p)。二、幾個著名定理定理一： Euler定理 aZ，mN，設 (a,m)=1，則有 。定理二： Fermat小定理當p為質數時，對任意a有apa (mod p)；特別的，若(a,p)=1，ap-11 (mod p)。定理三： Wilson定理設p為質數，則 (p-1)!-1 (mod p) 。Wilson定理的逆命題若n 為大於5的合成數，則 (n-1)!0 (mod n)定理四： 中國剩餘定理設m,n是互質的正整數；a,b為整數，則同餘式 有共同解x0；且所有的共同整數解x也是一個同餘式：xx0 (mod nm) 。設m1,m2，mk是兩兩互質的正整數，則對於任意整數c1,c2，ck，存在整數x使得 ， 同時成立。並且在模m1m2mk的意義下，上述的同餘方程組的解是唯一的，可表示為 xx0 (mod m1m2mk) 。其中x0可以這樣確定：令，是Mi關於模mi的數論倒數，則。定理五： Lagrange定理設p是質數，多項式 f(x)anxnan-1xn-1a1xa0 是一個模p為n次的整係數多項式 (即p不整除an)，則同餘方程 f(x)0 (mod p) 至多有n個解(在模p的意義下)。設p是質數，設 f(x)(x1)(x2)(xp1) xp-1A1 xp-2Ap-2 xAp-1則A1、A2、.、Ap-1 皆可為p整除。例題1： 設p為奇質數，a、n為正整數，且，證明：。又問：當p=2時，命題是否依然成立？證明： 由 ， (a，p)1，由Fermat小定理：ap-11 (mod p)，所以 ap-11ap (mod p)，所以 a1 (mod p)另一方面，設 Aap-1ap-21，則 ap1(a1) A，且A1p-11p-21p0 (mod p)，即 。更進一步，設 akp1，由二項式定理知： Akp(p1)(p2)1pp (mod p2)。最後一步， p為奇質數， 且 p2不整除A ()。綜上所述，結合 ，可知 。當p2時，命題不成立，例如：，但是22不整除312。 【注】此題綜合運用了二項式定理、代數式變形和費馬小定理，其中利用費馬小定理確定a與p的關係是關鍵的第一步。例題2： 對正整數n，如果對任意的正整數a，只要 ，就有，則稱n具有性質P。證明： (1) 每個質數都具有性質P； (2) 存在無窮多個合數具有性質P。證明： (1) 設p為質數，若 ，可知 (a，p)1， 於是由Fermat小定理可知ap-11 (mod p) a1 (mod p) 且 Aap-1ap-210 (mod p)， 因此 ，所以質數p都具有性質P。(2) 設p是奇質數，我們證明：2p具有性質P。 若 ，可知a為奇數，所以a2p(ap)21 (mod 8)，則 。 又 ，所以 或 ， 若 ，由(1)得知 ； 若 ，則 (a，p)1，由Fermat小定理可知ap-11 (mod p)， 進而 1apa (mod p)，即 由於p為奇數，則 Bap-1ap-21(1)p-1(1)p-21p0 (mod p) 所以 ，即總是有 結合 (4，p2)1，可知 。因此2p具有性質P。 由質數有無限多個，可知(2)成立。 例題3： 證明：不存在非負整數k與m，使得： k!4848(k1)m 。 證明： 若k0或m0時，上述不定方程式無解，所以，可設k，m為正整數。(1) 若k1為合數，設k1pq，2pq， ， k6，於是 12qk，所以 則 k8、12、24、48，分別代入原式，可得矛盾。(2) 若k1為質數，由Wilson定理，可知 k!-1 (mod k+1)， 於是 ，即 k147，則 46!484847m， m1， 可得 ，取模4得：(1)m1 (mod 4)，設 m2k， 得到 。 由於 ，而47k12 (mod 23)， 。 由二項式定理 47k(2231)k46k1 (mod 232)，所以 ， 則 m46，矛盾!(右式大於左式)。 例題4： 設a，bN，p為奇質數，且pab1。求最大的整數c，使得對於所有滿足上述條件的a、b、p，都有，此處的 。 證明： 取p5，a3，b2，由條件 ，所以 c3。接著證明：對於所有滿足上述條件的a、b、p，都有。 A其中A所以，我們只需證明：， 設 f(x)(x1)(x2)(xp1)xp-1 xp-2x(p1)!，則當x1,2,p-1時，均有f(x)0 (mod p)。由Fermat小定理知，當1xp1，xp-11 (mod p)，由Wilson定理知，(p-1)!-1 (mod p)，所以，p2次的同餘方程式f(x)(xp-1(p1)!)0 (mod p) 有p1個不同解(模p意義下)，由Lagrange定理，可知、.、 皆為p的倍數。進一步，在f(x)中，令xp，且p為奇質數，可知 ，則 A (p1)!b-1(p1)!b(p1)!b-1(p1)!b0 (mod p3)。所以，所求的最大整數為c3。 【注】此題將A中各乘積式展開後，容易證明 ，為了證明 ，先用Lagrange定理推出、.、 皆為p的倍數，進而 是解決該題的關鍵。【練習】第一部分：(大黃)1. 設p為奇質數，求證：2p-1有2kp+1形式的質因數。2. 設p為奇質數，證明：1232(p-2)2 (mod p)3. 設p為質數，apbp (mod p)。求證：apbp (mod p2)。4. 設p為奇質數，x,y為互質的整數且p|x2+y2。證明：(1)存在整數n使得 p|1+n2。(2)p1 (mod 4)。Hint：(x2+y2)(a2+b2)=(ax+by)2+(ay-bx)25. 設p為奇質數。求證：在1,2,3, p-1中恰有個關於模p與一個平方數。第二部分：1. 設n是大於1的正整數，證明：n為質數 iff 則 (n-1)!-1 (mod n) 。2. 設p為質數，證明：數列 2n-n 中有無窮多項為p的倍數。 (F) 3. 設正整數a，d互質，證明：在等差數列akd，中有無窮多項具有相同的質因子。 (E) 4. 設p，q為奇質數，2pq1，xN，且(x，2pq)1，證明：。(F)5. 設m，nN，且 (m，n)1，證明： (E) 6. 求所有的質數p，q，使得是一個整數。7. 設p為質數，a，nN，證明：若2p3pan，則n