初等数论-第五章--同余方程

107第五章同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。在本章中，总假定m是正整数。定义1设f(x)=anxna1xa0是整系数多项式，称f(x)0(modm)(1)是关于未知数x的模m的同余方程，简称为模m的同余方程。若an0(modm)，则称为n次同余方程。定义2设x0是整数，当x=x0时式(1)成立，则称x0是同余方程(1)的解。凡对于模m同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。由定义2，同余方程(1)的解数不超过m。定理1下面的结论成立：(ⅰ)设b(x)是整系数多项式，则同余方程(1)与f(x)b(x)b(x)(modm)等价；(ⅱ)设b是整数，(b,m)=1，则同余方程(1)与bf(x)0(modm)等价；(ⅲ)设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)0(modm)或h(x)0(modm)108的解。证明留做习题。下面，我们来研究一次同余方程的解。定理2设a，b是整数，a0(modm)。则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d=(a,m)个解。证明显然，同余方程(2)等价于不定方程axmy=b，(3)因此，第一个结论可由第四章第一节定理1得出。若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是tmaayytmamxx),(),(00，tZ。(4)由式(4)所确定的x都满足方程(2)。记d=(a,m)，以及t=dqr，qZ，r=0,1,2,,d1，则x=x0qmrdmxrdm0(modm)，0rd1。容易验证，当r=0,1,2,,d1时，相应的解dmdxdmxdmxx)1(20000，，，，对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。例1设(a,m)=1，又设存在整数y，使得abym，则xaymb(modm)是方程(2)的解。解直接验算，有axbymb(modm)。109注：例1说明，求方程(2)的解可以转化为求方程myb(moda)(5)的解，这有两个便利之处：第一，将一个对于大模m的同余方程转化为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设mr(moda)，ra，则又可继续转化成一个对于更小的模r的同余方程。例2解同余方程325x20(mod161)(6)解同余方程(6)即是3x20(mod161)。解同余方程161y20(mod3)，2y1(mod3)，得到y2(mod3)，因此方程(6)的解是x3161220=114(mod161)。例3设a0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程a1xb][am(modm)(7)等价于同余方程(2)。解设x是(2)的解，则由m=][amaa1得到][][])[(1ambamaxxamamxa(modm)，即x是同余方程(7)的解。但是由假设条件可知同余方程(2)与(7)都有且只有一个解。所以这两个同余方程等价。注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。例4解同余方程6x7(mod23)。解由例3，依次得到6x7(mod23)5x732(mod23)3x248(mod23)1102x8(7)10(mod23)x5(mod23)。例5设(a,m)=1，并且有整数0使得a1(modm)，则同余方程(2)的解是xba1(modm)。解直接验证即可。注：由例5及Euler定理可知，若(a,m)=1，则xba(m)1(modm)总是同余方程(2)的解。例6解同余方程81x324x25x230(mod7)。解原同余方程即是3x33x22x20(mod7)。用x=0，1，2，3逐个代入验证，得到它的解是x11，x22，x32(mod7)。注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。例7解同余方程组)7(mod232)7(mod153yxyx。(8)解将(8)的前一式乘以2后一式乘以3再相减得到19y4(mod7)，5y4(mod7)，y2(mod7)。再代入(8)的前一式得到3x101(mod7)，x4(mod7)。即同余方程组(8)的解是x4，y2(mod7)。例8设a1，a2是整数，m1，m2是正整数，证明：同余方程组)(mod)(mod2211maxmax(9)111有解的充要条件是a1a2(mod(m1,m2))。(10)若有解，则对模[m1,m2]是唯一的，即若x1与x2都是同余方程组(9)的解，则x1x2(mod[m1,m2])。(11)解必要性是显然的。下面证明充分性。若式(10)成立，由定理2，同余方程m2ya1a2(modm1)有解yy0(modm1)，记x0=a2m2y0，则x0a2(modm2)并且x0=a2m2y0a2a1a2a1(modm1)，因此x0是同余方程组的解。若x1与x2都是方程组(9)的解，则x1x2(modm1)，x1x2(modm2)，由同余的基本性质，得到式(11)。习题一1.证明定理1。2.解同余方程：(ⅰ)31x5(mod17)；(ⅱ)3215x160(mod235)。3.解同余方程组：)47(mod10)47(mod3853yxyx。4.设p是素数，0ap，证明：!)1()2)(1()1(1aapppbxa(modp)。是同余方程axb(modp)的解。5.证明：同余方程a1x1a2x2anxnb(modm)有解的充要条件是112(a1,a2,,an,m)=db。若有解，则恰有dmn1个解，modm。6.解同余方程：2x7y5(mod12)。第二节孙子定理本节要讨论同余方程组)(mod)(mod)(mod2211kkmaxmaxmax。(1)在第一节的例题中，我们已讨论了k=2的情形。下面考察一般情形。定理1(孙子定理)设m1,m2,,mk是正整数，(mi,mj)=1，1i,jk，ij。(2)记m=m1m2mk，Mi=imm，1ik，则存在整数Mi（1ik），使得MiMi1(modmi)，(3)MiMi0(modmi)，1jk，ij，(4)并且ikiiiMMax10(modm)(5)是同余方程组(1)对模m的唯一解，即若有x使方程组(1)成立，则xx0(modm)。(6)证明由式(2)，有(Mi,mi)=1，因此利用辗转相除法可以求出Mi与yi，使得MiMiyimi=1，即Mi满足式(3)和式(4)。由式(3)与式(4)，对于1ik，有113x0aiMiMiai(modmi)，1ik。若x也使式(1)成立，则xx0(modmi)，1ik，因此xx0(mod[m1,m2,,mk])。但是，由式(2)可知[m1,m2,,mk]=m，这就证明了式(6)。证毕。定理2在定理1的条件下，若式(1)中的a1,a2,,ak分别通过模m1,m2,,mk的完全剩余系，则式(5)中的x0通过模m1m2mk的完全剩余系。证明这是第二章第二节习题6的特例。证毕。定理3同余方程组(1)有解的充要条件是aiaj(mod(mi,mj))，1i,jn。(7)证明必要性是显然的。下面证明充分性。当n=2时，由第一节例8可知充分性成立。假设充分性当n=k时成立。假设式(7)当n=k1时成立。我们来考虑同余方程组xai(modmi)，1ik1。由第一节例8，存在bk，使得xbk(mod[mk，mk+1])满足同余方程组xak(modmk)，xak+1(modmk+1)。在同余方程组]),[(mod)(mod)(mod11111kkkkmmbxmaxmax中，由式(7)有aiaj(mod(mi,mj))，1i,jk1，因此，若能证明aibk(mod(mi,[mk,mk+1]))，1ik1。(8)则由归纳假设就可以证明充分性。由bk的定义，有akbk(modmk)，ak+1bk(modmk+1)(9)114而且，由于假设式(7)当n=k1时成立，所以，对于1ik1有aiak(mod(mi,mk))，aiak+1(mod(mi,mk+1))，由此及式(9)得到，对于1ik1，有aibk(mod(mi,mk))，aibk(mod(mi,mk+1))。因此aibk(mod[(mi,mk),(mi,mk+1)])。由上式及第一章第六节例2，就得到式(8)。证毕。定理4设m=m1m2mk，其中m1,m2,,mk是两两互素的正整数，f(x)是整系数多项式，以T与Ti（1ik）分别表示同余方程f(x)0(modm)(10)与f(x)0(modmi)(11)的解的个数，则T=T1T2…Tk。证明由第二章第一节定理5可知，同余方程(10)等价于同余方程组f(x)0(modmi)，1ik。(12)对于每i（1ik），设同余方程(11)的全部解是)()(2)(1,,,iTiiixxxx(modmi)，(13)则同余方程组(12)等价于下面的T1T2…Tk个方程组：)(mod)(mod)(mod)(2)2(1)1(21kkjjjmxxmxxmxxk，(14)其中)(ijix通过式(13)中的数值，即通过同余方程(11)的全部解。由孙子定理，对于选定的每一组{)()2()1(,,,21kjjjkxxx}，同余方程组(14)对模m有唯一解，而且，由定理2，当每个)(ijix通过(13)式中的值时，所得到的T1T2…Tk个同余方程组(14)的解对于模m都是两两不同余的。证毕。115由定理4及算术基本定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。例1求整数n，它被3，5，7除的余数分别是1，2，3。解n是同余方程组n1(mod3)，n2(mod5)，n3(mod7)的解。在孙子定理中，取m1=3，m2=5，m3=7，m=357=105，M1=35，M2=21，M3=15，M1=1，M2=1，M3=1，则n135(1)2211315152(mod105)，因此所求的整数n=52+105t，tZ。例2解同余方程5x26x490(mod60)。(15)解因为60=345，所以，同余方程(15)等价于同余方程组5x26x490(mod3)(16)5x26x490(mod4)(17)5x26x490(mod5)。(18)分别解同余方程(16)，(17)，(18)得到解x1(1)1，x2(1)1(mod3)，x1(2)1，x2(2)1(mod4)，x1(3)1(mod5)，这样，同余方程(15)的解x可由下面的方程组决定：xa1(mod3)，xa2(mod4)，xa3(mod5)，其中a1=1或1，a2=1或1，a3=1。利用孙子定理，取m1=3，m2=4，m3=5，m=60，M1=20，M2=15，M3=12，M1=2，M2=1，M3