初等数论同余式.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 同余式,1,同余方程的基本概念,定义,：设,则 叫做模,m,的同余方程,若,则称,n,为同余方程的次数。,若 ，则 称为同余式的解,模,m,的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数。,注：对模,m,互相同余的解是同一个解。,例,：同余式,次数为,2,，是解，也是解，因为,所以为同一解，解数是,1,，,为了求方程的解经常有等价变形的问题，对于同余方程同样也有等价变形，即使原同余方程和新的同余方程互相等价的若干变换。常用的变换有,（,1,）移项运算是传统的，,（,2,）同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。,（,3,）乘上一数,k,或除去一个数,k,，,为了保持其同解性，必须（,k,m,）,=1,，,这一点和同余的性质有区别。,例,等价于,等价于,即,，,同余方程和不定方程一样，我们同样要考虑以下三个问题，,即有解的条件，解数及如何求解，,一般地说，对于一般的同余方程，由于仅有有限个解，只要把模,m,的一个完全剩余系一一代入即可，满足同余方程的就是解。,但当模较大或次数较高时应寻求简洁而实用的解法,.,这一章主要讨论,1,、一次同余方程,axb(mod,m),、一次同余方程组,xb1(mod m1),xb2(mod m2),xbk(mod,mk,),的求解。,2,一次同余方程,一次同余方程的一般形式为,axb(mod,m),，有,2.1,定理,：,a,b,为整数，则,axb(mod m),有解的充要条件是,(a,m)|b,若有解则有,d=(a,m),个关于模,m,的解,证明：由同余的定义知,axb(mod m),等价于不定方程,ax=b-my,，而此不定方程有解的充要条件是,(,a,m)|b,。在,有解的,情况下，设不定方程的解为,此时同余方程有,d,个解，为,因当 时，,2.2,一次同余方程,axb(mod m),的解法,。,（,1,）化为不定方程,ax+my=b,例,：解同余式,解 因为,(45,132)=321,所以同余式有,3,个解,.,化简为等价的同余方程,我们再解不定方程,15x-44y=7,得到一解,(21,7).,方程,3,个解为,即为,2),利用欧拉定理 若,(a,m)=1,则有,axb(mod m),两边同乘 ，则有,即,因为,所以,例,:,解同余式,解：因为,(8,11)=1,所以由欧拉定理 有,(3),用形式分数,定义,1,：当（,a,，,m,）,=1,时，若,ab,1(modm),，,则记,b (,modm,),称为形式分数。,根据定义和记号，有性质,1,、,2,、（,d,，,m,）,=1,，,且 ，则,利用形式分数的性质把分母变成,1,，从而求出一次同余式的解,。,例,：解一次同余方程,解：,（,17,，,25,）,=1,，原同余方程有解，利用形式分数的性质，同余方程解为,3,一次同余方程组的解法,定义,:,如下,(*),称为一次同余方程组,xb,1,(mod m,1,),xb,2,(mod m,2,),（*）,xb,k,(mod,m,k,),有解判定定理,：同余方程组,（*）有解的,充要条件是,下面给出,k=2,时的证明,.,证,:,若,(1),有解,则有,(2),即,反之由,(1),得 代入,(2),有,因为,由一次同余方程有解条件知,t,有解,即同余方程组有解,.,下面给出一个例子，并用代入法求解,例,：解一次同余式组,解：因为,(4,6)=2|3-1,所以有解,由,(1),式得,x=3+4t,代入,(2),得,即 得 代入,x=3+4t,得,即 为一次同余式组的解。,下面我们给出模两两互素的情形，此时显然满足有解的条件，即,孙子定理,：设 两两互素，,则同余式,(*),组的解为,其中,证明：因为 两两互素，,所以有 中的 存在，又对任意的 有 有,所以 即是,(*),的解,若 是满足,(*),的两个整数，则有,又,所以有,即,说明是惟一解。,例,：解一次同余式组,解,:,因为,7,，,8,9,两两互素，可以利用孙子定理,.m=504,进而有,所以有,是原一次同余式组的解。,注,：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的。,同余方程组（,1,）有解的条件,(m,i,m,j,)b,i,-,b,j,，,1i,，,jk,。,在使用时一定要对所有的组合进行验算，进行有解的判别,求解一次同余方程组（*）有两种方法：待定系数法和孙子定理,二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是两两互素。,次数大于,1,的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理可求出原高次同余方程的解。,4,高次同余方程,定义,1,、次数大于,1,的同余方程称为高次同余方程,对一般模的高次同余方程我们要通过“小模”和“降次”的方法来得到一般模的高次同余方程的解。,1,、小模：即把一般模高次同等方程转化为一系列模两两互素的高次同余方程组，即有,定理：设 ，两两互素，则 （,1,）等价于下面方程组,（,2,）,设 和 的解数为 则有,下面来看证明,.,证明：若 是（,1,）的解，即 则 从而有 ，即 即（,1,）的解就是（,2,）的解，反之若 是（,2,）的解，则有,即 从而有 由于 两两互素，所以,，从而 有 即 即（,2,）的解也是（,1,）的解。,又由于（,2,）中第,i,个方程有 个解，则（,2,）一共可组合成 个一次同余式组，由孙子定理每一个同余式组有惟一解，所以有 个解，又由于（,1,）（,2,）的等价性，所以有,例,：同余方程,解：原同余方程等价于同余方程组,即有,所以有,4,解，由孙子定理为,由于 所以,等价于同余方程组,从而从理论上说只要能解 即可，而由性质可知若,x,是 的解，则一定是 的解,所以只要在 的解中 找 的解。,所以理论上只要解素数模 同余方程即可。,对素数模同余方程，可以降次，看下面的,定理,：设,p,是素数，是整系数多项式，设 是 的一个解，则有,（,1,）则存在整数,t,使得,是 的解。,（,2,）且 ，则 当,t=0,，,1,，,2P-1,时，都是 的解。,证明：由已知 是 的解，可设 代入 ，则有,两边同除 得,由 所以上式有惟一解，代入,x,有,是 的解。,又若 且 ，则（*）对任意,t,都成立。即当,t=0,，,1,，,2P-1,时，都是 的解。从而证明了定理。,例,：解方程,解：因为 的解为,即,x=2+3t,，,因为,由定理因为有 所以当,t=0,，,1,，,2,时，即 都是方程的解。,例,：解方程,解：因为 等价于,其解为,因 令,x=,1+5t,代入 有,即 即,即有 代入,x=1+5t,有,所以有 代入 有 两边同除,25,有,有 代入,x,有,即 是方程的解。,同理从 可得到另一解（作练习）,从上可知解 最后可归结为解 即可，下面讨论 的解法。,5,素数模同余方程 （*）,定理：同余方程（*）或者有,P,个解，或者与一个次数不超过,p-1,次的素数模同余方程等价。,证：由多项式除法，存在,q,（,x,）和,r,（,x,）,使得,由费马定理,因此若 的系数全为,p,的倍数，则同余方程（*）有,p,个解，若 的系数不都是,p,的倍数，则 的次数不超过,p-1,次，且对任意的,x,有是 ，即同余方程（*）等价 证毕。,定理,2,：设同余方程（*）有,k,个不同的解,则对于任意的,x,有,其中 是一个次数为,n-k,的整系数多项式，且它的 的系数为,注,:,这个定理同一般方程类似,有一个,则从,f(x,),中就可分解出,下面来看证明,.,证：由多项式除,因,有 ，即,令,有,由于 是有,k,个不同的解，所以有,(i=2,3,k),由归纳假设有,代入得有,证毕。,由定理,2,我们可得到下面的推论,推论,1,：,p,是素数，对任意的,x,有,证：由欧拉定理 有解，且其解为,1,2p-1,由定理,2,知即得。,推论,2(,威尔逊定理,）：,p,是素数，则有,证：由推论,1,令,x=p,代入则有，,反之若,则,m,是素数。（自己证明）,注：所以威尔逊定理可用来判定一个数是否为素数。,定理,3,：同余方程（*）的解数不超过它的次数。,证：假设同余方程（*）有,n+1,个解，设为,由定理,2,知，对前,n,个解有,对第,n+1,个解有,由于,所以有,i,使得,和已知矛盾，所以假设错误。即同余方程（*）的解数不超过它的次数。,定理,4,：同余方程（*）有,n,个解的充要条件是存在,q,（,x,）和,r,（,x,），,使得,r(x,),的次数小于,n.,证：必要性 由多项式除法，存在,q,（,x,）,和 使得,若同余方程（*）有,n,个解，由费马定理有,i=1,2,n,由定理,3,：同余方程（*）的解数不超过它的次数，所以只有当 对,p,没有次数时成立，即 即,充分性 若 ，则,即 有,p,个解，,因为,q(x),是,p-n,次多项式，的解数小于等于,p-n,若同余方程（*）的解数小于,n,则 的解数小于,p,而由费尔马定理知有,p,个解，矛盾。所以有,n,个解,例,：证明：若,p,是奇素数，则有,证：,由威尔逊定理知 （*）,所以（*）可写为,所以有,