剩余類(lèi)與剩余系

《剩余類(lèi)與剩余系》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、一、同餘，剩餘類(lèi)與剩餘系(a)同餘的性質(zhì)：(1)a≡b(modm)，c≡d(modm)，則ac≡bd(modm)且ac≡bd(modm)。(2)a≡b(modm)，cN，則ac≡bc(modcm)。(3)a≡b(modm)，nN且，則a≡b(modn)。(4)若a≡b(modm)，則(a，m)＝(b，m)。(輾轉(zhuǎn)相除原理)(5)整數(shù)a，b，則ab≡1(modm)iff(a，m)＝1。((1)a0,a1,…,a(m-1))(b)剩餘類(lèi)：m為正整數(shù)，將全體整數(shù)按照對(duì)模m的餘數(shù)進(jìn)行分類(lèi)，餘數(shù)為r()的所有整數(shù)歸為一類(lèi)，記為Kr(r=0,1,..,m-1

2、)，每一類(lèi)Kr均稱(chēng)為模m的剩餘類(lèi)(同餘類(lèi))。剩餘類(lèi)Kr是數(shù)集Kr={mq+r是模，r是餘數(shù)，q?Z}＝{a且}，它是一個(gè)以m為公差的(雙邊無(wú)窮)等差數(shù)集。並具有如下的性質(zhì)：(1)且()。(2)對(duì)於任意的，有唯一的r0使。(3)對(duì)於任意的a、b，a、b(c)完全剩餘系：設(shè)K0，K1，…，Km-1是模m的全部剩餘類(lèi)，從每個(gè)Kr中取任取一個(gè)數(shù)ar，這m個(gè)數(shù)a0，a1，…，am-1組成的一個(gè)數(shù)組稱(chēng)為模m的一個(gè)完全剩餘系。(d)簡(jiǎn)化剩餘系：如果一個(gè)模m的剩餘類(lèi)Kr中任一數(shù)都與m互質(zhì)，就稱(chēng)Kr是一個(gè)與模m互質(zhì)的剩餘類(lèi)。在與模m互質(zhì)的每個(gè)剩餘類(lèi)中，任取一個(gè)數(shù)(

3、共個(gè))所組成的數(shù)組，稱(chēng)為模m的一個(gè)簡(jiǎn)化剩餘系。Page8Page8(二)高觀點(diǎn)：同餘類(lèi)環(huán)(ring)1.等價(jià)關(guān)係：給集合S中一個(gè)關(guān)係”~”。S中元素有此關(guān)係便記為a~b。我們希望把S中所有的元素分成一些更小的子集S1，S2，…使得同一子集中任何兩個(gè)元素都有此關(guān)係，而不同子集中的任何兩個(gè)元素都沒(méi)有此關(guān)係。對(duì)於集合S，”~”是定義在S中的一種關(guān)係，若此關(guān)係滿(mǎn)足：(1)自反性(Reflexive)：，a~a。(2)對(duì)稱(chēng)性(Symmetric)：若a~b，則b~a。(3)傳遞性(Transitive)：若a~b且b~c，則a~c。則此種關(guān)係稱(chēng)為等價(jià)關(guān)係。

4、例如：”＝”是等價(jià)關(guān)係；”＞”不是等價(jià)關(guān)係?！澳同餘”是整數(shù)集合中的一個(gè)等價(jià)關(guān)係。2.同餘類(lèi)：所有模m彼此同餘的整數(shù)組成一類(lèi)，稱(chēng)為整數(shù)的一個(gè)模m同餘類(lèi)。整數(shù)a所在的同餘類(lèi)記為[a]。(1)對(duì)任意整數(shù)a與b，[a]＝[b]iffa≡b(modm)(2)Zm＝{[0]，[1]，…，[m－1]}完全剩餘系：在m個(gè)同餘類(lèi)中每個(gè)同餘類(lèi)取一個(gè)整數(shù)，這m個(gè)整數(shù)稱(chēng)為完全剩餘系，簡(jiǎn)稱(chēng)(模m的)完系。例如：Z3＝{－1，0，1}＝{0，2，4}【引理】(1)若{a1，a2，…，an}是模m完系，bN且(b，m)＝1，則{ba1，ba2，…，ban}也是模m完系。(

5、2)m、nN且(m，n)＝1，若{a1，a2，…，an}和{b1，b2，…，bn}分別為模m和模n的完系，則{nai＋mbj(1im，1jn)}是模mn的完系。3.環(huán)：一個(gè)包含有加、減、乘三種運(yùn)算並且滿(mǎn)足結(jié)合律，分配律，交換律的集合。由同餘式的性質(zhì)我們可以定義：[a]＋[b]＝[a＋b]；[a]－[b]＝[a－b]；。Page8所以Zm中可以自然的進(jìn)行加、減、乘三種運(yùn)算，稱(chēng)為(模m)同餘類(lèi)環(huán)。【性質(zhì)】Zm中，每個(gè)元素的m倍均為零。n[a]＝[a]＋[a]＋…＋[a]＝[na]，則m[a]＝[ma]＝[0]。1.Zm中的除法運(yùn)算：由性質(zhì)(2)：對(duì)於

6、在環(huán)Zm中的元素[a]，存在[b]使得iff(a，m)＝1。我們把[b]記為[a]-1，稱(chēng)為元素[a]的逆元素，[a]稱(chēng)為可逆元素。我們可以用可逆元素去除Zm中的任何元素：若[a]可逆，[a][x]=[b]，則[a]-1[a][x]＝[a]-1[b]，所以[x]＝[a]-1[b]＝2.域：一個(gè)包含有加、減、乘、除四則運(yùn)算的集合。當(dāng)p為質(zhì)數(shù)，Zp＝{[0]，[1]，…，[p－1]}，除了[0]以外，其餘p－1個(gè)元素都是可逆元素(∵1,2,…,(p-1)均與p互質(zhì))，所以Zp中的每個(gè)非零元素都可以作為分母去除其他元素，即Zp中的元素可以作四則運(yùn)算(只

7、是0不能為分母)，我們稱(chēng)為p元有限域?！纠?】Fermat小定理：當(dāng)p為質(zhì)數(shù)時(shí)，若(a,p)=1，ap-1≡1(modp)?！纠?】Euler定理：aZ，mN，設(shè)(a,m)=1，則有。【例3】(1)aZ，(a，m)＝1，則必存在nN，使得(2)設(shè)n是滿(mǎn)足(1)中的最小正整數(shù)，則對(duì)於每個(gè)rN，iff?！纠?】p為質(zhì)數(shù)且p＝4k+1若且唯若存在一個(gè)整數(shù)a，使得a2≡-1(modp)。Page8二、幾個(gè)著名定理定理一：Euler定理aZ，mN，設(shè)(a,m)=1，則有。定理二：Fermat小定理當(dāng)p為質(zhì)數(shù)時(shí)，對(duì)任意a有ap≡a(modp)；特別的，若(a

8、,p)=1，ap-1≡1(modp)。定理三：Wilson定理設(shè)p為質(zhì)數(shù)，則(p-1)!≡-1(modp)。Wilson定理的逆命題若n