初等数论§3同余

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

2、横线处漏写了一个 数字，你能以最快的办法补出吗？2022/10/142二、同余的定义注：下面的三个表示是等价的：2022/10/143三、同余的性质TH2设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).注：TH1、TH2是最简单、常用的性质。2022/10/1442022/10/145TH4 下面的结论成立： a b (mod m)，dm，d 0 a b (mod d)； a b (mod m)，k 0，kN ak bk (mod mk)； a b (mod m

3、i )，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);2022/10/146 a b (mod m)，dm，d 0 a b (mod d)； a b (mod m)，k 0，kN 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)；2022/10/147 ac bc (mod m)，(c, m) = 1 a b (mod m);

4、注：若没有条件(c, m) = 1，即为TH2的逆命题， 不能成立。反例：取m=6,c=2,a=20,b=23.2022/10/1482022/10/149四、一些整数的整除特征 (1) 3、9 的整除特征各位上的数字之和能被3（9）整除例1检查、435693能否被3（9）整除。2022/10/1410(2) 7、11、13 的整除特征注：一般地，求 被m除的余数时， 首先是求出正整数k，使得 10k 1或1 (mod m)， 2022/10/1411(2) 7、11、13 的整除特征特别地，由于 ，所以奇偶位差法 例2检查637693、能否被7（11，13）整除。由69363756，所以63

5、7693能被7整除，但不能被11，13整除， 当然也可以由6+3-7+6-9+3=2知637693不能被11整除； 由75-312+28952，所以能被13整除，但不能被7，11整除。 2022/10/14122022/10/1413 求出整数k，使ak 1 (mod m)； 求出正整数r，r 0是偶数，a1, a2, , am与b1, b2, , bm都是模m的完全剩余系， 则a1 b1, a2 b2, , am bm不是模m的完全剩余系。 证 由1, 2, , m与a1, a2, , am都是模m的完全剩余系， 如果a1 b1, a2 b2, , am bm是模m的完全剩余系， 不可能！2

6、022/10/1438例4 设miN（1 i n），则当xi通过模mi（1 i n） 的完全剩余系时，x = x1 m1x2 m1m2x3 m1m2mn 1xn通过模m1m2mn的完全剩余系。证明 对n施行归纳法。当n = 2时，由定理4知定理结论成立。假设定理结论当n = k时成立， 即当xi（2 i k 1）分别通过模mi的完全剩余系时，y = x2 m2x3 m2m3x4 m2mkxk 1通过模m2m3mk 1的完全剩余系。 2022/10/1439y = x2 m2x3 m2m3x4 m2mkxk 1通过模m2m3mk 1的完全剩余系。 由定理4，当x1通过模m1的完全剩余系， xi（

7、2 i k 1）通过模mi的完全剩余系时，x1 m1y = x1 m1(x2 m2x3 m2mkxk 1)= x1 m1x2 m1m2x3 m1m2mkxk 1通过模m1m2mk 1的完全剩余系。 即结论对于n = k 1也成立。 2022/10/1440三、与抽象代数的关系若将模m的剩余类作为元素，则 同余剩余类的相等，同余的运算元素剩余类的运算，剩余类的集合即是环。 特别地，当m为合数时，就有： 非零的剩余类的乘积可能为零的剩余类，即存在零因子的环。上述环中所有与模m互质的剩余类对乘法构成群；当m为质数时，上述的环又可以构成一个有限域。2022/10/14412022/10/14423.3

8、 简化剩余系与欧拉函数 一、基本概念定义1 设R是模m的一个剩余类，若有aR，使得(a, m)= 1，则称R是模m的一个简化剩余类。即与模m互质的剩余类。 注：若R是模的简化剩余类，则R中的数都与m互素。例如，模4的简化剩余类有两个：R1(4) = , 7 , 3, 1 , 5 , 9 , ，R3(4) = , 5 , 1 , 3 , 7 , 11 , 。2022/10/1443定义2 对于正整数k，令函数(k)的值等于模k的所有简化剩余类的个数，称(k)为Euler函数。容易验证：(2) = 1，(3) = 2，(4) = 2，(7) = 6。注：(m)就是在m的一个完全剩余系中与m互素的

9、整数的个数，且 定义3 对于正整数m，从模m的每个简化剩余类中 各取一个数xi，构成一个集合x1, x2, ,x(m)， 称为模m的一个简化剩余系（或简称为简化系）。 2022/10/1444注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合9, 5, 3, 1是模8的简化剩余系； 集合1, 3, 5, 7也是模8的简化剩余系. 集合1, 3, 5, 7称为最小非负简化剩余系。 2022/10/1445二、主要性质 定理1 整数集合A是模m的简化剩余系的充要条件是： A中含有(m)个整数； A中的任何两个整数对模m不同余； A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余

