《初等数论(闵嗣鹤、严士健)》第三版课件3-1.pdf

1 11第三章同 余第三章同 余同余是数论中的重要概念，同余理论是研究整数 问题的重要工作之一.本章介绍同余的基本概念，剩 余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如： 某年级有将近400名学生有一次演出节目排队时出 现：如果每8人站成一列则多余1人；如果改为每9人 站成一列则仍多余1人；结果发现现成每10人结成一 列，结果还是多余1人；聪名的你知道该年级共有学 生多少名吗？同余是数论中的重要概念，同余理论是研究整数 问题的重要工作之一.本章介绍同余的基本概念，剩 余类和完全剩余系.生活中我会经常遇到与余数有关的问题，比如： 某年级有将近400名学生有一次演出节目排队时出 现：如果每8人站成一列则多余1人；如果改为每9人 站成一列则仍多余1人；结果发现现成每10人结成一 列，结果还是多余1人；聪名的你知道该年级共有学 生多少名吗？2§3.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？§3.1同余的概念及其基本性质一、问题的提出1、今天是星期一，再过100天是星期几？1010再过天呢？再过天呢？7747、你知道的个位数是多少吗？、你知道的个位数是多少吗？3、、13511，，13903，，14589被自然数被自然数m除所得余数相同，问除所得余数相同，问m最大值是多少？2、3145×92653=2910 93995的横线处漏写了一个数字，你能以最快的办法补出吗？最大值是多少？2、3145×92653=2910 93995的横线处漏写了一个数字，你能以最快的办法补出吗？3二、同余的定义二、同余的定义,,|(),a bZ mZm ababm  设,如果则称 与 对模设,如果则称 与 对模(mod).abm同余，记作： 同余，记作：(mod).abmabm   否则，称 与 对模 不同余，记作：注：下面的三个表示是等价的：否则，称 与 对模 不同余，记作：注：下面的三个表示是等价的：(1)(mod);abm (2),;qZabqm  使得使得1212(3),,,.q qZaq mr bq mr 使得使得4三、同余的性质三、同余的性质TH1 ① ① a   a (mod m)；； ②② a   b (mod m)  b   a (mod m)；； ③③ a   b，，b   c (mod m)  a   c (mod m)。

1a bmm ab 整数对模 同余的充分必要条件为定理112212,,0,.amqr bmqrr rm 证设若    1212mod,,.abmrrabm 则因此反之若     121212,,,m abm m rrm rr则因此但1212,.rrmrr故2 25TH2设设a，，b，，c，，d，，k是整数，并且是整数，并且a   b (mod m)，，c   d (mod m)，则①，则①a   c   b   d (mod m)；②；②ac   bd (mod m); ③③ak   bk (mod m).12(1),,abmq cdmq 证设因此12acbdm  (1)即得 211 2(2)acbdm bqdqmq q (2)即得63,(0),iiTHa binx y  设，都是整数，设，都是整数，mod(),mod(), 0.iixymabmin 并且并且00(mod)nn ii ii iia xb ym   则：则：:(mod)(mod),iixymxym  证明 由得(mod)(mod),ii iiiiabma xb ym  由得00(mod).nn ii ii iia xb ym   再由可加性得7TH4TH4下面的结论成立：①下面的结论成立：①a   b (mod m)，，d m，，d > 0  a   b (mod d)；②；②a   b (mod m)，，k > 0，，k N  ak   bk (mod mk)；③；③a   b (mod mi)，，1   i   k  a   b (mod [m1, m2, , mk])；；④④a   b (mod m)  (a, m) = (b, m)；⑤；⑤ac   bc (mod m)，，(c, m) = 1  a   b (mod m);⑥⑥(mod)(mod)abcmacbm ⑦⑦11(mod),,,( ,)1abm aa d bb dd m 11(mod)abm⑧⑧(mod),,abm da bm 是及 的任一正公因数,则是及 的任一正公因数,则mod.abm ddd8①①a   b (mod m)，，d m，，d > 0  a   b (mod d)；；(mod ).abd(mod)abm 证：证：|m ab|d ab②②a   b(mod m)，，k> 0，，k N ak   bk(mod mk)；；(mod)abm 证：证：|m ab| ()mk k ab(mod).akbkmk③③a   b(mod mi)，，1   i   k  a   b(mod [m1, m2, , mk])(mod)iabm 证：证：im ab1[,,].kmmab④④a   b(mod m) (a, m) = (b, m)；；2bmqr  同理，同理，1amqr  证：证：( ,)(, ),a mm r ( ,)(, ).b mm r证 明证 明3 39⑤⑤ac   bc(mod m)，，(c, m) = 1  a   b(mod m);(mod)acbcm 证：证：m acbc()m ab c()m ab(mod).abm注：若没有条件注：若没有条件(c, m) = 1，即为，即为TH2③的逆命题，不能成立。

