剩余類與剩余系

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

1、一、同餘，剩餘類與剩餘系(a)同餘的性質：(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)。(輾轉相除原理)(5)整數(shù)a，b，則ab≡1(modm)iff(a，m)＝1。((1)a0,a1,…,a(m-1))(b)剩餘類：m為正整數(shù)，將全體整數(shù)按照對模m的餘數(shù)進行分類，餘數(shù)為r()的所有整數(shù)歸為一類，記為Kr(r=0,1,..,m-1

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

3、共個)所組成的數(shù)組，稱為模m的一個簡化剩餘系。Page8Page8(二)高觀點：同餘類環(huán)(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。則此種關係稱為等價關係。

4、例如：”＝”是等價關係；”＞”不是等價關係?！澳同餘”是整數(shù)集合中的一個等價關係。2.同餘類：所有模m彼此同餘的整數(shù)組成一類，稱為整數(shù)的一個模m同餘類。整數(shù)a所在的同餘類記為[a]。(1)對任意整數(shù)a與b，[a]＝[b]iffa≡b(modm)(2)Zm＝{[0]，[1]，…，[m－1]}完全剩餘系：在m個同餘類中每個同餘類取一個整數(shù)，這m個整數(shù)稱為完全剩餘系，簡稱(模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)：一個包含有加、減、乘三種運算並且滿足結合律，分配律，交換律的集合。由同餘式的性質我們可以定義：[a]＋[b]＝[a＋b]；[a]－[b]＝[a－b]；。Page8所以Zm中可以自然的進行加、減、乘三種運算，稱為(模m)同餘類環(huán)?！拘再|】Zm中，每個元素的m倍均為零。n[a]＝[a]＋[a]＋…＋[a]＝[na]，則m[a]＝[ma]＝[0]。1.Zm中的除法運算：由性質(2)：對於

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

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

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