第一节-同余

2020/9/121第二章同余同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本章介绍同余的基本概念，剩余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？2020/9/122§2.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？1010再过天呢？7747、你知道的个位数是多少吗？3、13511，13903，14589被自然数m除所得余数相同，问m最大值是多少？2、3145×92653=291093995的横线处漏写了一个数字，你能以最快的办法补出吗？2020/9/12310.,(mod);(1).(mod);mmababkmmabmabmabmabmm定义同余:设若,即则称为模,,对模同余.记作:否则,则称，对模不同余记作:关系式(1)称为模的同余式,或简称同余式.二、同余的定义2020/9/124,(mod));1.,,-/2/2(/2/2),mabmababmmbmbambmbammbmmbmbam由于等价于-所以同余式(1)等价于(-因此,以后总假设在同余式(1)中,若0则称是对模的最小非负剩余;若1称是对模的最小正剩余;若或称是对模的绝对最小剩余.2020/9/125111222121,0;,0;.abmabmaqmrrmbqmrrmrr定理2.同余于模的充要条件是和被除后所得的最小非负余数相等,即若则1212121212()().,.abqqmrrmabmrrrrmrr证我们有因此,的充要条件是由此及0即得:定理1表明可以用最小非负余数相等来定义同余.2020/9/126I(mod),(mod)(mod),(mod),(mod)(mod).0,,,()()aamabmbamabmbcmacmmaamabmbamabmbcmabbcac性质同余是一种等价关系,即有自反性对称性传递性证由以及三、同余的性质2020/9/127II(mod),(mod),(mod).,()()()().abmcdmacbdmmabmcdmabcdacbd性质同余可以相加减,即有则证由122112III(mod),(mod),(mod).,()abmcdmacbdmabkmcdkmacbdbkdkkkmm性质同余可以相乘,即有则证由推出2020/9/12800IV()...,()...(mod),0.(4)(mod),()()(mod).nnnnjjfxaxagxbxbabmjnabmfagbm性质设是两个整系数多项式,满足那么,若则()()(mod)(5)xfxgxm特别的,对所有整数有2020/9/129002()...,()...()(),()()(mod);(6)()(),nnnnfxaxagxbxbfxgxmfxgxmfxgxmm定义设是两个整系数多项式.当满足条件(4)时,称多项式同余于多项式模记作当满足式(5)时,称多项式等价于多项式模式(5)称为模的恒等同余式.2020/9/12101,.(mod).,ddmabddmmabdab性质V设那么,若同余式(1)成立,则证由即得.I0.(mod).ddadbdmdmdadbmab性质V设那么同余式(1)等价于证由推出.2020/9/1211(mod)(7)(mod/(,)).(,)1(mod),.cacbmabmcmcmabmc性质VII同余式等价于特别地,当时,同余式(7)等价于即同余式两边可约去(),().(,)(,)/(,),/(,)().(,)mcabmcabcmcmmcmccmmabcm证同余式(7)即这等价于由第一章§4定理6及()=1知,这等价于2020/9/1212110000011,(,)1,1(mod),(mod).2,,1.(mod)mamccamcamabmakxyaxmycxam性质若则存在使得我们把称为是对模的逆，记作或证由第一章4定理8()知,存在使得取既满足要求.由此提供一种求有效的方法,这是Euclid算法的又一重要应用.Ⅷ§2020/9/1213111(10)1(mod11)(5)6(mod11);1234567891016439287510aa解由1(-10)+11=1得1由2(-5)+11=1得2同样计算得：例求p=11所有元的逆元.2020/9/121411(mod),1,2,...,,(mod,...,]).(1,,),...,].jkjkabmjkabmmmabjkmmab性质IX同余式组同时成立的充要条件是[证由第一章4定理1知,同时成立的充要条件是[§2020/9/1215406406244044064042(mod10),09.91(mod10),1(mod10).1(mod10).9(mod10).aaa例1求3写成十进位数时的个位数.解要求满足3显然有,33进而有3因此，333所以个位数是9.2020/9/1216406406244812(mod100),099.1(mod4),1(mod5).41(mod25),.816(mod25),3611(mod25),669(moddbbbdd例2求3写成十进位数时的最后两位数.解只要求出满足3注意到100=425,(4,25)=1,显然有,33注意到是最小的方次,由第一章4例5知,使3成立的必有4因此计算333§162020204004064006625),544(mod25),241(mod25),1(mod4),IX1(mod100),1(mod100).29(mod100).33由此及3从性质推出33因此3333所以个位数是9,十位数是2.2020/9/1217773.7.例求的个位数12473(mod10),71(mod10),71(mod10)解：77477,kr记77477kr则有4(7)7kr17(mod10)r7777,77(mod10)rr故只须考虑被4除得的余数即12671(mod4),71(mod4),71(mod4),由7713(mod4)3r，7777r所以37277(1)(3)3(mod10).7773.即的个位数是2020/9/1218cbam一般地，求对模的同余的步骤如下：①求出整数k，使ak1(modm)；②求出正整数r，rk，使得bcr(modk)；——减小幂指数(mod)cbraam③19851949,10|.aZaa练习：若证明5(mod10)aa提示：2020/9/1219四、一些整数的整除特征1110110101010nnnnnnaaaaaaaa设表示(1)3、9的整除特征——各位上的数字之和能被3（9）整除101mod(3)i10101010mod(3)nnnaaaaaaa例1检查5874192、435693能否被3（9）整除。2020/9/1220(2)7、11、13的整除特征2105437|7|aaaaaaa——71113100110001(mod7)10132101000nnnnaaaaaaaaa21013nnaaaaaa21054316nnaaaaaaaaa(mod7).注：一般地，求1210nnaaaaa被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，0121021221010kkkkhkaaaaaaaa再将写成2020/9/1221(2)7、11、13的整除特征特别地，由于，所以101(mod11)101111(1)inniaaaa——奇偶位差法例2检查637693、75312289能否被7（11，13）整除。由693－637＝56，所以637693能被7整除，但不能被11，13整除，当然也可以由6+3-7+6-9+3=2知637693不能被11整除；由75-312+289＝52，所以75312289能被13整除，但不能被7，11整除。2020/9/1222五、弃九法〔验算计算结果〕,(mod9)abcababc若则有应用这种方法可以验算较大整数的乘法。例6.验算28997×39495＝1145236415是否正确。28997178(mod9)，394953(mod9)1145236415325(mod9)835(mod9)但注：若结论成立，其结果不一定正确；所以结果不正确。也可以检查和、差的运算。2020/9/1223例7.求方程2x3y=1的正整数解。解：显然y=1，x=2，是原方程的解。若x3，则20(mod8)x2391(mod8)但21233(mod8),31(mod8)nn所以3y1(mod8)不能成立。故原方程的正整数解只有x=2,y=1.2020/9/1224内容小结1.同余的概念；3.整数整除的一些特征；作业P1191(2),(4);2;7;11(1),(3);122.同余的基本性质；4.弃九法及其应用；