但有性质⑧反例：取③的逆命题，不能成立但有性质⑧反例：取m=6,c=2,a=20,b=23.4046(mod6),2023(mod6)这时，有但不成立！这时，有但不成立！10⑥⑥(mod)(mod)abcmacbm (mod)abcm  证：证：m cab()m cba()(mod).acbm⑦⑦11(mod),,,( ,)1abm aa d bb dd m 11(mod).abm(mod)abmm ab 证：证：11()m ab d11()m ab11(mod).abm( ,)1d m  注意：若没有的条件，不能成立！注意：若没有的条件，不能成立！4,6,10,2,mabd 反例： 取反例： 取 610(mod4),35(mod4).  有但不能成立有但不能成立11⑧⑧(mod),,abm da bm 是及 的任一正公因数,则是及 的任一正公因数,则mod.abm ddd:.m abm abd dd 证12四、一些整数的整除特征四、一些整数的整除特征11 10110101010nn nnnnaa aaaaaa     设表示(1)3、9 的整除特征——各位上的数字之和能被3（9）整除设表示(1)3、9 的整除特征——各位上的数字之和能被3（9）整除 101mod(3)101mod(3)i 10101010mod(3)n nnaaaaaaa例例1检查检查5874192、、435693能否被能否被3（（9）整除。

整除033.ni iaa  从而4 413(2) 7、11、13 的整除特征(2) 7、11、13 的整除特征7 11 13100110001(mod7)   -1 -110100010001000,nn nnaaaaa 设07(1113)|7(1113)|(-1).ni i iNa  则 或或或或: 10001(mod7,mod11,mod13),  证明或或1 110100010001000nn nnaaaaa   11 110( 1)( 1)( 1)nn nnaaaa        0( 1)(mod7,mod11,mod13).n i i ia  或或特别地，由于，所以特别地，由于，所以101(mod11)  10 011111ninni ia aaa   ——奇偶位差法——奇偶位差法 14注：一般地，求注：一般地，求1210nnaaaa a 被被m除的余数时，首先是求出正整数除的余数时，首先是求出正整数k，使得，使得10k  1或或1 (mod m)，，0 121021221010kkkkhkaaaa aaaa  再将 写成例再将 写成例3检查检查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整除15771.7.eg求的个位数求的个位数12473(mod10), 71(mod10), 71(mod10)    解：解：77477,k r  记记77477k r  则有则有4(7 )7kr  1 7 (mod10)r   7777,77 (mod10)rr 故只须考虑被4除得的余数 即故只须考虑被4除得的余数 即12671(mod4), 71(mod4), 71(mod4),  由由7713(mod4)3r    ，，7777r 所以所以37 277( 1)( 3)3(mod10).    7773.即的个位数是即的个位数是16cbam一般地，求对模 的同余的步骤如下：一般地，求对模 的同余的步骤如下：① 求出整数① 求出整数k，使，使ak  1 (mod m)；② 求出正整数；② 求出正整数r，，r < k，使得，使得bc  r (mod k)；——减小幂指数；——减小幂指数 (mod)cbraam ③③19851949,10|.aZaa   练习：若证明练习：若证明5(mod10)aa 提示：提示：5 517eg2证明：若证明：若n是正整数，则是正整数，则13 42n + 1  3n + 2 。

解 ：解 ：42n + 1  3n + 2= 4××42n  9××3n 。