§3同余PPT优秀课件

1、2021-8-1 1 教学目的和要求教学目的和要求 （1）熟练掌握同余的基本概念及性质。 （2）熟练掌握剩余类、完全剩余系、简 化剩余系和欧拉函数的概念及其性质。 （3）熟练掌握欧拉定理、费马定理和解 某些同余问题。 本章是初等数论的核心内容，是学生必须 掌握的基础知识。 第三章第三章 同同 余余 2021-8-1 2 第三章第三章 同同 余余 同余是数论中的重要概念，同余理论是研究整数同余是数论中的重要概念，同余理论是研究整数 问题的重要工具之一问题的重要工具之一. .本章介绍同余的基本概念，剩本章介绍同余的基本概念，剩 余类和完全剩余系余类和完全剩余系. . 生活中我们经常遇到与余数有关的

2、问题，比如：生活中我们经常遇到与余数有关的问题，比如： 某年级有将近某年级有将近400400名学生。有一次演出节目排队时出名学生。有一次演出节目排队时出 现：如果每现：如果每8 8人站成一列则多余人站成一列则多余1 1人；如果改为每人；如果改为每9 9人人 站成一列则仍多余站成一列则仍多余1 1人；如果每人；如果每1010人结成一列，结果人结成一列，结果 还是多余还是多余1 1人；聪明的你知道该年级共有学生多少名？人；聪明的你知道该年级共有学生多少名？ 2021-8-1 3 中学数学竞赛中学数学竞赛 1 1、今天是星期一，再过、今天是星期一，再过100100天是星期几？天是星期几？ 10 10

3、再再过过天天呢呢？ 7 7 47、你你知知道道的的个个位位数数是是多多少少吗吗？ 3、13511，13903，14589被自然数被自然数m除所得余数除所得余数 相同，问相同，问m最大值是多少？最大值是多少？ 2 2、3145314592653=2910 9399592653=2910 93995的横线处漏写了一个的横线处漏写了一个 数字，你能以最快的办法补出吗？数字，你能以最快的办法补出吗？ 2021-8-1 4 一、同余一、同余 3.13.1同余的概念及其基本性质同余的概念及其基本性质 1.定义定义1 给定正整数m，如果用m去除任意的 两个整数a与b所得的余数相同，则称a与b对 于模m同余。

4、记为 如果余数不同，则称a与b对于模m不同余。记为 )(modmba )(modmb a 注：注：mod是英语是英语modulo( (对对模模) )的缩写的缩写 ,5mod621如：,10mod7432mod8 3 2021-8-1 5 2 2、判断、判断a,b对模对模m同余同余 定义定义 (1)(mod);abm (2),;qZabqm 使使得得 1212 (3),.q qZaq mr bq mr 使使得得 3.13.1同余的概念及其基本性质同余的概念及其基本性质 定理定理1 1 整数整数a,b对对m同余的充要条件是同余的充要条件是 Ztmtbabam,),(即 注：下面的三个表示是等价的：

5、注：下面的三个表示是等价的： 2021-8-1 6 二、同余的性质二、同余的性质 3 3、同余关系是等价关系、同余关系是等价关系 1221 (mod ),|() ()() |()(mod ) nnnnnn nnnn abmm a b aba b aababb m ababm L 2021-8-1 7 二、同余的性质二、同余的性质 1122 1212121 2 11 2.(mod),(mod), ()(mod),(mod) (mod) abm abm aabbm a abbm kakbm 若则 ， 1122 11122212 1212 1212 (mod),(mod) , , , ()(mod)

6、 abm abm abmt abmt t tZ aabbmt tZ aabbm 2021-8-1 8 推广：推广： 11 11 (mod),1,2, 1)(mod), 2)(mod) ii nn iiii ii nn ii ii abm in k ak bm abm L若则 )(mod),(mod. 3mbcamcba则若 都是整数，设yxniba ii ,),0(,. 4 mod(),(mod),0. ii xymabmin 并并且且 00 (mod) nn ii ii ii a xb ym 则则： (mod)abcm证证：m cab ()m cba ()(mod).acbm 2021-8-

7、1 9 11 (mod), ( ,)1abm aa d bb dd m 11(mod ).abm 5. )(mod)(),( 1),(mod 111111 11 mbabamdbdam mdbda 。所以，从而 得由定理证：由已知得： ( ,)1d m 注注意意：若若没没有有的的条条件件，不不能能成成立立！ 4,6,10,2,mabd 反反例例： 取取 610(mod4),35(mod4). 有有但但不不能能成成立立 2021-8-1 10 6.6. a b (mod m)，k 0，k N ，则，则 1）ak bk (mod mk)； 2)(mod),| ,| ,| abm d a d b d

