高中数学竞赛讲座---同余理论及其应用(一)

同余理论及其应用基础知识一.定义定义1.设m为正整数，整数a和b之差可被m整除时，称为a和b关于模m同余，记作).(modmba定义2.被正整数m除余数相等的所有整数的集合称为模m的剩余类。模m的剩余类共有m个。定义3.在模m的m个剩余类中各取一个整数作为代表，这些代表的集合称为模m的完全剩余系。定义4.绝对值不超过]2[m的模m的完全剩余系称为模m的绝对最小剩余系。定义5.当模m的某一剩余类的所有整数均与m互素时，则称此剩余类是模m的简化类。模m的简化类共有)(m个。定义6.在模m的)(m个简化类中各取一个整数作为代表，这些代表的集合称为模m的简化剩余系。定义7.欧拉函数：设n为正整数，从1到n的整数中与n互素的整数的个数用)(n表示，称)(n为欧拉函数。当1212ssnppp时，有)11)...(11)(11()(21spppnn二.定理定理1.).(modmba的必要充分条件是a和b被m除的余数相等。定理2.I.);(modmaaII.若),(modmba则);(modmabIII.若),(modmba),(modmcb则).(modmca定理3.若)(mod11mba，)(mod22mba，则I.)(mod2121mbbaa；II.)(mod2121mbbaa2b)(mod2121mbbaa；III.)(mod2121mbbaa.定理4.如果),...,2,1)((modnimbaii，则I.)(mod......2121mbbbaaann；II.).(mod......2121mbbbaaann推论.如果).(modmban为任意正整数，则).(modmbann定理5.如果).(modmcbca则).),((modmcmba推论.如果1),(mc，).(modmcbca则).(modmba定理6.如果).(modmba则).,(),(mbma定理7.a和b属于模m的同一剩余类的充要条件是).(modmba定理8.m个整数maaa,...,,21是模m的完全剩余系的充要条件是maaa,...,,21关于模m两两互不同余。定理9.设f是正整数m的正因数。在模f的属于c的剩余类中取整数ffmcfcc)1(,...,,，则它们是模m的fm个剩余类。定理10.与m互素的)(m个整数是模m的简化剩余系的充要条件是这)(m个整数关于模m两两互不同余。又设raaa,...,,21是模m的简化剩余系，如果1),(mc，则rcacaca,...,,21也是模m的简化剩余系。定理11.欧拉定理：如果1),(ma，则)(mod1)(mam定理12.费马小定理：如果1),(pa，则)(mod11pap，其中p为素数。它也常写作：)(modpaap，这里不要求pa,互素。定理13.裴蜀定理：设dba,,是整数，则dba),(的充要条件是bdad,，存在整数vu,使得dvbua推论1.1),(ba的充要条件是，存在整数vu,使得1vbua推论2.ba,均为正整数，1),(ba的充要条件是，存在正整数vu,使得1vbua典型例题：一.同余与完全平方数例1.设素数p满足)8(mod7p，证明p必不能表作三个平方数之和。分析我们利用平方数模8的性质进行处理。证明：设存在三个整数cba,,使.222cbap其中cba,,或为偶数，或为奇数。因此下式),8(mod02a),8(mod02a),8(mod12a),8(mod42a必居其一。事实上，当a是奇数14ma或34ma时，有),8(mod12a当a是偶数ma4或24ma时，有),8(mod02a或),8(mod42a同样b和c也必居下式之一：),8(mod02b),8(mod12b),8(mod42b),8(mod02c),8(mod12c),8(mod42c),8(mod42c将cba,,所有可能满足的式子任意组合，只能得到),8(mod6,5,4,3,2,1,0222cba而得不到).8(mod7222cba因此形如)8(mod7p的素数不能表作三个平方数之和。评注选择合适的模是处理平方数问题的技巧之一。例2.（2003年越南数学奥林匹克）求最大的正整数n，使得方程组2222222212)(...)(...)2()1(nkynxykxyxyx2222222212)(...)(...)2()1(nkynxykxyxyx有整数解),...,,,(21nyyyx分析我们利用平方数的性质处理问题。解：当3n时，易知所给的方程组有整数解)0,1,0,2(321yyyx，当4n时，72523224323222221xyyxyyxyy，则4321,,,yyyy奇偶交替出现，则2)(2232122yyy且2)(2242223yyy若31,yy为奇数，则)8(mod0222y)8(mod422321yy矛盾。同理：若31,yy为偶数，则42,yy为奇数。后面式子又矛盾，所以4n无解。显然4n无解。评注选择适当的模，利用平方数性质是解决平方问题的技巧之一。二.费马小定理与欧拉定理例3.证明nn132730分析由原式联想到费马小定理。证明：1375322730，由费马小定理,)13(mod13nn,)7(mod7nn,)5(mod5nn,)3(mod3nn,)2(mod2nn,而10)(()1)(()1)((24681034856713nnnnnnnnnnnnnnnn10)(()1)(()1)((24681034856713nnnnnnnnnnnnnnnn并且nnnn132|，由此可知：13,7,5,3,2,|13knnk，所以原命题成立。评注费马小定理是处理此类整除问题的重要工具。例4.（2004年加拿大）p为奇素数，证明：).(mod2)1(21112pppkpkp解：由于1p为偶数，则1112pkpk))((1221112ppkpkpk，由二项式定理：12221123222121212...)(pppppppkpkCkpCpkp12221123222121212...)(pppppppkpkCkpCpkp右侧除最后两项外均被2p整除。因此1212)(ppkpk)(mod)12(222122211212pkppkpkCkppppp由于pk1由费马小定理)(mod11pkp)(mod11)12()12(222ppkpp，1)12(22mpkpp，则)(mod)12(2222pppmpkppp)(mod)12(2222pppmpkppp所以1112pkpk211)(pkp))(mod)(21(2ppp).(mod2)1(2222pppppp).(mod2)1(2222pppppp所以，原结论成立。评注二项式定理也是处理数论问题的重要工具。三.同余与不定方程例5.（2004年韩国数学竞赛）证明：方程xxy423没有正整数解。分析我们选择适当的模对x进行分类处理问题。证明：（1）当)(13Naax时，)3(mod24xx而方程左边能被3整除，此时无解。（2）当*)(3Naax时，)1)(1(24xxxxxx223)139)(13(3yaaaa，22)139)(13(yaaaa22)139)(13(yaaaa，而1)13,(aa，1)139,(2aaa，1)139,13(2aaa，,a139,132aaa139,132aaa均为完全平方数。而222)3(139)13(aaaa所以此时无解。（3）当*)(13Naax时，)1)(1(24xxxxxx223)133)(13(9yaaaa，.|3|32yy令*)(3Nccy则223)133)(13(caaaa，.|3a令*)(3Nbba，则22)1927)(19(cbbbb与（2）类似，1927,19,2bbbb均为完全平方数。设*),(1922Nmtmbtb则2219mt，即1)3)(3(mtmt1)3)(3(mtmt，所以1313mtmt方程无整数解。综上所述，原方程无整数解。评注方程右边可以进行因式分解，而左边系数为3，因而选择模3对x进行分类处理问题。例6.（2004年巴尔干数学奥林匹克）yx,是质数，解：.192xyyxxy分析我们要充分利用yx,是质数的条件。解：若yx,则192xy无整数解；若yx，则.192xyxyyx由于yx,是质数，由费马小定理)(modyxxy，).(mod2yxxyxyyx即)(mod19yx，xy19|①，再由费马小定理)(modxyyx).(mod2xyxyxyyx即)(mod19xy1.若19y则19|yx②；2.由①知：xy19；由②知：19yx即19xy，19xy，又y为质数。而x为奇质数，y为偶数，,2x21y与y为质数矛盾。所以此时无解；3.若19y，由xy19|知xy|xy，无解；4.若19y，则当17y时：.191717217xxx易知：17x时，01717xx，无解，13x，当3,5,7,11,13x时，两边模4，知无解；2x时，左边小于0，无解；当13y时：两边模4，3,5,7,11x2x时，左边小于0。当11y时：同理3,5,7x无解；2x时，左边小于0。当7y时：3,5x无解；2x时，满足条件。7,2yx为一组解。当5y时，3x无解；.195525xxx2x时，无整数解；当3y时，2x1923332，3,2yx为一组解。综上，7,2yx；3,2yx为解。评注在处理有关质数的幂的问题中，费马小定理常发挥重要作用。四.同余定理例7.设p是奇素数，a是连续数列2,3,...,4,3,2pp①中的任一数，则数列apapapaaa)1(,)2(,)3(,...,3,2,apapapaaa)1(,)2(,)3(,...,3,2,②中必有一个且只有一个数关于模p与1同余，设此数为ia，则i为①中一数且与a相异。分析利用p为素数证明：因为①中各数均小于p，p为素数，所以①中每一个数均与p互素。由于a是①中某数，故.1),(pa因此，由定理11，数列apapapaaa)1(,)2(,)3(,...,3,2,与数列①代表同一类数，也就是说，数列②表示模p的除p的倍数外，其余的一切类数。因此②中必有一数)11(piia，使)(mod1pia。这个i决不能等于a，事实上，如果ai，则有)(mod12pa，从而就有)(mod0)1)(1(paa)(mod0)1)(1(paa。由于p是素数，且2|p，故)(mod01pa或)(mod01pa，两者必居其一。但11pa，即papa12,10。所以不可能有)(mod01pa及)(mod01pa。故ai另外可以证明.1pi否则如果.1pi就有).(mod)1()1(papapapapia但11pa，即11pap，所以21)(1pap,因此不可