剩余类与剩系.doc

《剩余类与剩系.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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)整數a，b，則ab≡1(modm)iff(a，m)＝1。((1)a0,a1,…,a(m-1))(b)剩餘類：m為正整數，將全體整數按照對模m的餘數進行分類，餘數為r()的所有整數歸為一類，記為Kr(r=0,1,..,m-1)，每一類Kr均

2、稱為模m的剩餘類(同餘類)。剩餘類Kr是數集Kr={mq+r是模，r是餘數，qÎZ}＝{a且}，它是一個以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的一

3、個簡化剩餘系。(二)高觀點：同餘類環(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同餘”是整數集合中

4、的一個等價關係。2.同餘類：所有模m彼此同餘的整數組成一類，稱為整數的一個模m同餘類。整數a所在的同餘類記為[a]。(1)對任意整數a與b，[a]＝[b]iffa≡b(modm)(2)Zm＝{[0]，[1]，…，[m－1]}完全剩餘系：在m個同餘類中每個同餘類取一個整數，這m個整數稱為完全剩餘系，簡稱(模m的)完系。例如：Z3＝{－1，0，1}＝{0，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}分

5、別為模m和模n的完系，則{nai＋mbj(1im，1jn)}是模mn的完系。3.環：一個包含有加、減、乘三種運算並且滿足結合律，分配律，交換律的集合。由同餘式的性質我們可以定義：[a]＋[b]＝[a＋b]；[a]－[b]＝[a－b]；。所以Zm中可以自然的進行加、減、乘三種運算，稱為(模m)同餘類環。【性質】Zm中，每個元素的m倍均為零。n[a]＝[a]＋[a]＋…＋[a]＝[na]，則m[a]＝[ma]＝[0]。1.Zm中的除法運算：由性質(2)：對於在環Zm中的元素[a]，存在[b]使得iff(a，m)＝1。我們把[b]記為[a]-1，稱為元素[a]的逆元素

6、，[a]稱為可逆元素。我們可以用可逆元素去除Zm中的任何元素：若[a]可逆，[a][x]=[b]，則[a]-1[a][x]＝[a]-1[b]，所以[x]＝[a]-1[b]＝2.域：一個包含有加、減、乘、除四則運算的集合。當p為質數，Zp＝{[0]，[1]，…，[p－1]}，除了[0]以外，其餘p－1個元素都是可逆元素(∵1,2,…,(p-1)均與p互質)，所以Zp中的每個非零元素都可以作為分母去除其他元素，即Zp中的元素可以作四則運算(只是0不能為分母)，我們稱為p元有限域。【例1】Fermat小定理：當p為質數時，若(a,p)=1，ap-1≡1(modp)。【

7、例2】Euler定理：aZ，mN，設(a,m)=1，則有。【例3】(1)aZ，(a，m)＝1，則必存在nN，使得(2)設n是滿足(1)中的最小正整數，則對於每個rN，iff。【例4】p為質數且p＝4k+1若且唯若存在一個整數a，使得a2≡-1(modp)。二、幾個著名定理定理一：Euler定理aZ，mN，設(a,m)=1，則有。定理二：Fermat小定理當p為質數時，對任意a有ap≡a(modp)；特別的，若(a,p)=1，ap-1≡1(modp)。定理三：Wilson定理設p為質數，則(p-1)!≡-1(modp)。Wilson定理的逆命題若n為大於5的合成數

8、，則(n-1)!≡0(m