8、 m ddd 其中 (mod)abm 证证：|m ab| ()mk k ab (mod).akbkmk 7.7. 若若a b (mod mi )，1 i k ，则，则 a b (mod m1, m2, , mk)； (mod) i abm 证证： i m ab 1 ,. k mmab L L 2021-8-1 11 8. 8. 若若 a b (mod m)，d m，d 0， 则则 a b (mod d)； 9.9. 若若a b (mod m) ，则，则 (a, m) = (b, m)； (mod)abm 证证： |m ab| d ab (mod ).abd 1 amqr 证证： ( ,)(,

9、),a mm r 2 bmqr 同同理理， ( ,)(, ).b mm r 2021-8-1 12 55 232232(mod23)9(mod23)Q解： 除所得的余数被求例2321 40 )23(mod8122 10 知：由性质 )23(mod1281又 )23(mod12210 )23(mod6)23(mod144)23(mod122 220 )23(mod13)23(mod36)23(mod62 240 1323240除所得的余数为被所以， 2021-8-1 13 解：依次计算对模解：依次计算对模641的同余数的同余数 22 4（mod641）,24 16（mod641mod641）,

10、28 256（mod641mod641） 16 2256256154(mod641) 32 2154 1541(mod641) 32 210(mod641) 整除能否被判断例641122 32 整除能被所以，6411232 2021-8-1 14 11 110110 3101010 nn nnnn Na aa aaaaa LL例 设 n i i n i i aNaN 00 99)2(331 ）则（ n i i i aN 0 ) 1(11113）（ 2 (1)101(mod3)101(mod3)101(mod3) n QL证：， ， 110 +(mod3) nn Naaaa L（） n i i

11、aN 0 33 ）的证明类似（ 1)2( 2 (3)101(mod11),101(mod11)10( 1) (mod11) nn QL， ， 11 110 ( 1)( 1)( 1)(mod11) nn nn Naaaa L n i i i aN 0 ) 1(1111 2021-8-1 15 )10000(1000100010004 0 1 1 1 1 i n n n n aaaaaN设例 n i i ia N 0 1-)1311(7)1311(7）（或或或或则 10001(mod7mod11mod13) Q证：或或 1000( 1) (mod7mod11mod13) (1,2) ii in L

12、 或或 11 110 ( 1)( 1)( 1) (mod7mod11mod13) nn nn Naaaa L 或或 2021-8-1 16 21 75 ( 1)312 ( 1)28952 7 52,1152,13 52 Q 例例5判断判断75312289能否被能否被7（9，11，13）整除。）整除。 289100031210007575312289 12 解： 所以，所以，75312289不能被不能被7（11）整除，）整除，能被能被1313整除整除 753 12289379 37 Q 整除不能被975312289 2021-8-1 17 数字（十进制）的个位数字与最后两位求例 406 36 2

13、 39(mod10)-1(mod10)Q解： )10(mod13),10(mod13 4044 )10(mod9333 2404406 93406的个位数字是 6 329(mod100)Q又 )100(mod13),100(mod493 )100(mod833),100(mod613),100(mod873 2010 987 ， )100(mod293333 66400406 则 293406的最后两位数字是 2021-8-1 18 124 73(mod10), 71(mod10), 71(mod10) 解解： 7 74 77, k r 记记 7 74 77 k r 则则有有 4 (7 )7

14、kr 1 7 (mod10) r 7 77 7,77 (mod10) r r 故故只只须须考考虑虑被被4 4除除得得的的余余数数 即即 123 73(mod10), 71(mod10), 73(mod10), 由由 734 7773(mod10)3r ， 7 7 77 r 所所以以 3 7 2 77 ( 1)( 3)3(mod10). 7 7 73.即即的的个个位位数数是是 的个位数求例 7 7 77 2021-8-1 19 例例8 设设n的十进制表示是的十进制表示是 1345 ,xyz且且792 n， 求求 x，y，z. 解解 因为因为792 = 8911，故，故8 n，9 n及及11 n。

15、 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。 2021-8-1 20 五、弃九法五、弃九法验算计算结果验算计算结果 ,(mod9)abcababc若若则则有有 应用这种方法可以验算较大整数的乘法。应用这种方法可以验算较大整数的乘法。 例例9. 9. 验算验算 2899728997394953949511

16、452364151145236415是否正确。是否正确。 28997178(mod9)Q ，394953(mod9) 1145236415325(mod9) 835(mod9) 但但 注：若结论成立，其结果不一定正确；注：若结论成立，其结果不一定正确； 所以结果不正确。所以结果不正确。 也可以检查和、差的运算。也可以检查和、差的运算。 2021-8-1 21 2021-8-1 22 3.2 3.2 剩余类与完全剩余系剩余类与完全剩余系 引言引言 一个整数被正整数一个整数被正整数n除后，余数有除后，余数有n种情形：种情形：0 0， 1 1，2 2，3 3，n-1-1，它们彼此对模，它们彼此对模n

17、不同余。这表不同余。这表 明，每个整数恰与这明，每个整数恰与这n个整数中某一个对模个整数中某一个对模n同余。同余。 这样一来，按模这样一来，按模n是否同余对整数集进行分类，可是否同余对整数集进行分类，可 以将整数集分成以将整数集分成n个两两不相交的子集。个两两不相交的子集。 2021-8-1 23 3.2 3.2 剩余类与完全剩余系剩余类与完全剩余系 一、一、剩余类剩余类 按余数的不同对整数分类按余数的不同对整数分类 1,01,mZrZrm 定定义义 给给定定对对每每个个称称集集合合 是模是模m的一个剩余类，的一个剩余类， 即即 余数相同的整数构成余数相同的整数构成m的的一个剩余类。一个剩余类

18、。 注：一个剩余类中任意一个数称为它同类注：一个剩余类中任意一个数称为它同类的数的剩余。的数的剩余。 )(mod)(mrnnmKr 1.1.剩余类剩余类 2021-8-1 24 K0(5) = nn 0 (mod 5)，n Z K1(5) = nn 1 (mod 5)，n Z K2(5) = nn 2(mod 5)，n Z K3(5) = nn 3 (mod 5)，n Z K4(5) = nn 4(mod 5)，n Z 模模5 5的五个剩余类是的五个剩余类是 2021-8-1 25 2.2.定理定理1 1 (). r mZmmK m 设设，则则全全部部整整数数分分别别在在模模 的的 个个剩剩余

19、余类类里里 01,rm 并并且且 (1)() r nK m任任一一整整数数 必必包包含含且且仅仅包包含含在在某某个个里里； (2),()(mod). r a bZa bK mabm 设设，则则 ，其中)(mod)(mrnnmKr 2021-8-1 26 二、完全剩余系二、完全剩余系 1.1.定义定义2 2 mZm 设设，从从模模 的的每每一一个个剩剩余余类类里里各各取取一一个个 011 ,01, im ximxxxm 数数称称集集合合是是模模 的的一一个个L 完完全全剩剩余余系系，简简称称完完全全系系. . 完全剩余系不唯一；完全剩余系不唯一； 若把剩余系作为一个集合，则同一剩余类里若把剩余系

20、作为一个集合，则同一剩余类里 的整数，看作同一元素。的整数，看作同一元素。 注：注： 模模m的一个完全剩余系有且仅有的一个完全剩余系有且仅有m个整数；个整数； 2021-8-1 27 2.2.定义定义3 3： 集合集合0, 6, 7, 13, 24是模是模5的一个完全剩余系，的一个完全剩余系， 如，集合如，集合0, 1, 2, 3, 4是模是模5的最小非负完全剩余系。的最小非负完全剩余系。 ,1,0,1,1 22 LL mm 和和 2|1,1, 0,1, 22 LL mm m当当时时， 叫做模叫做模m的绝对最小完全剩余系。的绝对最小完全剩余系。 叫做模叫做模m的绝对最小完全剩余系。的绝对最小完

21、全剩余系。 0,1, 2, , m 1这这m个整数个整数叫做模叫做模m的最小非负的最小非负 完全剩余系；完全剩余系； m-11 2-, 1,0,1, 22 m m LL当 不整除 时， L 2021-8-1 28 例例1 1 写出模写出模7 7（或（或8 8）的）的最小非负完全剩余系和最小非负完全剩余系和绝对绝对 最小完全剩余系最小完全剩余系 模模7的绝对最小完全剩余系为的绝对最小完全剩余系为-3,-2,-1,0,1,2,3 解：解：模模7 7的的最小非负完全剩余系为最小非负完全剩余系为0,1,2,3,4,5,60,1,2,3,4,5,6 2021-8-1 29 3 3、完全剩余系的构造、完全

22、剩余系的构造 推论推论 m个整数作成模个整数作成模m的完全剩余系的充要条件是的完全剩余系的充要条件是 两两对模两两对模m不同余。不同余。 注：由定理注：由定理1 1及定义及定义2 2易得证。易得证。 思考思考：1 1、既然完全剩余系是不唯一的，不同的剩余系、既然完全剩余系是不唯一的，不同的剩余系 之间存在什么关系呢？之间存在什么关系呢？ 2 2、一个完全剩余系的所有元素通过线性变换、一个完全剩余系的所有元素通过线性变换 后，还是完全剩余系吗？后，还是完全剩余系吗？ 2021-8-1 30 检验：设检验：设x1, x2, , xm是模是模m的一个完全剩余系，的一个完全剩余系， 那么，那么，b+x

23、1, b+x2, , b+ xm和和 ax1, ax2, ,axm 是模是模m的一个完全剩余系吗？的一个完全剩余系吗？ 6,2mb 5,2mb 5,2ma 6,2ma L LL 2021-8-1 31 定理定理2设设m 1，a，b是整数，是整数，(a, m) = 1，x1, x2, , xm 是模是模m的一个完全剩余系，则的一个完全剩余系，则 ax1 b, ax2 b, , axm b也是模也是模m的完全剩余系。的完全剩余系。 证明证明 由定理由定理1，只需证明：若，只需证明：若xi xj， 则则 axi b axj b (mod m)。 假设假设 axi b axj b (mod m)， 则

24、则 axi axj (mod m)， 且且(a, m) = 1， xi xj (mod m) 由由3.13.1中的结论中的结论,P50,P50第三行知：第三行知： . ij xx 1, i jm L L 2021-8-1 32 注意：注意： (2)(2)在定理在定理2 2中，条件中，条件(a, m) = 1不可缺少，否则不能不可缺少，否则不能 成立；成立； (3) 定理定理2也可以叙述为：设也可以叙述为：设m 1，a，b是整数，是整数， (a, m) = 1，若若x通过模通过模m的一个完全剩余系，的一个完全剩余系， 则则ax+b也通过模也通过模m的一个完全剩余系；的一个完全剩余系； （4）特别

25、地，若）特别地，若x通过模通过模m的一个完全剩余系，的一个完全剩余系， (a, m) = 1,则则ax和和x+b也分别通过模也分别通过模m的一的一 个完全剩余系。个完全剩余系。 (1)(1)任意任意m m个连续整数都能构成模个连续整数都能构成模m m的一个完全剩余系的一个完全剩余系； 2021-8-1 33 例例1 设设p 5是素数，是素数，a 2, 3, , p 1，则，则 在数列在数列a，2a，3a， ，(p 1)a，pa中有且仅有中有且仅有 一个数一个数b，满足，满足 b 1 (mod p). 证证 ： 因为因为1，2，3， ，(p 1)，p是模是模p的的 一个完全剩余系，一个完全剩余系

26、， ( , )1papa p是是素素数数， 所以所以a，2a，3a， ，(p 1)a，pa构成模构成模p的的 一个完全剩余系。一个完全剩余系。 因此必有唯一的数因此必有唯一的数b满足式满足式b 1 (mod p)。 L L L L 2021-8-1 34 例例2 设设A = x1, x2, , xm是模是模m的一个完全剩余系，的一个完全剩余系， 以以x表示表示x的小数部分，证明：若的小数部分，证明：若(a, m) = 1，则，则 1 1 (1) 2 m i i axb m m 证：证： 当当x通过模通过模m的完全剩余系时，的完全剩余系时，ax b也通过也通过 模模m的完全剩余系，的完全剩余系，

27、 因此对于任意的因此对于任意的i（1 i m），），axi b一定与且只与一定与且只与 某个整数某个整数j（1 j m）同余，）同余， 即存在整数即存在整数k，使得，使得 axi b = km j，（，（1 j m） 11 mm i ij axbj k mm 从从而而 1 m j j m 1 1 m j j m 1 1 m j j m 1(1) 2 m m m 1 2 m . . L 2021-8-1 35 定理定理3 若若m1, m2 N，(m1, m2) = 1，当当x1与与x2分别通过分别通过 模模m1与模与模m2的完全剩余系时，的完全剩余系时， 则则 m2x1 m1x2通过模通过模m1

28、m2的完全剩余系。的完全剩余系。 4 4、剩余系间的联系、剩余系间的联系 2021-8-1 36 例例3 设设m 0是偶数，是偶数，a1, a2, , am与与b1, b2, , bm 都是模都是模m的完全剩余系，的完全剩余系， 则则a1 b1, a2 b2, , am bm不是模不是模m的完全剩余系。的完全剩余系。 证证 由由1, 2, , m与与a1, a2, , am都是模都是模m的完全的完全 剩余系，剩余系， 11 (1) (mod ) 22 mm i ii m mm aim 所所以以， 1 (mod) 2 m i i m bm 同同理理， 如果如果a1 b1, a2 b2, , am

29、 bm是模是模m的完全剩余系，的完全剩余系， 1 ()(mod) 2 m ii i m abm 则则 111 0()(mod) 2222 mmm iiii iii mmmm =ababm 从从而而 不可能！不可能！ L L L LL L 2021-8-1 37 例例4 设设mi N（1 i n），则当），则当xi通过模通过模mi（1 i n） 的完全剩余系时，的完全剩余系时， x = x1 m1x2 m1m2x3 m1m2 mn 1xn 通过模通过模m1m2 mn的完全剩余系。的完全剩余系。 证明证明 对对n施行归纳法。施行归纳法。 当当n = 2时，结论成立。时，结论成立。 假设定理结论当假

30、设定理结论当n = k时成立，时成立， 即当即当xi（2 i k 1）分别通过模）分别通过模mi的完全剩余系时，的完全剩余系时， y = x2 m2x3 m2m3x4 m2 mkxk 1 通过模通过模m2m3mk 1的完全剩余系。的完全剩余系。 L L L L L L 2021-8-1 38 y = x2 m2x3 m2m3x4 m2 mkxk 1 通过模通过模m2m3 mk 1的完全剩余系。的完全剩余系。 由定理由定理3，当，当x1通过模通过模m1的完全剩余系，的完全剩余系， xi（2 i k 1）通过模）通过模mi的完全剩余系时，的完全剩余系时， x1 m1y = x1 m1(x2 m2x

31、3 m2 mkxk 1) = x1 m1x2 m1m2x3 m1m2 mkxk 1 通过模通过模m1m2 mk 1的完全剩余系。的完全剩余系。 即结论对于即结论对于n = k 1也成立。也成立。 L L L LL L L L 2021-8-1 39 2021-8-1 40 3.3 3.3 简化剩余系与欧拉函数简化剩余系与欧拉函数 一、基本概念一、基本概念 定义定义1 设设R是模是模m的一个剩余类，若有的一个剩余类，若有a R，使得，使得(a, m) = 1，则称，则称R是模是模m的一个简化剩余类的一个简化剩余类。 即与模即与模m互质的剩余类。互质的剩余类。 注：若注：若R是模是模m 的简化剩余

32、类，则的简化剩余类，则R中的数都与中的数都与m互素。互素。 例如，模例如，模4的简化剩余类有两个：的简化剩余类有两个： R1(4) = , 7 , 3, 1 , 5 , 9 , ， R3(4) = , 5 , 1 , 3 , 7 , 11 , 。 L L L LL 2021-8-1 41 定义定义2 对于正整数对于正整数k，令函数，令函数 (k)的值等于模的值等于模k的所有的所有 简化剩余类的个数，称简化剩余类的个数，称 (k)为为Euler函数。函数。 容易验证：容易验证： (2) = 1， (3) = 2， (4) = 2， (7) = 6。 注注:(1) (m)就是在就是在m的一个完全剩

33、余系中与的一个完全剩余系中与m互素的互素的 整数的个数，整数的个数， 1 2, . Lmm m 即即等等 于于 ，中中 与与互互 素素 的的 个个 数数 1 11 (3)( )1, (). 12 ,2 ,3 ,. , kkk kk kk pppppp ppp pppppp L L 当 为素数时， 因为 ， ， ，中与不互素的能被 整除的数 共个 (2) (1)1, (2)1 2021-8-1 42 定义定义3 对于正整数对于正整数m，从模，从模m的每个简化剩余类中的每个简化剩余类中 各取一个数各取一个数xi，构成一个集合，构成一个集合x1, x2, ,x (m)， ， 称为模称为模m的一个简化

34、剩余系（或简称为简化系）。的一个简化剩余系（或简称为简化系）。 注：由于选取方式的任意性，模注：由于选取方式的任意性，模m的简化剩余系的简化剩余系 有无穷多个。有无穷多个。 例如，集合例如，集合9, 5, 3, 1是模是模8的简化剩余系；的简化剩余系； 集合集合1, 3, 5, 71, 3, 5, 7也是模也是模8 8的简化剩余系的简化剩余系. . 集合集合1, 3, 5, 71, 3, 5, 7称为模称为模8 8的最小非负简化剩余系。的最小非负简化剩余系。 注：模注：模m的任意一组简化剩余系中有的任意一组简化剩余系中有 ( (m m) )个整数个整数 L 2021-8-1 43 二、主要性质

35、二、主要性质 1.定理定理1 整数集合整数集合A是模是模m的简化剩余系的充要条件是：的简化剩余系的充要条件是： A中含有中含有 (m)个整数；个整数； A中的任何两个整数对模中的任何两个整数对模m不同余；不同余； A中的每个整数都与中的每个整数都与m互素。互素。 说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素 构成的集合，故满足条件构成的集合，故满足条件2； 由定义由定义1易知满足条件易知满足条件3； 由定义由定义3 3易知满足条件易知满足条件1 1。 2021-8-1 44 2.定理定理2 若若a1, a2, , a (m)是是 (m)个与个与 m互

36、质的整数，且两两对模互质的整数，且两两对模m不同余，不同余， 则则a1, a2, , a (m) 是模是模m的一个简的一个简 化系。化系。 (留做练习留做练习) L L 2021-8-1 45 3.定理定理3 设设a是整数，是整数，(a, m) = 1，B = x1, x2, , x (m) 是模是模m的简化剩余系，则集合的简化剩余系，则集合 A = ax1, ax2, , ax (m) 也是模也是模m的简化剩余系。的简化剩余系。 证明证明:1)显然，集合显然，集合A中有中有 (m)个整数。个整数。 2)由于由于(a, m) = 1， 对于任意的对于任意的xi（1 i (m)），xi B， 有

