剩余类与剩余系

1、飞同餘，剩餘類與剩餘系(a) 同餘的性質：(1) a= b (mod m), 尸 d (mod m),貝 U a - c= b_d (mod m) 且 ac= bd (mod m)。(2) a= b (mod m), c N,貝U ac= bc (mod cm)。(3) a= b (mod m), n迂 N 且 nm ,貝U a= b (mod n)。(4) 若 a= b (mod m),貝U (a, m)= (b, m)。(5) 整數 a, b,貝U ab= 1 (mod m) iff (a, m) = 1。(b) 剩餘類：m為正整數，將全體整數按照對模 m的餘數進行分類，餘數為r (0 r

2、 一 m -1)的所 有整數歸為一類，記為 Kr (r=0,1,.,m-1)，每一類Kr均稱為模m的剩餘類(同餘類)。剩餘類Kr是數集Kr=mq+r|m是模，r是餘數，q Z = a|aZ且a三r(modm),它是一個以m為公差的(雙邊無窮)等差數集。並具有如下的性質：(1) Z 二 K0 _ K, _ K2 一. - KmJ且心 - Kj = 一 (i = j )。對於任意的Z，有唯一的r0使y Kr0。(3)對於任意的 a、b Z , a、b Kr = a=b(modm)(c) 完全剩餘系：設K。，K1,，Km-1是模m的全部剩餘類，從每個Kr中取任取一個數ar,這m個數 a0, a1,，

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

4、 對稱性(Symmetric):若ab,則ba。(3) 傳遞性(Transitive):若ab且bc,則ac。則此種關係稱為等價關係。例如：”二”是等價關係；”不是等價關係。模m同餘”是整數集合中的一個等價關係。2. 同餘類：所有模m彼此同餘的整數組成一類，稱為整數的一個模m同餘類。整數a所在的同餘類記為a。(1)對任意整數a與b,a = b iff a= b (mod m) Zm = 0 , 1,，口 1完全剩餘系：在m個同餘類中每個同餘類取一個整數，這m個整數稱為完全剩餘系，簡稱(模m的)完系。例如：Z3= - 1, 0, 1 =0 , 2, 4【引理】(1)若a1, a2,，an是模m完

5、系，b N且(b, m)= 1, 則U ba1, ba2,，ban也是模m完系。(2) m、n N 且(m, n)= 1, 若 a1, a2,，an和b1, b2,，bn分別為 模m和模n的完系，則U nai + mbj (1_im, 1_j_n)是模mn的完系。3. 環：一個包含有加、減、乘三種運算並且滿足結合律，分配律，交換律的集合。由同餘式的性質我們可以定義：a + b = a+ b ;a-b = a b ;a b=a b。【性質】Zm中，每個元素的m倍均為零。na = a + + + a = na,貝U ma = ma| = 0。4. Zm中的除法運算：由性質(2)：對於在環Zm中的元

6、素a,存在b使得a b二1 iff (a, m)= 1。 我們把b記為a-1，稱為元素a的逆元素，a稱為可逆元素。我們可以用可逆元素去除Zm中的任何元素：若a可逆，ax=b,則a-1ax二a-1b，所以x = a-1b二卑a5. 域：一個包含有加、減、乘、除四則運算的集合。當p為質數，Zp二0，1，P1，除了 0以外，其餘P1個元素都是可逆 元素( 1,2,(p-1)均與p互質)，所以Zp中的每個非零元素都可以作為分母去除 其他元素，即Zp中的元素可以作四則運算(只是0不能為分母)，我們稱為p元有限 域。【例1】Fermat小定理：當p為質數時，若(a,p)=1，ap_1 = 1 (mod p

7、)。【例2 Euler 定理：a Z，m N，設(a,m)=1，則有 a (m)三 1(modm)。【例3 (1) a Z，(a，m)= 1，則必存在 n N，使得 an 三 1(modm) 設n是滿足(1)中的最小正整數，則對於每個r N， a，三1(modm) iff nr。【例4 p為質數且p=4k+1若且唯若 存在一個整數a，使得a2三-1 (mod p)。1、幾個著名定理定理一： Euler定理a Z, m N，設(a,m)=1，則有 a (m)三 1(modm)。定理二： Fermat小定理當p為質數時，對任意a有ap=a (mod p);特別的，若(a,p)=1, apJ = 1

