同余的性质与应用

..Word文档Word文档同余的性质及应用1引言数论的一些基础内容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的基础，其中同余理论有时整数论的重要组成部分，所以学好同余理论是非常重要的.在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一.我国古代孙子算经里已经提出了同余式xb(modm),xb(modm),…,xb(modm) 1 1 2 2 k k这种形式的问题，并且很好地解决了它.宋代大数学家秦九韶在他的《数学九章》中提出了同余式xM1(modm),i1,2,...k,m是k个两两互质的正整数， i i immm...m,mmM的一般解法. 12 k i i同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级数问题中的质数分布问题，an2bnc形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.2同余的概念给定一个正整数m，把它叫做模，如果用m去除任意两个整数a与b所得的余数相同，我们就说对模m同余，记作ab(modm),如果余数不同，就说对模m不同余.由定义得出同余三条性质：aa(modm)；ab(modm),则ba(modm)；ab(modm),bc(modm),则ac(modm).定义也可描述为:整数a,b对模m同余的充分必要条件是mab,即abmt,t是整数.3同余的八条基本性质由同余的定义和整数的性质得出[1]：若ab(modm),cd(modm),则acbd(modm)若abc(modm),则acb(modm)若ab(modm),cd(modm),则acbd(modm)特别地,若ab(modm),则akbk(modm)若A B (modm),xy(modm),i0,1,...,n ... ... i i 1 k 1 k则A x1...xkB y1...yk(modm) ...1 k ...1 k 1 k 1 k若aad,bbd,(d,m)1,ab(modm),则ab(modm)1 1 1若ab(modm),k0,则akbk(modm)； ab m若ab(modm),d是a,b及m任一正公因数,则(mod) dd d若ab(modm),i1,2,...k,则ab(mod[m,m,...,m]) i 1 2 k其中[m,m,...,m]是m,m,...,m,k个数最小公倍数2 k 1 2 k若ab(modm),dm,d0,则ab(modd)ab(modm),(a,m)(b,m),若d能整除m及a,b两数之一,则d必整除a,b另一个.4同余性质在算术里的应用4.1检查因数的一些方法例1一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除.证:按照通常方法,把任意整数a写成十进位数形式,即aan10nan110n1...a0,0ai10.因101(mod3),所以由同余基本性质,即3a当且仅当3a；i同法可得9a当且仅当9a，i0,1,...,n.i例2设正整数aa1000na1000n1...a，0a1000，则7（或11或13） n n1 0 i整除a的充要条件是7（或11或13）整除(aa...)(aa...)(1)ia， 0 2 1 3 ii0,1,...,n.证：1000与-1对模7（或11或13）同余，根据同余性质知，a与(1)ia对模7（或11或13）同余i即7（或11或13）整除a当且仅当7（或11或13）整除(1)ia，i0,1,...,n.i例3a=5874192，则a587419236，i0,1,...,n能被3，9整i除，当且仅当a能被3，9整除解：由例1证法可知，该结论正确.例4a=435693，则a43569330，i0,1,...,n能被3整除，但a i i不能被9整除当且仅当3是a的因数，9不是a的因数.解：由例1的证法可得.例5a=637693，则a6371000693，a69363756，i0,1,...,n能被i7整除而不能被11或13整除当且仅当7是a的因数但11，13不是a的因数.解：由例2的证法可知，该结论正确.例6a=75312289，a75100023121000289a2893127552，ii0,1,...,n能被13整除，而不能被7，11整除当且仅当13是a的因数，而7与11不是a的因数.解：由例2的证法可知.例7应用检查因数的方法求出下列各数标准分解式①1535625②1158066解：①15356251106510531045103610221015，a153562527，92791535625，i15356251100025351000625，(aa)a625153591，由例2得1391，791， 0 2 171535625，131535625，1535625又51535625，951374095，375，40953755375，75，2575，515356253554137.②1158066110611055104810361016，a11586627，92791158066，i1158066110002158100066，(aa)a66115891，由例2得791，1391 0 2 171158066，131158066，1158066又21158066，971321638，707，7707，16381158066297213101.4.2弃九法（验证整数计算结果的方法）我们由普通乘法的运算方法求出整数a，b的乘积是P，并令aa10na10n1...a，0a10 n n1 0 ibb10nb10n1...b，0b10， n n1 0 iPc10nc10n1...c，0c10，n n1 0 i如果(a)(b)与c对模9不同余，那么所求得的乘积是错误的.i j k特别的，在实际验算中，若a，b，c中有9出现，则可去掉（因90(mod9)）. i j k例1a=28997，b=39495，按普通计算方法算得a，b乘积是P=1145236515，按照上述弃九法a8(mod9)，b3(mod9)，P5(mod9).但83与5对模9不同余，所以计算有误.例2若a=28997，b=39495，P=1145235615，那么Pab？解：按照上述弃九法，a8(mod9)，b3(mod9)，P6(mod9).虽然83与6对模9同余，但是由通常乘法计算得到ab1145236515，故Pab不成立.注：当使用弃九法时，得出的结果虽然是(a)(b)c(mod9)也还不能完全肯 i j k定原计算是正确的.4.3同余性质的其他应用例1求7除4750的余数.解：由47(2)12(mod7)，472(2)24(mod7)，475(2)51(mod7)，4750(475)16472144(mod7)，即4750除以7余数为4.例2试证：形如8k7(kN)的整数不能表为三个平方数之和.证：假定N8k7a2b2c2(a,b,cZ)，则a2b2c27(mod8)，但这不可能.因为对模8而论.每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数.而020(mod8)，121(mod8)，224(mod8)，321(mod8)，420(mod8)，521(mod8)，624(mod8)，721(mod8).因此，任一整数平方对模8必与0，1，4三个数之一同余，而从｛0，1，4｝中任取三个数，其和都不可能与7对模8同余，所以对于任何整数a，b，c都有a2b2c2与7对模8不同余.即形如8k7(kN)的整数不能表为三个平方数之和.例3试证：53533333能被10整除.证：由已知条件有533(mod10)，532329(mod10)，535357(mod10)，534341(mod10)，5353(534)1553(34)153133(mod10)又333(mod10)，332329(mod10)，335357(mod10)，334341(mod10)，3333(334)833(34)83133(mod10)53533333(mod10)，即10(53533333)也就是说，53533333能被10整除.例4设a,b,cN且6(abc)，求证：6(a3b3c3)证：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5030(mod6)，131(mod6)，232(mod6)，333(mod6)，434(mod6)，535(mod6)，即对任何整数k，k3k(mod6)a3a(mod6)，b3b(mod6)，c3c(mod6)(a3b3c3)(abc)(mod6)又(abc)0(mod6)(a3b3c3)0(mod6)故6(a3b3c3)例5若(5,n)1，证明n5n能被30整除.证：设nN，nk(mod6)则k0,1,2,3,4,5由050(mod6)，151(mod6)，252(mod6)，353(mod6)，454(mod6)，555(mod6)，k5k(mod6)即n5k5kn(mod6)，6(n5n)同理可知5(n5n)又(5,6)130(n5n)故n5n能被30整除.5同余性质在数论中的应用：求简单同余式的解5.1一次同余式、一次同余式解的概念在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：若用f(x)表示多项式axnaxn1...a，其中a是 n n1 0 i整数，又设m是一个正整数，则f(x)0(modm)叫做模m的同余式.若a与0n对m不同余，则n叫做f(x)0(modm)的次数.定义：若a是使f(a)0(modm)成立的一个整数，则xa(modm)叫做同余式f(x)0(modm)的一个解.定理一次同余式axb(modm),a与0对模m不同余,它有解充要条件是(a,m)b.[3]5.2孙子定理解一次同余式组引例今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?解:设x是所求物数，则依题意有，x2(mod3),x3(mod5),x2(mod7)孙子算经里介绍用下列方法求解除数除数余数最小公倍数衍数乘率各总答数最小答数32357=1055723522140+63+30=233233-2105=23537312113723511512由表格知，所求物数是23.孙子定理：设m,m,…,m是k个两两互质的正整数，mmm...m，mmM，12k 12kiii1,2,...k,则同余式组xb(modm),xb(modm),..., 1 1 2 2xb(modm)的解是xM1MbM1Mb...M1Mb(modm),其kk111222kkk中M1M1(modm),i1,2,...,k[4] i i i用表格形式概括如下除数除数余数最小公倍数衍数乘率各总答数1m1b12...kMmmm1M11M1111MMb11(mod)kiiiixMMbm2m2b2M12M1222MMbkmkbkM1kM1kkkMMb例1解同余式组xb(mod5),xb(mod6)，xb(mod7)，xb(mod11). 1 2 3 4解：此时m567112310,M6711462,M5711385， 1 2M5611330,M567210. 3 4解M1M1(modm),i1,2,3,4得M13,M11,M11,M11iii1234即x1386b385b330b210b(mod2310). 1 2 3 4例2韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？解:由题意，有x1(mod5)，x5(mod6)，x4(mod7)，x10(mod11)x3462385533042101067312111(mod2310).5.3简单高次同余式组f(x)0(modm),i1,2,...,k及f(x)0(modp),p为i质数，0的解数及解法的初步讨论定理1若m,m,…,m是k个两两互质的正整数,mmm...m,则同余式 1 2 k 12 kf(x)0(modm)与同余式组f(x)0(modm),i1,2,...,k等价.i若用T表示f(x)0(modm),i1,2,...k,对模m的解数,T表示 i i if(x)0(modm)对模m的解数，则TTT...T.[5] 12 k例1解同余式f(x)0(mod35)，f(x)x42x38x9.解:由定理1知f(x)0(mod35)与同余式f(x)0(mod5),f(x)0(mod7)等价.同余式f(x)0(mod5)有两个解，即x1,4(mod5)同余式f(x)0(mod7)有三个解，即x3,5,6(mod7)即f(x)0(mod35)有六个解，即xb(mod5),xb(mod7) 1 2由孙子定理有，x21b15b(mod35) 1 2即得f(x)0(mod35)的解为x31,26,6,24,19,34(mod35).定理2设xx(modp),即xxpt,t0,1,2,...是f(x)0(mod 1 1 1 1p)的一解，并且p不整除f1(x),(f1(x)是f(x)的导函数),则xxpt刚好给出 1 1f(x)0(modp)，p为质数，0的一解xxpt,t0,1,2,...,即xx(modp),其中xx(modp).[6]1例2解同余式6x327x217x200(mod30).解:由定理1知f(x)0(mod30)与f(x)0(mod2),f(x)0(mod3),f(x)0(mod5)等价.显然，f(x)0(mod2)有两解x0,1(mod2)f(x)0(mod3)有一解x2(mod3)f(x)0(mod5)有三解x0,1,2(mod5)同余式f(x)0(mod30)有六个解即xb(mod2),xb(mod3),xb(mod5),b0,1；b2；b0,1,2 1 2 3 1 2 3由孙子定理得x15b10b6b(mod30),以b,b,b值分别代入，得 1 2 3 1 2 3f(x)0(mod30)全部解为x20,2,26,5,11,17(mod30).例3解同余式f(x)0(mod27)，f(x)x47x4.解:f(x)0(mod3)有一解x1(mod3)，并且3不整除f1(1)，以x13t代入f(x)0(mod9)得f(1)3tf1(1)0(mod9) 1 1但f(1)3(mod9)，f1(1)2(mod9)即33t20(mod9)即2t10(mod3) 1 1因此t13t而x13(13t)49t是f(x)0(mod9)的一解；2 2 2以x49t代入f(x)0(mod27)即f(4)9tf1(4)0(mod27),2189t200(mod27)即2t20(mod3),t23t2 2 3即x49(23t)2227t为所求的解.35.4简单二次同余式x2a(modp),0,(a,p)1解的判断二次同余式一般形式为ax2bxc0(modm),a与0对模m不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如x2a(modp),0有解与否问题.先讨论单质数模同余式x2a(modp),(a,p)1有解与否问题若它有解，则a叫做模p的平方剩余，若它无解，则a叫做模p的平方非剩余.定理1若(a,p)1,则a是模p的平方剩余的充要条件是a1(modp)且有两解；而a是模p的平方非剩余充要条件是a1(modp).[7]a()是勒让得符号，它是一个对于给定单质数p定义在一切整数a上的函数，它pa的值规定如下:当()1时，a是模p的平方剩余；pa当()1时，a是模p的平方非剩余；pa当（）=0时，pa.[8]p讨论质数模同余式x2a(modp),0,(a,p)1有解与否问题a定理2x2a(modp),0,(a,p)1有解的充要条件是()1，并且在有解情p况下，解数是2.[9]讨论合数模同余式x2a(mod2),0,(2,a)1有解与否问题定理3设1,当2,a1(mod4)时，x2a(mod2),0,(2,a)1有解，且解数是2；当3，a1(mod8)时，上式有解，解数是4.[10]例解x257(mod64).解:因571(mod8)故有4个解.把x写成x(14t)代入原同余式,得到(14t)257(mod16),由此得 3 3t1(mod2),故x[14(12t)](58t)是适合x257(mod16)的一切 3 4 4整数，再代入原同余式得到(58t)257(mod32),由此得4t0(mod2),故x(582t)(516t)是适合x257(mod32)的一切 4 5 5整数,再代入原同余式得到(516t)257(mod64),由此得5t1(mod2),故x[516(12t)](2132t)是适合x257(mod64)的 5 6 6一切整数，因此x21,53,21,53(mod64)是所求四个解.6结论本文从同余概念及其基本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应