37、有(axi, m) = (xi, m) = 1。 故故A中的每一个数都与中的每一个数都与m互素。互素。 3)A中的任何两个不同的整数对模中的任何两个不同的整数对模m不同余。不同余。 因为，若有因为，若有x , x B，使得，使得 a x ax (mod m)， 那么，那么， x x (mod m)， 于是于是x = x 。 由以上结论及定理由以上结论及定理1可知集合可知集合A是模是模m的一个简化系。的一个简化系。 注注:条件条件(a, m) = 1不可少。不可少。 L L 2021-8-1 46 注：在定理注：在定理3的条件下，若的条件下，若b是整数，集合是整数，集合 ax1 b, ax2 b

38、, , ax (m) b 不一定是模不一定是模m的简化剩余系。的简化剩余系。 例如，取例如，取m = 4，a = 1，b = 1， 以及模以及模4的简化剩余系的简化剩余系1, 3。 但但2 2，4 4不是模不是模4 4的简化剩余系。的简化剩余系。 L 2021-8-1 47 4.定理定理4 设设m1, m2 N，(m1, m2) = 1，又设，又设 12 12()12() ,LL mm Xx xxYyyy ，与与， 分别是模分别是模m1与与m2的简化剩余系，的简化剩余系， 则则 A = m1y m2xx X，y Y 是模是模m1m2的简化剩余系。的简化剩余系。 证明证明 由第二节定理由第二节定