8、 (mod p)定理三：Wilson定理設 p 為質數，則(p-1)U-1 (mod p)。Wilson定理的逆命題若n為大於5的合成數，則(n-1)! = 0 (mod n)定理四：中國剩餘定理、"x 三 a ( m ond)設m,n是互質的正整數；a,b為整數，則同餘式有共同解xo；X 三 b ( m ord)且所有的共同整數解x也是一個同餘式：x=xo (mod nm)。設mi,m2,，mk是兩兩互質的正整數，則對於任意整數 ci,C2,，ck,存在整數 x使得x 三 G ( m oral)，1 兰 i 兰 k同時成立。並且在模 mm2mk的意義下，上述的同餘方程組的解是唯一的

9、，可表 示為 x三xo (mod mm2 mk)。其中xo可以這樣確定：令Mi二一匹，M是Mi關於模mi的數論倒數，則mikx° = ' M i M i Ci。i:i定理五： Lagrange定理設p是質數，多項式nn-1,f(x) = anx + an-1X + + a1x+ a0是一個模p為n次的整係數多項式(即p不整除an)，則同餘方程f(x)三0 (mod p)至多有n個解(在模p的意義下)。設p是質數，設f(x)= (x+ 1)(x+ 2)(x+ p 1) = x3-1 + A1 xp-2+ Ap-2 x+ Ap-1則A1、A2、Ap-1皆可為p整除例題1:設p為奇

10、質數，a、n為正整數，且pn|ap_1，證明：pn"*|a-1又問：當p=2時，命題是否依然成立？證明：【注】此題綜合運用了二項式定理、代數式變形和費馬小定理，其中利用費馬小定理確定a與p的關係是關鍵的第一步。例題2：對正整數n,如果對任意的正整數a,只要n|an-1，就有n 2|an-1，則稱n具有性質P。證明：(1) 每個質數都具有性質P；(2) 存在無窮多個合數具有性質P。證明：例題3:證明：不存在非負整數k與m,使得：k! + 48= 48(k+ 1)m證明：例題4：設a, b N, p為奇質數，且p>a>b> 1。求最大的整數c,使得對於所有滿足上述 條件

11、的a、b、p,都有pc歸-C：，此處的以= n(n1厂(n一k+°。k!證明：【注】此題將A中各乘積式展開後,容易證明p2 A,為了證明p'| A,先用Lagrange定理推出、G 2、G p/皆為p的倍數，進而 P2|di是解決該題的關鍵。【練習】第一部分：(大黃)1. 設p為奇質數，求證：2p-1有2kp+1形式的質因數。p出2. 設p為奇質數，證明：12 32(p-2)2三(-1)2 (mod p)3. 設 p 為質數，a b* (mod p)。 求證：ap 三bp (mod p2)。4. 設p為奇質數，x,y為互質的整數且p|x2+y2。證明：(1)存在整數 n 使得

12、 p|1 +n2。(2)p=1 (mod 4)。2 2 2 2 2 2Hint: (x +y )(a +b )=(ax+by) +(ay_bx)5. 設p為奇質數。求證：在1,2,3p-1中恰有 心 個關於模p與一個平方數。2第二部分：1. 設n是大於1的正整數，證明：n為質數iff貝U (nT)UT (mod n)。2. 設p為質數，證明：數列2 n nN中有無窮多項為p的倍數。3. 設正整數a, d互質，證明：在等差數列a+ kd k=0,1,2,.，中有無窮多項具有相同的 質因子。4. 設 p, q 為奇質數，2p = q+ 1, x N,且(x, 2pq)= 1,證明：x2(pJI)三

13、 1(mod16pq)。5. 設 m, n N,且(m, n) = 1,證明：m (m) n 三 1 (modmn)6. 求所有的質數p, q,使得 一2卩)(5 一2)是一個整數。pq7. 設p為質數，a, n N，證明：若2p + 3p= an,則n= 1。8. 求一個自然數n,使得n, n+ 1,，n + 20中的每一個數都與3030有大於1的公因數。9. 設m, n N, p為質數，且對於任意的k N,均有(pk 1, m) = (pk- 1, n)。證明：存 在某個tZ,使得m= pt n。10. 設p>3, p為質數，且設1 1r1, (r, s)二 1, r, s N,2 pps證明：p3 r -s。f (n)11. 設f(n)是使得和式v k能被正整數n整除的最小正整數。證明：k吕f(n) = 2n 1 iff n = 2m, m為非負整數。12. 設n> 1, n為奇數。證明：對於任意的 m N, n都無法整除mn-1 + 1。仅供个人用于学习、研究；不得用于商业用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zw