《剩余类及其运算》课件1

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

1、2.3剩余类及其运算人教B版数学选修4-6《初等数论初步》定义1给定正整数m，对于任意整数a，称集合Ca={c

2、ac(modm)，cZ}是模m的一个剩余类。一个剩余类中的任一数叫做该类的剩余或者代表元。若r0，r1,…,rm-1是m个整数,并且其中任何两个数都不在同一剩余类里,则r0，r1,…,rm-1称为模m的一个完全剩余系从定义可以看出,模m的剩余类有m个C0,C1,…,Cm-1,定理1设m是一个正整数,则①任一整数必包含在一个Cr中,0≤r≤m-1②Ca=Cbiffab(modm).③Ca与Cb

3、的交集为空集的充要条件是a!b(modm).①任一整数必包含在一个Cr中,0≤r≤m-1证明:设a是任一整数,由欧几里得除法有唯一q,r使得a=qm+r,其中0≤r≤m-1,故ra(modm)②Ca=Cbiffab(modm).证明:“”由Ca=Cbabc(modm)“←”对任意的c∈Ca,满足ac(modm),又ab(modm),由同余的传递性知道,bc(modm),故CaCb,同理CbCa证毕③Ca与Cb的交集为空集的充要条件是a!b(modm).证明:由②必要性成立充分性:反证法

4、,假设Ca与Cb的交集非空,则,存在c∈Ca∩Cb也就是说ac(modm),bc(modm)成立,从而,ab(modm).矛盾定理2m个整数构成模m的一完全剩余系iff这m个整数两两对模m不同余证明,由定理1和定义易证例1设m是一个正整数,则①0,1,…,m-1是模m的一个完全剩余系叫做模m的最小非负完全剩余系②1,…,m-1,m是模m的一个完全剩余系叫做模m的最小正完全剩余系③-m+1,…,-1,0是模m的一个完全剩余系叫做模m的最大非正完全剩余系④-m,-m+1,…,1是模m的一个完全剩余系叫做模

5、m的最大负完全剩余系⑤当m分别为偶数时,-m/2,-(m-2)/2,…,-1,0,1,…,(m-2)/2或-(m-2)/2,…,-1,0,1,…,(m-2)/2,m/2是模m的一个完全剩余当m是奇数时,-(m-1)/2,…,-1,0,1,…,(m-1)/2是模m的一个完全剩余系上述两个完全剩余系统称为模m的一个绝对值最小完全剩余系定理3若a0,a1,…,am-1是模m的一个完全剩余系,a和c是任意两个整数，且(a,m)=1,则aa0+c,aa1+c,…,aam-1+c也是模m的一个完全剩余系.证明:由定理2

6、,只需证明当a0,a1,…,am-1是模m的一个完全剩余系时,aa0+c,aa1+c,…,aam-1+c两两模m不同余就可以了采用反证法,假设,存在ai和ak(i≠k),使得aai+c≡aak+c(modm)m

7、a(ai-ak),又(a,m)=1从而m

8、ai-ak,即ai和ak同余,矛盾定理4设m1和m2是大于零的整数,(m1,m2)=1,x1和x2分别遍历模m1和m2的完全剩余系,则m2x1+m1x2是遍历模m1m2的完全剩余系。证明:显然,当x1和x2分别遍历m1和m2个数时,m2x1+m1x2遍历m

9、1m2个数,由定理2,只需证明这m1m2个数两两不同余反证法m2ai1+m1bj1m2ai2+m1bj2(modm1m2),0≤i1,i2≤m1-1,0≤j1,j2≤m2-1.于是,得到m2ai1m2ai2(modm1),m1bj1m1bj2(modm2),因为(m1,m2)=1,故ai1ai2(modm1),bj1bj2(modm2).ai1和ai2是模ml同余，与假设矛盾例2设m=6,a=7,b=5,找m的一个形如ax+b的完全剩余系解,取x=0,1,2,3,4,5则5,12,19,26,33

10、,40即为所求例3设m1=5,m2=4,找m1m2的一个形如m1x2+m2x1的完全剩余系解取x1=0,1,2,3,4,x2=0,1,2,3则0,5,10,15,20，4,9,14,19,24,8,13,18,23,28,12,17,22,27,32例4设p,q是两个不同的素数,n是它们的乘积,则对任意整数c,存在唯一的一对整数x,y满足qx+py≡c(modn)由定理4易证TheEnd