39、理3 3可知，可知， 若以若以X 与与Y 分别表示分别表示 模模m1与与m2的完全剩余系，使得的完全剩余系，使得X X ，Y Y ， 则则A = m1y m2xx X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。 因此只需证明因此只需证明A 中所有与中所有与m1m2互素的整数的集合互素的整数的集合R 即模即模m1m2的简化剩余系是集合的简化剩余系是集合A。 2021-8-1 48 若若m1y m2x R，则，则(m1y m2x, m1m2) = 1， 所以所以(m1y m2x, m1) = 1， 于是于是 (m2x, m1) = 1，(x, m1) = 1，x X。 同理可得到同理

40、可得到y Y，因此，因此m1y m2x A。 这说明这说明R A。 另一方面，若另一方面，若m1y m2x A，则，则x X，y Y， 即即 (x, m1) = 1，(y, m2) = 1。由此及由此及(m1, m2) = 1得到得到 (m2x m1y, m1) = (m2x, m1) = 1 (m2x m1y, m2) = (m1y, m2) = 1。 因为因为m1与与m2互素，所以互素，所以(m2x m1y, m1m2) = 1， 于是于是m2x m1y R。因此。因此A R。 从而从而A = R。 2021-8-1 49 推论推论 设设m1, m2 N,(m1, m2) = 1,则则 (

41、m1m2) = (m1) (m2) 证证 由定理由定理4知，若知，若x1,x2分别通过分别通过m1 , m2的简化剩余系，的简化剩余系， 则则m1x2 m2x1通过通过m1m2的简化剩余系，的简化剩余系， 即有即有 m1x2 m2x1通过通过 (m1m2)个整数。个整数。 另一方面，另一方面，x1m2x1通过通过 (m1)个整数，个整数， x2m1x2通过通过 (m2)个整数个整数, 从而从而m1x2 m2x1通过通过 (m1) (m2)个整数。个整数。 故有故有 (m1m2) = (m1) (m2)。 注：可以推广到多个两两互质数的情形。注：可以推广到多个两两互质数的情形。 2021-8-1

