第四章--同余方程

第四章同余方程,本章主要介绍同余方程的基础知识,并介绍几类特殊的同余方程的解法.,第一节同余方程的基本概念,本节要介绍同余方程的基本概念及一次同余方程。在本章中，总假定m是正整数。,定义1设f(x)=anxna1xa0是整系数多项式，称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).则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d=(a,m)个解。,证明显然，同余方程(2)等价于不定方程axmy=b，(3),第一节同余方程的基本概念,因此，第一个结论可由第四章第一节定理1得出。,若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是,第一节同余方程的基本概念,由式(4)所确定的x都满足方程(2)。记d=(a,m)，以及t=dqr，qZ，r=0,1,2,d1，则x=x0qm(modm)，0rd1。,容易验证，当r=0,1,2,d1时，相应的解,第一节同余方程的基本概念,对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。,在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。,第一节同余方程的基本概念,例1设(a,m)=1,又设存在整数y,使得abym，则是方程(2)的解。,证明直接验算，有axbymb(modm)。,第一节同余方程的基本概念,注:例1说明,求方程(2)的解可以转化为求方程myb(moda)(5)的解,这有两个便利之处：第一,将一个对于大模m的同余方程转化为一个对于小模a的同余方程,因此有可能通过对模a的完全剩余系进行逐个验证,以求出方程(5)和(2)的解;第二,设mr(moda),r0，且(a,m)=1，a1是m对模a的最小非负剩余，则同余方程a1xb(modm)(7)等价于同余方程(2)。,解设x是(2)的解，则由m=a1得到,(modm)，即x是同余方程(7)的解。,第一节同余方程的基本概念,但是由假设条件可知同余方程(2)与(7)都有且只有一个解.所以这两个同余方程等价.,注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。,第一节同余方程的基本概念,例4解同余方程6x7(mod23)。,解由例3，依次得到6x7(mod23)5x732(mod23)3x248(mod23)2x8(7)10(mod23)x5(mod23)。,第一节同余方程的基本概念,例5设(a,m)=1，并且有整数0使得a1(modm)，则同余方程(2)的解是xba1(modm)。,解直接验证即可。,注:由例5及Euler定理可知，若(a,m)=1，则xba(m)1(modm)总是同余方程(2)的解。,第一节同余方程的基本概念,例6解同余方程81x324x25x230(mod7)。,解原同余方程即是3x33x22x20(mod7)。用x=0，1，2，3逐个代入验证，得到它的解是x11，x22，x32(mod7)。,注:本例使用的是最基本的解同余方程的方法,一般说来,它的计算量太大,不实用.,第一节同余方程的基本概念,例7解同余方程组.(8),解将(8)的前一式乘以2后一式乘以3再相减得到19y4(mod7)，5y4(mod7)，y2(mod7)。,第一节同余方程的基本概念,再代入(8)的前一式得到3x101(mod7)，x4(mod7)。即同余方程组(8)的解是:x4，y2(mod7).,第一节同余方程的基本概念,例8设a1，a2是整数，m1，m2是正整数，证明：同余方程组(9)有解的充要条件是a1a2(mod(m1,m2)。(10)若有解，则对模m1,m2是唯一的，即若x1与x2都是同余方程组(9)的解，则x1x2(modm1,m2)。(11),第一节同余方程的基本概念,证明必要性是显然的。下面证明充分性。若式(10)成立，由定理2，同余方程m2ya1a2(modm1)有解yy0(modm1)，记x0=a2m2y0，则x0a2(modm2)并且x0=a2m2y0a2a1a2a1(modm1)，因此x0是同余方程组的解。,第一节同余方程的基本概念,若x1与x2都是方程组(9)的解，则x1x2(modm1)，x1x2(modm2)，由同余的基本性质，得到式(11)。,习题一,1.证明定理1。2.解同余方程：()31x5(mod17)；()3215x160(mod235)。3.解同余方程组：。,习题一,4.设p是素数，0ap，证明：