初等数论3同余课件.ppt

《初等数论3同余课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章同余同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本章介绍同余的基本概念，剩余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？8/3/20211皖西学院数理系§3.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？3、13511，13903，14

2、589被自然数m除所得余数相同，问m最大值是多少？2、3145×92653=291093995的横线处漏写了一个数字，你能以最快的办法补出吗？8/3/20212皖西学院数理系二、同余的定义注：下面的三个表示是等价的：8/3/20213皖西学院数理系三、同余的性质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是最简单、常用的性质。8/3/20214皖西学院数理系8/3/20

3、215皖西学院数理系TH4下面的结论成立：①ab(modm)，dm，d>0ab(modd)；②ab(modm)，k>0，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);⑥⑦8/3/20216皖西学院数理系①ab(modm)，dm，d>0ab(modd)；②ab(modm)，k>0，kNakbk(modmk)；

4、③ab(modmi)，1ikab(mod[m1,m2,,mk])；④ab(modm)(a,m)=(b,m)；8/3/20217皖西学院数理系⑤acbc(modm)，(c,m)=1ab(modm);注：若没有条件(c,m)=1，即为TH2③的逆命题，不能成立。反例：取m=6,c=2,a=20,b=23.8/3/20218皖西学院数理系⑥⑦8/3/20219皖西学院数理系四、一些整数的整除特征(1)3、9的整除特征——各位上的数字之和能被3（9）整除例1检查5874192、435693

5、能否被3（9）整除。8/3/202110皖西学院数理系(2)7、11、13的整除特征注：一般地，求被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，8/3/202111皖西学院数理系(2)7、11、13的整除特征特别地，由于，所以——奇偶位差法例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，所以

6、75312289能被13整除，但不能被7，11整除。8/3/202112皖西学院数理系8/3/202113皖西学院数理系①求出整数k，使ak1(modm)；②求出正整数r，r

7、z.解因为792=8×9×11，故8n，9n及11n。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。8/3/202116皖西学院数理系五、弃九法〔验算计算结果〕应用这种方法可以验算较大整数的乘法。例6.验算28997×39495＝1145236415是否正确。注：若结论成立，其结果不一定正确；所以结果不正确

8、。也可以检查和、差的运算。8/3/202117皖西学院数理系例7.求方程2x3y=1的正整数解。解：显然y=1，x=2，是原方程的解。若x3，则所以3y1(mod8)不能成立。故原方程的正整数解只有x=2,y=1.8/3/202118皖西学院数理系习题讲解：3.找出整数能被37、101整除的判别条件。8/3/202119皖西学院数理系解：依次计算对模641的同余数224，2416，28256，8/3/202120皖西学院数理系