42、 50 注：由上式立即得到注：由上式立即得到 若若n=2m，（，（2，m）=1，则，则 (n)= (m)； 若若m是奇数，则是奇数，则 (4m) =2 (m)。 2021-8-1 51 5.定理定理5 设设n是正整数，是正整数，p1, p2, , pk是它的全部素因数，是它的全部素因数， 证证 设设n的标准分解式是的标准分解式是 1 i k i i np 由定理由定理4 4推论得到推论得到 1 ( )() i k i i np 对任意的素数对任意的素数p， (p )等于数列等于数列1, 2, , p 中与中与p 互素的整数的个数，互素的整数的个数， 1 1 ()1() p ppppp pp 因

43、因此此， 从而定理得证。从而定理得证。 12 111 111( )()() () k ppp nnL则 L 2021-8-1 52 证：证： 显然显然mn与与m, n有相同的素因数，有相同的素因数， 设它们是设它们是pi（1 i k），则），则 12 111 ()111()() () k mnmn ppp ，L 12 111 (, ), 111()() () k m nm n ppp . .L 由此两式及由此两式及mn = (m, n)m, n即可得证。即可得证。 例例2.2.证明：若证明：若m, n N，则，则 (mn) = (m, n) (m, n) ）（计算例3001 22 30023

44、5 111 300300(1-)(1-)(1-)80 235 Q解： （） 三、应用举例三、应用举例 2021-8-1 53 例例3 设设n N，证明：，证明： 1) 若若n是奇数，则是奇数，则 (4n) = 2 (n)； 的充要条件是的充要条件是n = 2k，k N； 1 2) ( ) 2 nn 的充要条件是的充要条件是n = 2k3l，k, l N； 1 3) ( ) 3 nn 4) 若若6 n，则，则 (n) 1 3 n 2021-8-1 54 1) 若若n是奇数，则是奇数，则 (4n) = 2 (n)； (4n) = (22n) = (22) (n) = 2 (n) 2021-8-1

