合同一次同余式.ppt

§5.3 合同 一次同余式 §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是正整数。 §5.3.1 合同及其性质 设a=q1m+r1，0≤r1<m；b=q2m+r2，0≤r2<m。于是 a-b=(q1-q2)m+(r1-r2) 由此式，m|(a-b)必要而且只要m|(r1-r2)，但|r1-r2|<m，故m|(r1-r2)必要而且只要r1-r2=0。因之，a≡b(mod m)必要而且只要以m除a和b所得的余数相同。 合同的基本性质 性质1 a≡a。 性质2 若a≡b,则b≡a。 性质3 若a≡b，b≡c，则a≡c。 这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。 合同的基本性质 性质4 若a≡b(mod m)，c≡d(mod m)，则a?c≡b?d(mod m)，ac≡bd(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+rsm2?bd+0+0+0(mod m)=bd(mod m)，故ac?bd(mod m)。 合同的基本性质 性质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)，则an?bn(mod m)， n?0。 合同的基本性质 性质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)。 合同的基本性质 性质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，则有和相等完全类似的消去律。 合同的基本性质 合同的基本性质 性质13 设p(x)是整系数多项式，x和y是整数变量，则由x?y(mod m)可得 p(x) ?p(y) (mod m)。 §5.3.2 剩余类 一次同余式 模m合同既然是一种等价关系，就可以把所有整数按照模 m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。 同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。 因为以m去除任意整数，可能得到的余数恰有0，1，…，m-1，这m个数，所以模m共有m个剩余类， §5.3.2 剩余类 一次同余式 从每个剩余类中取出一个数作为代表，这样便可得到m个数，比方r1, r2, …,rm说是作成一个完全剩余系，任意整数模m恰好合同于此完全剩余系中的一个数。例如，0，1，…，m-1便是这样一个完全剩余系。又如，模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数。 同余式 含有整数变量的合同式，称为合同方程或同余式 。 ax?b(mod m)这种形式的合同式称为一次同余式；类似地，a2x2+a1x?b(mod m)称为二次同余式。 同余式 求解一次同余式实际上是解 ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？ 定理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)