合同一次同余式.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.3 合同 一次同余式,1,5.3.1 合同及其性质,设,m,是任意非0整数。,a,被,m,整除时，我们就说,a,合同于0模,m，,记为：,a,0(mod m),一般来说，若,a-b,被,m,整除，则我们说,a,合同于,b,模,m：a,b(mod m),一个数为,m,整除，当且仅当此数为-,m,整除。所以，若未指定,m,而一般地讨论模,m,合同时，我们总假定,m,是正整数。,2,5.3.1 合同及其性质,设,a=q,1,m+r,1,，0r,1,m；b=q,2,m+r,2,，0r,2,m。,于是,a-b=(q,1,-q,2,)m+(r,1,-r,2,),由此式，,m|(a-b),必要而且只要,m|(r,1,-r,2,)，,但|,r,1,-r,2,|m，,故,m|(r,1,-r,2,),必要而且只要,r,1,-r,2,=0。,因之，,ab(mod m),必要而且只要以,m,除,a,和,b,所得的余数相同。,3,合同的基本性质,性质1,aa。,性质2,若,ab,则,ba。,性质3,若,ab，bc，,则,ac。,这就是说，合同是一种等价关系。每一个等价类称为模,m,的一个,剩余类,。,4,合同的基本性质,性质4,若,ab(mod m)，cd(mod m)，,则,a,cb,d(mod m)，acbd(mod m),证明：,由题设有,r，s,使,a-b=rm，c-d=sm。,故(,a,c)-(b,d)=(r,s)m,因而,a,c,b,d(mod m)。,其次，,ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm,2,bd+0+0+0(mod m)=bd(mod m)，,故,ac,bd(mod m)。,5,合同的基本性质,性质5,若,a,b(mod m)，,则,a,k,b,k(mod m)。,其中,k,为整数。,性质6,若,a+b,c(mod m)，,则,a,c-b(mod m)。,性质7,若,a,b(mod m)，,则,ac,bc(mod m)。,性质8,若,a,b(mod m)，,则,a,n,b,n,(mod m)，n,0。,6,合同的基本性质,性质9,若,c,0,而,ac,bc(mod mc)，,则,a,b(mod m)。,证明：由题设有,q,使,ac-bc=qmc，,于是,a-b=qm，,因而,a,b(mod m)。,性质10,若,c,和,m,互质，则由,ac,bc(mod m),可以推出,a,b(mod m)。,证明：,ac=bc(mod m),表示,m|(a-b)c，,但,c,和,m,互质，所以有,m|(a-b)，,于是,a,b(mod m)。,7,合同的基本性质,性质11,若,ac,bc(mod m)，,且（,c,m）=d，,则,a,b(mod m/d),证明：由,ac,bc(mod m),知，,m|(a-b)c，,而(,c,m)=d，,故,m/d|(a-b)c/d。,注意到（,m/d,c/d）=1，,从而得,m/d|(a-b)，,即,a,b(mod m/d)。,对于质数模,p，,则有和相等完全类似的消去律。,8,合同的基本性质,性质12,若,p,为质数，,c,0(mod p)，,而,ac,bc(mod p)，,则,a,b(mod p)。,证明：因为,p,是质数，,c,0(mod p),就表示,c,和,p,互质，(,c,p)=1，,因而性质12不过是性质10的推论。,9,合同的基本性质,性质13,设,p(x),是整系数多项式，,x,和,y,是整数变量，则由,x,y(mod m),可得,p(x),p(y)(mod m)。,10,运用性质13，我们再看能被9整除数的数码特征。设,N=a,n,10,n,+a,n-1,10,n-1,+a,1,10+a,0,为一整数，因为10,1(,mod 9)，,由性质13得,N,a,n,1,n,+a,n-1,1,n-1,+a,1,+a,0,(mod 9),即,。,于是 9|,N,当且仅当9|,11,5.3.2,剩余类,一次同余式,模,m,合同既然是一种等价关系，就可以把所有整数按照模,m,合同的关系分为等价类，每一个等价类称为模,m,的一个剩余类。,同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。,因为以,m,去除任意整数，可能得到的余数恰有0，1，,m-1，,这,m,个数，所以模,m,共有,m,个剩余类，,12,5.3.2,剩余类,一次同余式,从每个剩余类中取出一个数作为代表，这样便可得到,m,个数，比方,r,1,r,2,r,m,说是作成一个完全剩余系，任意整数模,m,恰好合同于此完全剩余系中的一个数。例如，0，1，,m-1,便是这样一个完全剩余系。又如，模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数。,13,同余式,含有整数变量的合同式，称为合同方程或同余式,。,ax,b(mod m),这种形式的合同式称为一次同余式；类似地，,a,2,x,2,+a,1,x,b(mod m),称为二次同余式。,14,同余式,求解一次同余式实际上是解,ax-b=my,这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？,15,定理,5.3.1,若,a,和,m,互质，,b,任意，则模,m,恰有一个数,x,使,ax,b(mod m)。,证明：,存在性,。因为,a,和,m,互质，故有,s，t,使,as+mt=1，,于是,asb+mtb=b，,若取模,m，,则有,asb,b(mod m)。,取,x=sb，,则,sb,所在的剩余类中的数皆是解。,唯一性,。所谓模,m,只有一个这样的,x,，,意思是说在模,m,合同的意义下，解是唯一的。即若,ax,b(mod m),，,ay,b(mod m),，,则,x,y(mod m),。,因为，由,ax,b(mod m),，,ay,b(mod m),得,ax,ay(mod m),，,消去和,m,互质的,a,乃得,x,y(mod m),。,16,定理,5.3.1,推论,设,P,为质数。若,a,0(mod p),，,b,任意，则模,p,恰有一个数,x,使,ax,b(mod p),。,17,定理5.3.2,若(,a,m)=d,1，,且,d|b，,则同余式,ax,b(mod m),无解。,证明：,反证法。若上式可解，则存在,，,使得,a,b(mod m),。,从而存在,q,，,使得,b=a,-mq,。,因为,(,a,m)=d,1,，,故,d|(a,-mq),，,从而,d|b,，,矛盾。,18,定理5.3.3,若(,a,m)=d,1，,且,d|b，,则同余式,ax,b(mod m)(,1,),有,d,个解，分别为,+m/d,+2m/d,+(d-1)m/d(,2,),其中,是同余式(,a/d)x,b/d(mod m/d)(,3,),的解。,19,定理5.3.3,证明：,由,性质11,和,性质9,知,(,1,)的解是(,3,)的解，(,3,)的解也是(,1,)的解。因为(,a,m)=d，,所以(,a/d,m/d)=1。,由,定理5.3.1,知，(,3,)在模,m/d,下有唯一解，设为,，,不妨设0,m/d。,因为,+km/d,恰是,所在的模,m/d,剩余类的全部元素，,k=0,1,2,，,故,(,3,),的解作为数都可以表示成,+km/d,的形式。于是,(,1,),的解都是,+km/d,形式的数，,k=0,1,2,。,20,定理5.3.3,下面证明(,2,)式是(,1,)的,d,个不同解。因为0,m/d，,故0,(,2,)中每一个式子,m，,且互不相同，所以它们之间关于模,m,互不同余，即(,2,)为(,1,)的,d,个不同解。,再考虑(,1,)只有(,2,)这,d,个不同解。即若数,+lm/d,是(,1,)的解，则关于模,m，,+lm/d,必同余(,2,)中,d,个数之一。,因为,0,，,1,，,d-1,为关于模,d,的完全剩余系，故存在,i,，,0,i,d-1,，,使得,l,i(mod d),。,由,m/d,0,和性质,9,，两边和模同乘,m/d,得，,(,l/d)m,(i/d)m(mod m),，,故,+lm/d,+im/d(mod m),。,证毕。,21,求解一次合同方程的方法,我们以,解合同式,103,x,57(mod 211),为例.,方法一:,定理,5.3.1,告诉我们若,a,和,m,互质，,b,任意，则模,m,恰有一个数,x,使,ax,b(mod m),。,该定理证明存在性的过程即告诉了我们一种求解方法：因为,a,和,m,互质，故有,s,，,t,使,as+mt=1,，,于是,asb+mtb=b,，,若取模,m,，,则有,asb,b(mod m),。,取,x=sb,，,则,sb,所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的,a,与,m,的最大公因数,1,表示为,a,和,m,的倍数和的形式：,1=,as+mt,，,然后取,x=sb,，,即可。,22,求解一次合同方程的方法,解：由于,103,与,211,互质，我们先将,103,与,211,的最大公因数,1,表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算,S,k,，,T,k,如下表所示：,k,0,1,2,3,4,5,r,k,5,3,2,1,0,q,k,2,20,1,1,3,S,k,0,1,20,21,41,T,k,1,2,41,43,84,23,求解一次合同方程的方法,因此，,1=,（,-1,）,3,41,211+（-1）,4,84,103。,由此知，,S=（-1）,4,84,，,所以,x=sb=84,57=4788=21,23-65,-65(mod 211),。,24,求解一次合同方程的方法,方法二:,就是利用合同的性质，使,x,的系数变成,1,，即得到解。,对于上例解合同式,103,x,57(mod 211),。,由于,211=103,2+5,，,由合同的性质,7,有,2,103,x,2,57(mod 211),。,因为,211,x,0(mod 211),，,所以由合同的性质,5,知，,211,x-2,103x,0-2,57(mod 211),。,即,5,x,-114(mod 211),97(mod 211),。,25,求解一次合同方程的方法,由于,211=42,5+1,由合同的性质,7,有,42,5,x,42,97,211,19+65,65(mod 211),。,由合同的性质,5,知，,211,x-42,5,x,0-65(mod 211),。,即,x,-65(mod 211),。,对于一些例子，使用这种方法是比较快的。比如，解合同式,4,x,1(mod 15),。,因为,1,16(,mod 15),，,所以,4,x,1,16,4,4,(mod 15),，,因为,4,与,15,互质，由合同的性质,10,知，合同式两边可以消去,4,，得到,x,4(mod 15),。,26,求解一次合同方程的方法,方法三:,利用,Fermat-Euler,定理（教材中定理,5.4.7,），见下例。,例,5.2.18,解合同式,7,x,5(mod 10),。,解：因为,7,和,10,互质，由,Fermat-Euler,定理有,7,(10),1(,mod 10),，,因,(10)=4,，所以,7,4,1(,mod 10),。,由合同的性质,7,，在,7,x,5(mod 10),两边乘以,7,3,，有,7,3,7,x,7,3,5(mod 10),，,而,7,3,7,x=7,4,x,x(mod 10),，,7,3,5=,7,2,75,（,-1,）,75,5(mod 10),，,所以所给合同式的解为,x,5(mod 10),。,27,