45、55 的充要条件是的充要条件是n = 2k，k N； 1 2) ( ) 2 nn 若若n = 2k， 1 (2 ) TH4 21 2 () kk 则则 1 2k 1 2 n 若若 (n) = 1 2 n设设n = 2kn1， 1 2 n n 1 2 n 由由 (n) = (2kn1) = (2k) (n1 ) =2 k 1 (n1) 1 1 1 1() 2 2 k n n n 1 1 1() 2 n n n 11 ()nn 所以所以n1 = 1，即，即n = 2k； 2021-8-1 56 的充要条件是的充要条件是n = 2k3l，k, l N； 1 3) ( ) 3 nn 111 213 1

46、 233 () () kl n 1 ( ), 3 nn 若若 设设 n = 2k3ln1， 1 1 ( )(2 3) 3 kl nnn由由 1 (2 ) (3 ) () kl n 11 ()nn 所以所以n1 = 1，即，即n = 2k3l； 若若 n = 2k3l， 则则 (n) = (2k) (3l) 1 1 1() 3 n n n 1 2,3均不整除n 2021-8-1 57 4) 若若6 n，则，则 (n) 1 3 n 设设 n = 2k3ln1， 则则 (n) = (2k) (3l) (n1) 1 3 n 1 1 2 3() 3 kl n 1 1 2 3 3 kl n 1 2,3均不

