第四章--同余方程

第四章同余方程•本章主要介绍同余方程的基础知识,并介绍几类特殊的同余方程的解法.第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。在本章中，总假定m是正整数。定义1设f(x)=anxna1xa0是整系数多项式，称f(x)0(modm)(1)是关于未知数x的模m的同余方程，简称为模m的同余方程。若an0(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)的解.证明留做习题。下面，我们来研究一次同余方程的解。第一节同余方程的基本概念定理2设a，b是整数,a0(modm).则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d=(a,m)个解。证明显然，同余方程(2)等价于不定方程axmy=b，(3)第一节同余方程的基本概念因此，第一个结论可由第四章第一节定理1得出。若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是)4(.Z),(),(00ttmaayytmamxx第一节同余方程的基本概念由式(4)所确定的x都满足方程(2)。记d=(a,m)，以及t=dqr，qZ，r=0,1,2,,d1，则x=x0qm(modm)，0rd1。容易验证，当r=0,1,2,,d1时，相应的解dmdxdmxdmxx)1(20000，，，，第一节同余方程的基本概念对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。dmdxdmxdmxx)1(20000，，，，第一节同余方程的基本概念例1设(a,m)=1,又设存在整数y,使得abym，则是方程(2)的解。证明直接验算，有axbymb(modm)。)(modmaymbx第一节同余方程的基本概念注:例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=114(mod161)。3161220第一节同余方程的基本概念例3设a0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程a1xb(modm)(7)等价于同余方程(2)。解设x是(2)的解，则由m=a1得到][am][ama][][])[(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)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解同余方程组.(8)解将(8)的前一式乘以2后一式乘以3再相减得到19y4(mod7)，5y4(mod7)，y2(mod7)。)7(mod232)7(mod153yxyx第一节同余方程的基本概念再代入(8)的前一式得到3x101(mod7)，x4(mod7)。即同余方程组(8)的解是:x4，y2(mod7).第一节同余方程的基本概念例8设a1，a2是整数，m1，m2是正整数，证明：同余方程组(9)有解的充要条件是a1a2(mod(m1,m2))。(10)若有解，则对模[m1,m2]是唯一的，即若x1与x2都是同余方程组(9)的解，则x1x2(mod[m1,m2])。(11))(mod)(mod2211maxmax第一节同余方程的基本概念证明必要性是显然的。下面证明充分性。若式(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，证明：(modp)。是同余方程axb(modp)的解。!)1()2)(1()1(1aapppbxa习题一5.证明：同余方程a1x1a2x2anxnb(modm)有解的充要条件是(a1,a2,,an,m)=db。若有解，则恰有dmn1个解，modm。6.解同余方程：2x7y5(mod12)。