10、系中的部分元素构成的集合，故满足条件2； 由定义1易知满足条件3；由定义3易知满足条件1。2022/10/1446定理2 设a是整数，(a, m) = 1，B = x1, x2, , x(m) 是模m的简化剩余系，则集合 A = ax1, ax2, , ax(m) 也是模m的简化剩余系。证明 显然，集合A中有(m)个整数。 由于(a, m) = 1， 对于任意的xi（1 i (m)），xiB， 有(axi, m) = (xi, m) = 1。 故A中的每一个数都与m互素。 而且，A中的任何两个不同的整数对模m不同余。 因为，若有x , x B，使得 a x ax (mod m)，那么， x x

11、 (mod m)， 于是x = x 。 由以上结论及定理1可知集合A是模m的一个简化系。 2022/10/1447注：在定理2的条件下，若b是整数，集合ax1 b, ax2 b, , ax(m) b不一定是模m的简化剩余系。 例如，取m = 4，a = 1，b = 1， 以及模4的简化剩余系1, 3。但2，4不是模4的简化剩余系。2022/10/1448定理3 设m1, m2N，(m1, m2) = 1，又设分别是模m1与m2的简化剩余系， 则 A = m1y m2x；xX，yY 是模m1m2的简化剩余系。证明 由第二节定理3推论可知， 若以X 与Y 分别表示 模m1与m2的完全剩余系，使得X

12、 X ，Y Y ， 则A = m1y m2x；xX ，yY 是模m1m2的完全 剩余系。 因此只需证明A 中所有与m1m2互素的整数的集合R 即模m1m2的简化剩余系是集合A。 2022/10/1449若m1y m2xR，则(m1y m2x, m1m2) = 1， 所以(m1y m2x, m1) = 1， 于是 (m2x, m1) = 1，(x, m1) = 1，xX。同理可得到yY，因此m1y m2xA。 这说明R A。 另一方面，若m1y m2xA，则xX，yY， 即 (x, m1) = 1，(y, m2) = 1。由此及(m1, m2) = 1得到 (m2x m1y, m1) = (m2

13、x, m1) = 1(m2x m1y, m2) = (m1y, m2) = 1。因为m1与m2互素，所以(m2x m1y, m1m2) = 1， 于是m2x m1yR。因此A R。 从而A = R。 2022/10/1450推论 设m, nN，(m, n) = 1，则(mn) = (m)(n)。证 由定理3知，若x,y分别通过m , n的简化剩余系， 则my nx通过mn的简化剩余系， 即有 my nx通过(mn)个整数。 另一方面，xnx通过(m)个整数， ymy通过(n)个整数, 从而my nx通过(m) (n)个整数。故有 (mn) = (m)(n)。注：可以推广到多个两两互质数的情形。

14、2022/10/1451定理4 设n是正整数，p1, p2, , pk是它的全部素因数， 证 设n的标准分解式是 由定理3推论得到 对任意的素数p， (p)等于数列1, 2, , p中与p互素的整数的个数， 从而定理得证。2022/10/1452注：由定理4可知，(n) = 1的充要条件是n = 1或2。考虑有重素因子和没有重素因子的情形。 三、应用举例注意：有重素因子时，上述不等式中等号不成立！2022/10/1453例1 设整数n 2，证明： 即在数列1, 2, , n中，与n互素的整数之和是 证 设在1, 2, , n中与n互素的个数是(n)，a1, a2, , a(n)，(ai, n)

15、 = 1，1 ai n 1，1 i (n)，则 (n ai, n) = 1，1 n ai n 1，1 i (n)，因此，集合a1, a2, , a(n)故 a1 a2 a(n) = (n a1) (n a2) (n a(n)，从而，2(a1 a2 a(n) = n(n)，因此 a1 a2 a(n) 与集合n a1, n a2, , n a(n)是相同的，2022/10/1454例2 设nN，证明：1) 若n是奇数，则(4n) = 2(n)；的充要条件是n = 2k，kN；的充要条件是n = 2k3l，k, lN；4) 若6n，则(n) 5) 若n 1与n 1都是素数，n 4，则(n) 2022

16、/10/14551) 若n是奇数，则(4n) = 2(n)；(4n) = (22n)= (22)(n)= 2(n)TH42022/10/1456的充要条件是n = 2k，kN；若n = 2k， 若(n) = 设n = 2kn1， 由 (n) = (2kn1) = (2k)(n1) =2k 1(n1) 所以n1 = 1，即n = 2k；2022/10/1457的充要条件是n = 2k3l，k, lN；设 n = 2k3ln1， 所以n1 = 1，即n = 2k3l；若 n = 2k3l，则 (n) = (2k)(3l)2022/10/14584) 若6n，则(n) 设 n = 2k3ln1， 则

17、 (n) = (2k)(3l)(n1) 2022/10/14595) 若n 1与n 1都是素数，n 4，则(n) 因为n 4，且n 1与n 1都是奇素数， 所以n是偶数，且n 1 3.所以n 1与n 1都不等于3，所以3n，由结论4，也不能被3整除，因此6n。即可得到结论5。若6n，则(n) 2022/10/1460例3 证明：若m, nN，则(mn) = (m, n)(m, n)；证： 显然mn与m, n有相同的素因数， 设它们是pi（1 i k），则由此两式及mn = (m, n)m, n即可得证。2022/10/14613.4欧拉定理 费马定理及其对循环小数的应用 本节主要通过应用简化剩