47、整除n 2021-8-1 58 2021-8-1 59 3.43.4欧拉定理欧拉定理 费马定理及其对循环小数的应用费马定理及其对循环小数的应用 本节主要通过应用简化剩余系的性质证明本节主要通过应用简化剩余系的性质证明 数论中的两个重要定理，欧拉定理和费马定理数论中的两个重要定理，欧拉定理和费马定理, 并说明其在理论和解决实际问题中的应用。并说明其在理论和解决实际问题中的应用。 2021-8-1 60 一、两个基本定理一、两个基本定理 定理定理1 Euler 设设 m是正整数，是正整数，(a, m) = 1， 则则 a m) 1 (mod m). 证明：证明： 设设x1, x2, , x (m)

48、是模是模m的一个简化剩余系，的一个简化剩余系， 则则ax1, ax2, , ax (m)也是模也是模m的简化剩余系，的简化剩余系， 所以所以 ax1ax2 ax (m) x1x2 x (m) (mod m)， 即即 a (m)x1x2 x (m) x1x2 x (m) (mod m). 12() (,)(,)(,)1 m x mx mxm 由由L 得得 (x1x2 x (m), m) = 1， 所以所以 a (m) 1 (mod m). L L L L L L L 2021-8-1 61 定理定理2(Fermat) 设设p是素数，是素数， ,aZ 则则对对有有a p a (mod p)。 注：

49、注：FermatFermat定理即是欧拉定理的推论。定理即是欧拉定理的推论。 证：证： 由于由于p是素数，是素数， ( )1.pp 所所以以 若若 (a, p) 1， 则由定理则由定理1 1得到得到 a p 1 1 (mod p) a p a (mod p) 若若(a, p) 1，则，则p a， 所以所以 a p 0 a (mod p) a m) 1 (mod m) 2021-8-1 62 注注:根据欧拉定理，当根据欧拉定理，当(a, m) = 1时，时， 总能找到总能找到x= (m)，使得，使得ax 1 (mod m)。 但但 (m)并不是使并不是使ax 1 (mod m)成立的自成立的自

50、然数然数x中的最小数。中的最小数。 2021-8-1 63 二、定理的应用举例二、定理的应用举例 例例1 求求131956 被被60除的余数。除的余数。 a m) 1 (mod m) 即即 131956被被60除的余数为除的余数为1。 解：解： 111 (13,60)1, (60)60(1)(1)(1)16 235 Q ）（由欧拉定理得60mod113 16 ）（）（）（）（）（ ）（）（又 60mod160mod12160mod11-60mod49 60mod16960mod131313 22 244122161956 2021-8-1 64 练习练习 求求313159被被7除的余数。除的余

