53合同一次同余式

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,作业：,170,页,2,22,