18、余系的性质证明数论中的两个重要定理，欧拉定理和费马定理，并说明其在理论和解决实际问题中的应用。2022/10/1462一、两个基本定理定理1Euler 设 m是正整数，(a, m) = 1， 则 am) 1 (mod m).证明： 设x1, x2, , x(m)是模m的一个简化剩余系， 则ax1, ax2, , ax(m)也是模m的简化剩余系， 所以 ax1ax2ax(m) x1x2 x(m) (mod m)，即 a(m)x1x2x(m) x1x2, x(m) (mod m). 得 (x1x2x(m), m) = 1， 所以 a(m) 1 (mod m). 2022/10/1463定理2(Fe

19、rmat) 设p是素数， a p a (mod p)。 注：Fermat定理即是欧拉定理的推论。证： 由于p是素数， 若 (a, p) 1， 则由定理1得到 a p 1 1 (mod p) a p a (mod p) 若(a, p) 1，则pa， 所以 a p 0 a (mod p) am) 1 (mod m)2022/10/1464二、定理的应用举例例1 求313159被7除的余数。解：313159所以由欧拉定理得 am) 1 (mod m)从而 5159= (56)2653 53 (mod 7) 53 = 255 45 6 (mod 7)。即 313159被7除的余数为6。2022/10/

20、1465例2 设n是正整数，则5 1n 2n 3n 4n的充要条件是4n。证： 因为(5) = 4， 由定理1得 am) 1 (mod m)k4 1 (mod 5)，1 k 4。因此，记n = 4q r，0 r 3， 则 1n 2n 3n 4n 1r 2r 3r 4r 1r 2r (2)r (1)r (mod 5). 用 r = 0，1，2，3分别代入即可得出结论。2022/10/1466例3 设x1, x2, , x(m)是模m的简化剩余系， 则 (x1x2x(m)2 1 (mod m).证： 记P = x1x2x(m)， 则(P, m) = 1. 1 i (m)，则y1, y2, , y(

21、m)也是模m的简化剩余系， 再由Euler定理得证.am) 1 (mod m)2022/10/1467例4 设a，b，c，m是正整数，m 1，(b, m) = 1， 并且 b a 1 (mod m)，b c 1 (mod m)， 记d = (a, c)，则bd 1 (mod m)。证 利用辗转相除法可以求出整数x，y，使得ax cy = d， 显然xy 0，y 0， 则 1 b ax= b db cy= b d(b c) y b d (mod m)若x 0， 则 1 b cy= b db ax= b d(ba) x b d (mod m)。2022/10/1468例5 设n是正整数，记Fn =

22、 证： 容易验证，当n 4时Fn是素数， 由Fermat定理可知结论显然成立。a p a (mod p)。 当n 5时，有n 1 2n， 其中Q1与Q2是整数， 2022/10/1469补充说明我们已经知道，F5是合数，因此例5表明， Fermat定理的逆定理不成立。 设p是素数， a p a (mod p)。 即若有整数a，(a, n) = 1，使得 a n 1 1 (mod n)， 并不能保证n是素数。 例5 设n是正整数，记Fn = Fermat定理2022/10/1470例6 如果今天是星期一，再过101010天是星期几？即得：再过101010天是星期五。2022/10/1471三、在

23、分数与小数互化中的应用 有理数，即有限小数和无限循环小数，可以用分数来表示。利用欧拉定理可以解决分数、小数的转化问题。定义 如果对于一个无限小数 则称之为循环小数，并简记为 注：若找到的t是最小的，则称 为循环节；t称为循环节的长度；若最小的s0， 则称该小数为纯循环小数，否则为混循环小数。2022/10/1472定理3 有理数 能表示为纯循环小数 即：分母不含质因数2或5。2022/10/1473定理3 有理数 能表示为纯循环小数 (b, 10) = 1 由Euler定理可知，有正整数k，使得10k 1 (mod b)，0 k (b)，因此存在整数q使得 而且ak, , a1不能都等于0，也

24、不能都等于9。 = 0.akak 1a1akak 1a1 。2022/10/1474定理4 设a与b是正整数，0 a b，(a, b) = 1， 并且 b = 25b1，(b1, 10) = 1，b1 1， 此处与是不全为零的正整数， 其中不循环的位数码个数是 = max .则 可以表示成混循环小数，证明：不妨假设 = ， 其中0 a1 b1，0 M 10， 且(a1, b1) = (2 a Mb1, b1) = (2 a, b1) = (a, b1) = 1。因此，由定理3， 可以表示成纯循环小数： 2022/10/1475M = m110 1 m210 2 m（0 mi 9，1 i ）， 下面说明，上式中的是最小的不循环位数码的个数。 若不然，设又有正整数， 2022/10/1476由定理3有 其中b1 ， 10ab1 = ba。 上式右端可以被5 整除，