51、数。 159 (75)k 159 5(mod7) (7)6 又又， 所以由欧拉定理得所以由欧拉定理得 6 51(mod7) a m) 1 (mod m) 从而从而 5159= (56)2653 5 3 (mod 7) 53 = 25 5 4 5 6 (mod 7)。 即即 313159被被7除的余数为除的余数为6。 解：解：313159 2021-8-1 65 a m) 1 (mod m) 即即 所求余数为所求余数为5 210 101010 21010+107L例 计算被 除的余数 .7mod11067( 6 ）（，由欧拉定理得）解： 210 104 mod6 ,104 mod6 ,104 m

52、od6L又（）（） ，（） 210 101010444 4444 1010101010 +10mod7 333mod7310(mod7) 4 3 mod75 mod7 LL L （） （） （） （） 2021-8-1 66 例例3 如果今天是星期一，再过如果今天是星期一，再过1010 10天是星期几？ 天是星期几？ 1024 4(mod6) 10 1064,()qqN即即， (10,7)1 因因为为， 6 101(mod7). 所所以以 10 1064 1010 q 从从而而 64 (10 ) 10 q 4 1 10 q 4(mod7). 即得：再过即得：再过1010 10天是星期五。 天是

53、星期五。 4 (3) 1010 10( 2) 解：解： 2021-8-1 67 三、在分数与小数互化中的应用三、在分数与小数互化中的应用 有理数，即有限小数和无限循环小数，可以用有理数，即有限小数和无限循环小数，可以用 分数来表示。利用欧拉定理可以解决分数、小数的分数来表示。利用欧拉定理可以解决分数、小数的 转化问题。转化问题。 1.1.定义定义 如果对于一个无限小数如果对于一个无限小数 12 0. n a aaLL ,0,0,s tZ st ,1,2, ;0,1,. s is i kt aait k 使使得得LL 则称之为循环小数，并简记为则称之为循环小数，并简记为 1 12 0. ss t

54、 s a aa aa 注：注：若找到的若找到的t是最小的，则称是最小的，则称 为循环节；为循环节；t称为循环节的长度；若最小的称为循环节的长度；若最小的s0， 则称该小数为纯循环小数，否则为混循环小数。则称该小数为纯循环小数，否则为混循环小数。 12 , sss t aaa L ， 2021-8-1 68 2.2.定理定理3 3 有理数有理数 ,0,( , )1 a ab a b b 能表示为能表示为纯纯循环小数循环小数 ( ,10)1.b 即：分母不含质因数即：分母不含质因数2 2或或5 5。 1212 ()0.LLL tt a a aa a aa b 证证：设设能能表表示示为为纯纯循循环环

55、小小数数， 121 121 101010+10L ttt tt a aaaa b 则则 1212 +0.LLL tt a aa a aa, a qqZ b 101 t aq b (101) t abq ( , )1a b 又又，101 t b( ,10)1.b 所所以以 2021-8-1 69 定理定理3 3 有理数有理数 ,0,( , )1 a ab a b b 能表示为能表示为纯纯循环小数循环小数 ( ,10)1.b (b, 10) = 1 ()由由Euler定理可知，有正整数定理可知，有正整数k，使得，使得 10k 1 (mod b)，0 k (b)， 因此存在整数因此存在整数q使得使得

56、 10 10(*) kk aa aqbaq bb ， 而且而且ak, , a1不能都等于不能都等于0，也不能都等于，也不能都等于9。 11 1 101 kkk a a aa b 11 (*)(101) k kk a qa aa b 由由式式得得， 112 11 1010 () kkkk a aa = 0.akak 1 a1akak 1a1 。 2021-8-1 70 3.定理定理4 设设a与与b是正整数，是正整数，0 a b，(a, b) = 1， 并且并且 b = 2 5 b1，(b1, 10) = 1，b1 1， 此处此处 与与 是不全为零的正整数，是不全为零的正整数， 其中不循环的位数码

57、个数是其中不循环的位数码个数是 = max= max . . 则则 可以表示成可以表示成混混循环小数，循环小数， a b 证明：不妨假设证明：不妨假设 = = ， 1 11 2 10 aaa M bbb 则则 其中其中0 a1 b1，0 M 10 ， 且且(a1, b1) = (2 a Mb1, b1) = (2 a, b1) = (a, b1) = 1。 1 1 a b 因此，由定理因此，由定理3， 可以表示成纯循环小数：可以表示成纯循环小数： 2021-8-1 71 1 111 1 0 .0 . kkk a cc cccc b 记记， M = m110 1 m210 2 m （0 mi 9

58、，1 i ），）， 1 1 11 1010 aa M bb 则则 11 1 0.0. 10 k mmcc 11 0. k mm cc . . 下面说明，上式中的下面说明，上式中的 是最小的不循环位数码的个数。是最小的不循环位数码的个数。 若不然，设又有正整数若不然，设又有正整数， 11 0. l a mm cc b 使使得得 2021-8-1 72 11 100. l a mmcc b 于于是是 由定理由定理3 3有有 1 1 1 0., l a cc b 其中其中 b1 ， 1 1 11 10 aaa mm bbb 因因此此，10 ab1 = ba 。 上式右端可以被上式右端可以被5 整除，

59、整除， 但是但是(a, 10) = 1，(b1 , 10) = 1， 所以所以5 ， 。 这就证明了不循环位数码个数不能再少了。这就证明了不循环位数码个数不能再少了。 2021-8-1 73 12 50. t b bb 定定理理纯纯循循环环小小数数可可以以化化为为分分数数 9.t其其中中，分分母母中中含含有有 个个 证明：证明： 1 2 , 999 t b bb 1 2 10t t b bb 1 2 (101) t t b bb 1 2 101 t t b bb 1 2 . 999 t b bb 0.23 23 99 0.36 36 99 4 11 0.023 23 999 4.4. 2021

60、-8-1 74 112 60. st aa b bb 定定理理混混循循环环小小数数可可以以化化为为分分数数 1121 , 999000 sts aa b bbaa 9,0.ts其其中中，分分母母中中含含有有 个个个个 证明：证明： 1212 100. s st a aab bb 12 12 101 t st b bb a aa 1212 (101) 101 t st t a aab bb 121212 101 sts t a aa b bba aa 121 212 (101)10 sts ts a aa b bba aa 11 21 . 999000 sts aa bbbaa 5.5. 202