初等数论§4同余式

2020/5/3,阜阳师范学院数科院,1,第四章同余式,4.1基本概念及一次同余式,2020/5/3,阜阳师范学院数科院,2,一、基本概念,是关于模m的同余方程，或同余式。,则称为n次同余方程。,则剩余类里的元素都满足该方程。,定义1,2020/5/3,阜阳师范学院数科院,3,即与a同余的一切整数作为（1）式的一个解。,注：同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。显然，同余方程(1)的解数不超过m。,2020/5/3,阜阳师范学院数科院,4,二、等价同余式,定理1下面的结论成立：,（1）设b(x)是整系数多项式，则同余方程(1)与f(x)b(x)b(x)(modm)等价；,（2）设b是整数，(b,m)=1，则同余方程(1)与bf(x)0(modm)等价；,（3）设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)0(modm)或h(x)0(modm)的解。,2020/5/3,阜阳师范学院数科院,5,三、一次同余方程的基本解法,定理2设a，b是整数，a0(modm)。则同余方程,axb(modm)(2),有解的充要条件是(a,m)b。,若有解，则恰有d=(a,m)个解。,特别地，若(a,m)1，则方程（2）有唯一解。,证明axb(modm),同余方程(2)等价于不定方程axmy=b，(3),因此，第一个结论可由第二章第一节定理1P25得出。,2020/5/3,阜阳师范学院数科院,6,若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，,由式(4)所确定的x都满足方程(2)。,axb(modm)(2),axmy=b(3),此时，方程(3)的解是,记d=(a,m)，以及t=dqr，qZ，r=0,1,2,d1.,0rd1。,2020/5/3,阜阳师范学院数科院,7,容易验证，当r=0,1,2,d1时，相应的解,对于模m是两两不同余的，所以同余方程(2)恰有d个解。,解方程(2)的方法：,先求出相应不定方程axmy=b的一个特解,2020/5/3,阜阳师范学院数科院,8,例1解同余式,故原同余式有3个解。,所以原同余式的解为,2020/5/3,阜阳师范学院数科院,9,四、其他解法,定理3,axb(modm),证:直接验算，有,axbymb(modm)。,注：将一个对于较大模m的同余方程转化为一个对于较小模a的同余方程，设mr(moda)，r0，且(a,m)=1，a1是m对模a的最小,非负剩余，则同余方程,等价于同余方程axb(modm),证：设x是axb(modm)的解，,即x是同余方程的解。,由假设条件知：这两个同余方程都有且只有一个解，,所以这两个同余方程等价。,2020/5/3,阜阳师范学院数科院,14,例3解同余方程6x7(mod23)。,解由定理4，依次得到,6x7(mod23),5x732(mod23),3x248(mod23),2x8710(mod23),x5(mod23)。,axb(modm),2020/5/3,阜阳师范学院数科院,15,定理5,四、其他解法,应用欧拉定理,设(a,m)=1，并且有整数0使得a1(modm)，,则同余方程axb(modm)的解是xba1(modm).,注1：直接验证即可。,注2：由定理5及Euler定理可知，若(a,m)=1，则,xba(m)1(modm)是同余方程axb(modm)的解。,例4解同余方程,解：xba(21)1,2020/5/3,阜阳师范学院数科院,16,五、简单同余方程组模相同的解法,例5解同余方程组,解:将(*)的前一式乘以2，后一式乘以3，相减得到,(*),19y4(mod7)，,即5y4(mod7)，,y2(mod7)。,再代入(*)的前一式得到,3x101(mod7)，,x4(mod7)。,即同余方程组(*)的解是x4，y2(mod7)。,注：同余方程组的解法与方程组的解法相似。,2020/5/3,阜阳师范学院数科院,17,4.2孙子定理,2020/5/3,阜阳师范学院数科院,18,问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。孙子算经,分析：设所求物数为x，则有,称之为同余式组。,即要求这些同余式的公共解。,2020/5/3,阜阳师范学院数科院,19,问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。孙子算经,为什么啊？,2020/5/3,阜阳师范学院数科院,20,问题1：今有物不知其数，三三数之剩二，五五数之剩二，七七数之剩二，问物几何。,问题2：今有物不知其数，三三数之剩二，五五数之剩三，问物几何。,x-2是3、5、7的公倍数。,2020/5/3,阜阳师范学院数科院,21,问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。孙子算经,2020/5/3,阜阳师范学院数科院,22,一、同余式组的解法中国剩余定理,定理1孙子定理,m1,m2,mk是两两互质的正整数，,记m=m1m2mk，,则(1)的解为,其中，整数Mi（1ik），满足MiMi1(modmi).,设有同余式组,2020/5/3,阜阳师范学院数科院,23,证明：由(Mi,mi)=1，利用辗转相除法可以求出,Mi与yi，使得,MiMiyimi=1，,aiMiMiai(modmi)，1ik。,2020/5/3,阜阳师范学院数科院,24,反之，若是（1）的解，,又m1,m2,mk两两互质，,故方程（1）的解只能为（2）式。,2020/5/3,阜阳师范学院数科院,25,例1解同余式组,衍数,乘率,2020/5/3,阜阳师范学院数科院,26,例2韩信点兵有兵一队，若列成五行纵队，则末行1人；成六行纵队，则末行5人；成七行纵队，则末行4人；成十一行纵队，则末行10人。求兵数。,余数,衍数,2020/5/3,阜阳师范学院数科院,27,列表如下：,其他略,14623,53851,43301,102101,6731,3,1,1,1,2020/5/3,阜阳师范学院数科院,28,定理2在定理1的条件下，若式(1)中的a1,a2,ak分别通过模m1,m2,mk的完全剩余系，则式(2)中的x通过模m1m2mk的完全剩余系。,证明：,则x通过m1m2mk个整数，,且容易它们是两两不同余的。,2020/5/3,阜阳师范学院数科院,29,二、同余方程组解的存在性及解数的判定,引理：设a1，a2是整数，m1，m2是正整数，则同余方程组,有解的充要条件是a1a2(mod(m1,m2)(4),若有解，则对模m1,m2是唯一的，即若x1与x2都是同余方程组(3)的解，则x1x2(modm1,m2)。(5),证必要性,2020/5/3,阜阳师范学院数科院,30,充分性记(m1,m2)d.,若式(4)成立，,则同余方程m2ya1a2(modm1)有解yy0(modm1)，,记x0=a2m2y0，则x0a2(modm2).,并且x0=a2m2y0a2a1a2a1(modm1)，,因此x0是同余方程组(3)的解。,若x1与x2都是方程组(3)的解，,则x1x2(modm1)，x1x2(modm2)，,从而有x1x2(modm1,m2)。,2020/5/3,阜阳师范学院数科院,31,定理3同余方程组(1)有解的充要条件是,aiaj(mod(mi,mj)，1i,jn。(6),2020/5/3,阜阳师范学院数科院,32,2020/5/3,阜阳师范学院数科院,33,2020/5/3,阜阳师范学院数科院,34,4.3高次同余式的解数及解法,2020/5/3,阜阳师范学院数科院,35,一、化合数模为两两互质的模,例1解同余方程5x26x490(mod60)。（1）,解：60=345，同余方程(1)等价于同余方程组,5x26x490(mod3)即-x210(mod3)(2)5x26x490(mod4)即x22x10(mod4)(3)5x26x490(mod5)即x-10(mod5)(4),由(2)得：,x1(1)1，x2(1)1(mod3)，,由(3)得：,x1(2)1，x2(2)1(mod4)，,由(4)得：,x1(3)1(mod5),2020/5/3,阜阳师范学院数科院,36,这样，同余方程(1)的解x可由下面的方程组决定：,x1(1)1，x2(1)1(mod3)，,x1(2)1，x2(2)1(mod4)，,x1(3)1(mod5),xa1(mod3)，xa2(mod4)，xa3(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=3，,则x40a115a236a3(mod60)。,将a1，a2，a3所有可能的取值代入上式，得到方程(1)的全部解是,x11(mod60)，x219(mod60)，x331(mod60)，x411(mod60)。,2020/5/3,阜阳师范学院数科院,37,注：由定理4及算术基本定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。,定理4设m=m1m2mk，其中m1,m2,mk是两两,互素的正整数，f(x)是整系数多项式，以T与Ti,（1ik）分别表示同余方程,f(x)0(modm)（1）,与f(x)0(modmi)，1ik.（2）,的解的个数，,则T=T1T2Tk。,2020/5/3,阜阳师范学院数科院,38,定理的证明：,因为ab(modmi)，1ik,ab(modm)，,所以同余方程(1)等价于同余方程组（2）,f(x)0(modm)（1）,f(x)0(modmi)，1ik.（2）,对于每个i（1ik），设同余方程(2)的全部解是,则同余方程组(3)等价于下面的T1T2Tk个方程组：,其中通过式(3)中的数值，即通过方程(2)的全部解。,2020/5/3,阜阳师范学院数科院,39,f(x)0(modm)（1）,f(x)0(modmi)，1ik.（2）,由孙子定理，对于选定的每一组,同余方程组(4)对模m有唯一解。,而且，由4.2定理2，,当每个通过(3)式中的值时，,所得到的T1T2Tk个同余方程组(4)的解对于模m都是,两两不同余的。,2020/5/3,阜阳师范学院数科院,40,二、方幂模的解法,若x0是同余方程f(x)0(modp)(1)的解，,则必是方程f(x)0(modp-1)(2)的解.,因此，必有与x0相应的方程(2)的某个解x1，使,x0x1(modp)，x0=x1p-1t0，,即可以从方程(2)的解中去求方程(1)的解。,但对于方程(2)的每个解x1，是否必有方程(1)的解x0与之对应？若有，如何去确定它？,2020/5/3,阜阳师范学院数科院,41,定理5设p是素数，n2，f(x)=anxna1xa0是整系数多项式，又设x1是同余方程(2)的一个解。以f(x)表示f(x)的导函数。,则对于t=0，1,2,p1，式(3)中的x都是,方程(1)的解。,f(x)0(modp)(1),f(x)0(modp-1)(2),是方程(1)的解。,2020/5/3,阜阳师范学院数科院,42,证明：如何确定式(3)中的t，,使x1p1t满足同余方程(1)，,an(x1+p1t)n+an1(x1+p1t)n1+a1(x1+p1t)+a0,0(modp),即要使,由二项式定理展开可得,f(x1)p1tf(x1)0(modp)（4）,f(x)0(modp)(1),f(x)0(modp-1)(2),下面考虑两种情形,2020/5/3,阜阳师范学院数科院,43,(1)若f(x1)0(modp)，,则关于t的同余方程(5)有唯一解tt0(modp)，,即t=t0pk（kZ），,于是xx1p1t0(modp)是同余方程(1)的解。,(2)若f(x1)0(modp)，并且f(x1)0(modp)，,则式(5)对于任意的整数t成立，,即同余方程(5)有p个解ti(modp)，0ip1。,于是xx1p1i(modp)，0ip1，都是同余方程(1)的解。,2020/5/3,阜阳师范学院数科院,44,2020/5/3,阜阳师范学院数科院,45,例2解同余方程,考虑方程：,则(2)的解可表示为：,代入(2)，得,2020/5/3,阜阳师范学院数科院,46,则(2)的解可表示为：,即(2)的解可表示为：,从而(1)的解可表示为：,2020/5/3,阜阳师范学院数科院,47,推论1,若xa(modp)是同余方程,2020/5/3,阜阳师范学院数科院,48,推论2,2020/5/3,阜阳师范学院数科院,49,三、一般高次同余式的解法,例3解同余方程x33x140(mod45),解：原同余方程等价于同余方程组,x33x140(mod9)，(1)x33x140(mod5).(2),先求(1)的解：,x33x140(mod3)的解为,x2(mod3)。,令x=23t并代入方程(1)，得到,(23t)33(23t)140(mod9)，,恒成立。,于是方程(1)的解是x2，5，8(mod9)。,2020/5/3,阜阳师范学院数科院,50,例3解同余方程x33x140(mod45),(2)的解为：x1，2(mod5)。,解：原同余方程等价于同余方程组,x33x140(mod9)，(1)x33x140(mod5).(2),(1)的解是：x2，5，8(mod9)。,xa1(mod9)，a1=2，5，8，xa2(mod5)，a2=1，2。,因此，原同余方程的解是下面六个同余方程组的解：,利用孙子定理解这六个方程组.,2020/5/3,阜阳师范学院数科院,51,记m1=9，m2=5，m=45，M1=5，M2=9，,将a1和a2的不同取值代入，得到所求的解是,x11029111(mod45)，x2102922(mod45)，x31059141(mod45)，x41059232(mod45)，x51089126(mod45)，x61089217(mod45),2020/5/3,阜阳师范学院数科院,52,4.4质数模的同余式,2020/5/3,阜阳师范学院数科院,53,在上节证明了，对于素数p，模p的同余方程的求解可以转化为模p的同余方程的求解。本节要对素数模的同余方程做些初步研究。,以下，设f(x)=anxna1xa0是整系数多项式，,2020/5/3,阜阳师范学院数科院,54,f(x)=anxna1xa00(modp)(1),定理1同余方程,与一个次数不超过p-1的同余式等价。,证：由带余数除法，存在整系数多项式,由费马定理知，,2020/5/3,阜阳师范学院数科院,55,定理2设kn，若同余方程(1)有k个不同的解,其中fk(x)是一个次数为nk的整系数多项式，,x1,x1,xk，则对有,f(x)(xx1)(xx2)(xxk)fk(x)(modp)，,并且它的xnk项的系数是an.,证明：由多项式除法，有f(x)=(xx1)f1(x)r1，(2),f1(x)是首项系数为an的n1次整系数多项式，r1是常数。,在式(2)两边令x=x1，则可知f(x1)=r10(modp)，,因此，式(2)成为f(x)(xx1)f1(x)(modp)(3),即当k=1时，定理成立。,2020/5/3,阜阳师范学院数科院,56,如果k1，在(3)式中，令x=xi（i=2,3,k），,则有0f(xi)(xix1)f1(xi)(modp)(4),由于x1,x2,xk对于模p是两两不同余的，,f1(xi)0(modp)，i=2,k。(5),所以，由(4)式得出,由此及归纳法，即可证明定理。,f(x)(xx1)f1(x)(modp)(3),2020/5/3,阜阳师范学院数科院,57,定理3,(1)若p是素数，则对于任何整数x，有,xp11(x1)(x2)(xp1)(modp)。,(2)Wilson定理,证明:,(1)由Fermat定理，数1,2,p1是同余方程,xp11(modp)，即xp110(modp)的解，,因此，利用定理2可得,xp11(x1)(x2)(xp1)fk(x)(modp),其中fk(x)an1，,所以xp11(x1)(x2)(xp1)(modp)。,2020/5/3,阜阳师范学院数科院,58,定理4同余方程(1)的解数n。,证明:假设同余方程(1)有n+1个不同的解,xxi(modp)，1in1。,由定理2，有f(x)an(xx1)(xxn)(modp)，,因此0f(xn+1)an(xn+1x1)(xn+1xn)(modp)。,矛盾！,2020/5/3,阜阳师范学院数科院,59,定理5,设np，则同余方程,f(x)=xnan1xn1a1xa00(modp)(1),有n个解的充要条件是,存在整数多项式q(x)和r(x)，r(x)的次数n，