《剩余类及其运算》课件

《《剩余类及其运算》课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1剩余类及其运算剩余类与完全剩余系引言一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。一、剩余类——按余数的不同对整数分类是模m的一个剩余类，即余数相同的整数构成m的一个剩余类。注：一个剩余类中任意一个数称为它同类的数的剩余。1.剩余类K0(5)={n︱n0(mod5)，nZ}K1(5)={n︱n1(mod5)，nZ}K2(5)={n︱n2(mod5)，nZ}K3(5)={n︱n

2、3(mod5)，nZ}K4(5)={n︱n4(mod5)，nZ}模5的五个剩余类是2.定理1二、完全剩余系1.定义2②完全剩余系不唯一；③若把剩余系作为一个集合，则同一剩余类里的整数，看作同一元素。注：①模m的一个完全剩余系有且仅有m个整数；2.定义3：集合{0,6,7,13,24}是模5的一个完全剩余系，如，集合{0,1,2,3,4}是模5的最小非负完全剩余系。叫做模m的绝对最小完全剩余系。叫做模m的绝对最小完全剩余系。①0,1,2,,m1这m个整数叫做模m的最小非负完全剩余系；②例1写出模7（或8）的最小非负完全剩余系和绝对最小完全剩余系模7的绝

3、对最小完全剩余系为-3,-2,-1,0,1,2,3解：模7的最小非负完全剩余系为0,1,2,3,4,5,63、完全剩余系的构造推论m个整数作成模m的完全剩余系的充要条件是两两对模m不同余。注：由定理1及定义2易得证。思考：1、既然完全剩余系是不唯一的，不同的剩余系之间存在什么关系呢？2、一个完全剩余系的所有元素通过线性变换后，还是完全剩余系吗？检验：设{x1,x2,,xm}是模m的一个完全剩余系，那么，{b+x1,b+x2,,b+xm}和{ax1,ax2,,axm}是模m的一个完全剩余系吗？定理2设m1，a，b是整数，(a,m)=1，{x1,x2,,xm}是

4、模m的一个完全剩余系，则{ax1b,ax2b,,axmb}也是模m的完全剩余系。证明由定理1，只需证明：若xixj，则axibaxjb(modm)。假设axibaxjb(modm)，则axiaxj(modm)，且(a,m)=1，xixj(modm)由§3.1中的结论,P50第三行知：注意：(2)在定理2中，条件(a,m)=1不可缺少，否则不能成立；(3)定理2也可以叙述为：设m1，a，b是整数，(a,m)=1，若x通过模m的一个完全剩余系，则ax+b也通过模m的一个完全剩余系；（4）特别地，若x通过模m的一个完全剩余系，(a,m)=1,

5、则ax和x+b也分别通过模m的一个完全剩余系。(1)任意m个连续整数都能构成模m的一个完全剩余系；例1设p5是素数，a{2,3,,p1}，则在数列a，2a，3a，，(p1)a，pa中有且仅有一个数b，满足b1(modp).证：因为｛1，2，3，，(p1)，p｝是模p的一个完全剩余系，所以｛a，2a，3a，，(p1)a，pa｝构成模p的一个完全剩余系。因此必有唯一的数b满足式b1(modp)。例2设A={x1,x2,,xm}是模m的一个完全剩余系，以{x}表示x的小数部分，证明：若(a,m)=1，则证：当x通过模m的完全剩余系时，axb也通过模

6、m的完全剩余系，因此对于任意的i（1im），axib一定与且只与某个整数j（1jm）同余，即存在整数k，使得axib=kmj，（1jm）定理3若m1,m2N，(m1,m2)=1，当x1与x2分别通过模m1与模m2的完全剩余系时，则m2x1m1x2通过模m1m2的完全剩余系。4、剩余系间的联系例3设m>0是偶数，{a1,a2,,am}与{b1,b2,,bm}都是模m的完全剩余系，则{a1b1,a2b2,,ambm}不是模m的完全剩余系。证由{1,2,,m}与{a1,a2,,am}都是模m的完全剩余系，如果{a1b1,a2b2,,a

7、mbm}是模m的完全剩余系，不可能！例4设miN（1in），则当xi通过模mi（1in）的完全剩余系时，x=x1m1x2m1m2x3m1m2mn1xn通过模m1m2mn的完全剩余系。证明对n施行归纳法。当n=2时，结论成立。假设定理结论当n=k时成立，即当xi（2ik1）分别通过模mi的完全剩余系时，y=x2m2x3m2m3x4m2mkxk1通过模m2m3mk1的完全剩余系。y=x2m2x3m2m3x4m2mkxk1通过模m2m3mk1的完全剩余系。由定理3，当x1通过模m1的完全剩余系，xi（2ik1）通

8、过模mi的完全剩余系时，x1m1y=