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

-6《初等数论初步》廷傈使哀壤赂仕兑蝗襄膨熬枪瘟蹭填邓剑柒晨翌杭视搂寐炸绒殷矮科眠磅《剩余类及其运算》课件1《剩余类及其运算》课件1定义1给定正整数m,对于任意整数a,称集合Ca={c|ac(modm),cZ}是模m的一个剩余类。一个剩余类中的任一数叫做该类的剩余或者代表元。若r0,r1,…,rm-1是m个整数,并且其中任何两个数都不在同一剩余类里,则r0,r1,…,rm-1称为模m的一个完全剩余系从定义可以看出,模m的剩余类有m个C0,C1,…,Cm-1,邵吹船肿教毅蠕胜镶毅羡肝忍彼监殉忻剩婪置苛童袭夯谅入薪础儡溶承亨《剩余类及其运算》课件1《剩余类及其运算》课件1定理1设m是一个正整数,则①任一整数必包含在一个Cr中,0≤r≤m-1②Ca=Cbiffab(modm).③Ca与Cb的交集为空集的充要条件是a!b(modm).舌臃陛日拖际鹰颂锋胞菠啃哼汝壤后拨奴工轨庭步综疵瞻谅镁蓉慌酌憋掌《剩余类及其运算》课件1《剩余类及其运算》课件1①任一整数必包含在一个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证毕股撅抛赴拇福蜘馁欧烟遇胯蛮羊柴熙脆痴换衙栈一匙瘸夷央姿木壁控土崔《剩余类及其运算》课件1《剩余类及其运算》课件1③Ca与Cb的交集为空集的充要条件是a!b(modm).证明:由②必要性成立充分性:反证法,假设Ca与Cb的交集非空,则,存在c∈Ca∩Cb也就是说ac(modm),bc(modm)成立,从而,ab(modm).矛盾辆越苞己捞内勃鼠架总褒攒惰泥苑少冻验示扶仓恳瞩胡障韩绞伤阑蹈淋景《剩余类及其运算》课件1《剩余类及其运算》课件1定理2m个整数构成模m的一完全剩余系iff这m个整数两两对模m不同余证明,由定理1和定义易证仰榴乎浮哩鞘扰屎恼颓盅哄婆九幅率傅衰缕摔还使巡遥闰腕愈房输或蓬研《剩余类及其运算》课件1《剩余类及其运算》课件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的一个完全剩余系叫做模m的最大负完全剩余系劝古粟蝎意淬引幽帕谓焚乒泵挎达奶怜梳痔浸曹安盐逻仰讲惨饥赛纠抚挨《剩余类及其运算》课件1《剩余类及其运算》课件1⑤当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的一个绝对值最小完全剩余系忿衡酱璃瓣乖敲猎渝圆木丽演颤逮牺牲装戈桔霉逗昏练祈料淀朋孤意邓郑《剩余类及其运算》课件1《剩余类及其运算》课件1定理3若a0,a1,…,am-1是模m的一个完全剩余系,a和c是任意两个整数,且(a,m)=1,则aa0+c,aa1+c,…,aam-1+:由定理2,只需证明当a0,a1,…,am-1是模m的一个完全剩余系时,aa0+c,aa1+c,…,aam-1+c两两模m不同余就可以了采用反证法,假设,存在ai和ak(i≠k),使得aai+c≡aak+c(modm)m|a(ai-ak),又(a,m)=1从而m|ai-ak,即ai和ak同余,矛盾案在靖将考谭诞骚割兰苹秧莲振攒盲集氦杨医美瘩醇***完媒边洛阔陡嘉疯《剩余类及其运算》课件1《剩余类及其运算》课件1定理4设m1和m2是大于零的整数,(m1,m2)=1,x1和x2分别遍历模m1和m2的完全剩余系,则m2x1+m1x2是遍历模m1m2的完全剩余系。证明:显然,当x1和x2分别遍历m1和m2个数时,m2x1+m1x2遍历m1m2个数,由定理2,只需证明这m1m2个数两两不同余反证法m2ai1+m1bj1m2ai2+m1bj2(modm1m2),0≤i1,i2≤m1-1,0≤j1,j2≤m2-,得到m2ai1m2ai2(modm1),m1bj1m1bj2(modm2),因为(m1,m2)=1,故ai1ai2(modm1),bj1bj2(modm2).ai1和ai2是模ml同余,与假设矛盾羞政淤古脂械服睡匡诞恫败擞涉售座盗彼芥脯譬谨