初等数论§3同余1

4/19/2020皖西学院数理系1第三章同余同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本章介绍同余的基本概念，剩余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？4/19/2020皖西学院数理系2§3.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？1010再过天呢？7747、你知道的个位数是多少吗？3、13511，13903，14589被自然数m除所得余数相同，问m最大值是多少？2、3145×92653=291093995的横线处漏写了一个数字，你能以最快的办法补出吗？4/19/2020皖西学院数理系3二、同余的定义,,|(),abZmZmababm设,如果则称与对模(mod).abm同余，记作：(mod).abmabm否则，称与对模不同余，记作：注：下面的三个表示是等价的：(1)(mod);abm(2),;qZabqm使得1212(3),,,.qqZaqmrbqmr使得4/19/2020皖西学院数理系4三、同余的性质TH1①aa(modm)；②ab(modm)ba(modm)；③ab，bc(modm)ac(modm)。TH2设a，b，c，d，k是整数，并且ab(modm)，cd(modm)，则①acbd(modm)；②acbd(modm);③akbk(modm).注：TH1、TH2是最简单、常用的性质。4/19/2020皖西学院数理系53,(0),iiTHabinxy设，都是整数，mod(),mod(),0.iixymabmin并且00(mod)nniiiiiiaxbym则：4/19/2020皖西学院数理系6TH4下面的结论成立：①ab(modm)，dm，d0ab(modd)；②ab(modm)，k0，kNakbk(modmk)；③ab(modmi)，1ikab(mod[m1,m2,,mk])；④ab(modm)(a,m)=(b,m)；⑤acbc(modm)，(c,m)=1ab(modm);⑥(mod)(mod)abcmacbm⑦11(mod),,,(,)1abmaadbbddm11(mod).abm4/19/2020皖西学院数理系7①ab(modm)，dm，d0ab(modd)；(mod).abd(mod)abm证：|mab|dab②ab(modm)，k0，kNakbk(modmk)；(mod)abm证：|mab|()mkkab(mod).akbkmk③ab(modmi)，1ikab(mod[m1,m2,,mk])；(mod)iabm证：imab1[,,].kmmab④ab(modm)(a,m)=(b,m)；2bmqr同理，1amqr证：(,)(,),ammr(,)(,).bmmr4/19/2020皖西学院数理系8⑤acbc(modm)，(c,m)=1ab(modm);(mod)acbcm证：macbc()mabc()mab(mod).abm注：若没有条件(c,m)=1，即为TH2③的逆命题，不能成立。反例：取m=6,c=2,a=20,b=23.4046(mod6),2023(mod6)这时，有但不成立！4/19/2020皖西学院数理系9⑥(mod)(mod)abcmacbm(mod)abcm证：mcab()mcba()(mod).acbm⑦11(mod),,,(,)1abmaadbbddm11(mod).abm(mod)abmmab证：11()mabd11()mab11(mod).abm(,)1dm注意：若没有的条件，不能成立！4,6,10,2,mabd反例：取610(mod4),35(mod4).有但不能成立4/19/2020皖西学院数理系10四、一些整数的整除特征1110110101010nnnnnnaaaaaaaa设表示(1)3、9的整除特征——各位上的数字之和能被3（9）整除101mod(3)i10101010mod(3)nnnaaaaaaa例1检查5874192、435693能否被3（9）整除。4/19/2020皖西学院数理系11(2)7、11、13的整除特征2105437|7|aaaaaaa——71113100110001(mod7)10132101000nnnnaaaaaaaaa21013nnaaaaaa21054316nnaaaaaaaaa(mod7).注：一般地，求1210nnaaaaa被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，0121021221010kkkkhkaaaaaaaa再将写成4/19/2020皖西学院数理系12(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整除。4/19/2020皖西学院数理系13773.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.即的个位数是4/19/2020皖西学院数理系14cbam一般地，求对模的同余的步骤如下：①求出整数k，使ak1(modm)；②求出正整数r，rk，使得bcr(modk)；——减小幂指数(mod)cbraam③19851949,10|.aZaa练习：若证明5(mod10)aa提示：4/19/2020皖西学院数理系15例4证明：若n是正整数，则1342n+13n+2。解：42n+13n+2=4×42n9×3n4×3n9×3n=13×3n0(mod13)=4×16n9×3n4/19/2020皖西学院数理系16例5设n的十进制表示是1345,xyz且792n，求x，y，z.解因为792=8×9×11，故8n，9n及11n。8|8|456.nzz9n913xy45z=19xy9xy1，(1)11n11z54yx31=3yx113yx。(2)即有xy1=9或18，3yx=0或11解方程组，得到x=8，y=0，z=6。4/19/2020皖西学院数理系17五、弃九法〔验算计算结果〕,(mod9)abcababc若则有应用这种方法可以验算较大整数的乘法。例6.验算28997×39495＝1145236415是否正确。28997178(mod9)，394953(mod9)1145236415325(mod9)835(mod9)但注：若结论成立，其结果不一定正确；所以结果不正确。也可以检查和、差的运算。4/19/2020皖西学院数理系18例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.4/19/2020皖西学院数理系19习题讲解：533,4,5P3.找出整数能被37、101整除的判别条件。37,101101.n解：用试除，除到余数为为止1000=3727+1由2105433737aaaaaaa1001(mod101)由103254101101aaaaaaa3101(mod37)n24101(mod101),101(mod101)4/19/2020皖西学院数理系20324.64121证明：解：依次计算对模641的同余数224，2416，28256，162256256154(mod641)3221541541(mod641)32210(mod641)4/19/2020皖西学院数理系21225.1(mod2)(1).nnaan设为奇数，则解：设a=2m1，当n=1时，有a2=(2m1)2=4m(m1)11(mod23)（*）成立。设式(*)对于n=k成立，则有221(mod2)kka2212kkaq1222(12)kkaq所以32(2)2122kkqq31'2kq记31(mod2),'.kqZ这说明式(*)当n=k1也成立。由归纳法得证.4/19/2020皖西学院数理系224/19/2020皖西学院数理系23§3.2剩余类与完全剩余系一、剩余类——按余数的不同对整数分类1,,01,mZrZrm定义给定对每个称集合():(mod)rKmnnrm是模m的一个剩余类，即余数相同的整数构成m的一个剩余类。一个剩余类中任意一个数称为它同类的数的剩余。一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。4/19/2020皖西学院数理系24定理1().rmZmmKm设，则全部整数分别在模的个剩余类里():(mod)rKmnnrm其中，01,rm并且(1)()rnKm任一整数必包含且仅包含在某个里；(2),,()(mod).rabZabKmabm设，则4/19/2020皖西学院数理系25二、完全剩余系1.定义2mZm设，从模的每一个剩余类里各取一个011,01,,,,imximxxxm数称集合是模的一个完全剩余系，简称完全系.注：①完全剩余系不唯一；②{0,1,2,,m1}是模m的最小非负完全剩余系；③若把剩余系作为一个集合，则可以把对模m的余数相同的整数——即同一剩余类里的整数，看作同一元素。4/19/2020皖西学院数理系26完全剩余系举例：集合{0,6,7,13,24}是模5的一个完全剩余系，集合{0,1,2,3,4}是模5的最小非负完全剩余系。,,1,0,1,,122{}mm和2|1,,1,0,1,,22{}mmm当时，都是模m的绝对最小完全剩余系。112,,1,0,1,,22{}mmm当时，Œ是模m的绝对最小完全剩余系。4/19/2020皖西学院数理系272、完全剩余系的构造定理2整数集合A是模m的完全剩余系的充要条件是①A中含有m个整数；②A中任何两个整数对模m不同余。注：由定理1及定义2易得证。思考：1、既然完全剩余系是不唯一的，不同的剩余系之间存在什么关系呢？2、一个完全剩余系的所有元素通过线性变化后，还是完全剩余系吗？4/19/2020皖西学院数