53合同一次同余式

1、5.3 合同 一次同余式 15.3.1 合同及其性质 设m是任意非0整数。a被m整除时，我们就说a 合同于0模m，记为：a0(mod m)一般来说，若a-b被m整除，则我们说a合同于b 模m：ab(mod m)一个数为m整除，当且仅当此数为- m整除。所以，若未指定m而一般地讨论模m合同时，我们总假定m是正整数。 25.3.1 合同及其性质 设a=q1m+r1，0r1m；b=q2m+r2，0r2m。于是a-b=(q1-q2)m+(r1-r2)由此式，m|(a-b)必要而且只要m|(r1-r2)，但|r1-r2|m，故m|(r1-r2)必要而且只要r1-r2=0。因之，ab(mod m)必要而且

2、只要以m除a和b所得的余数相同。 3合同的基本性质 性质1 aa。性质2 若ab,则ba。性质3 若ab，bc，则ac。这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。 4合同的基本性质 性质4 若ab(mod m)，cd(mod m)，则acbd(mod m)，acbd(mod m) 证明：由题设有r，s使a-b=rm，c-d=sm。故(ac)-(bd)=(rs)m, 因而acbd(mod m)。其次，ac=(b+rm)(d+sm)=bd+rdm+bsm+rsm2bd+0+0+0(mod m)=bd(mod m)，故acbd(mod m)。5合同的基本性质 性质5 若ab(m

3、od m)，则akbk (mod m)。其中k为整数。性质6 若a+bc(mod m)，则ac-b(mod m)。性质7 若ab(mod m)，则acbc(mod m)。性质8 若ab(mod m)，则anbn(mod m)， n0。 6合同的基本性质 性质9 若c0而acbc(mod mc)，则ab(mod m)。证明：由题设有q使ac-bc=qmc，于是a-b=qm，因而ab(mod m)。性质10 若c和m互质，则由acbc(mod m)可以推出ab(mod m)。证明：ac=bc(mod m)表示m|(a-b)c，但c和m互质，所以有m|(a-b)，于是ab(mod m)。 7合同的基

4、本性质 性质11 若acbc(mod m)，且（c, m）=d，则ab(mod m/d)证明：由acbc(mod m)知，m|(a-b)c，而(c, m)=d，故 m/d | (a-b)c/d。注意到（m/d, c/d）=1，从而得 m/d|(a-b)，即 ab(mod m/d)。对于质数模p，则有和相等完全类似的消去律。 8合同的基本性质 性质12 若p为质数，c0(mod p)，而acbc(mod p)，则ab(mod p)。证明：因为p是质数，c 0(mod p)就表示c和p互质，(c, p)=1，因而性质12不过是性质10的推论。9合同的基本性质 性质13 设p(x)是整系数多项式，x

5、和y是整数变量，则由xy(mod m)可得 p(x) p(y) (mod m)。 10运用性质13，我们看能被9整除数的数码特征。设N=an10n+an-110n-1+a110+a0为一整数，因为101(mod 9)，由性质13得N an1n+an-11n-1+a1+a0(mod 9)即 。于是 9|N当且仅当9| 115.3.2 剩余类 一次同余式 模m合同既然是一种等价关系，就可以把所有整数按照模 m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。 因为以m去除任意整数，可能得到的余数恰有0，1，m-1，这m个数，所以模m共

6、有m个剩余类， 125.3.2 剩余类 一次同余式 从每个剩余类中取出一个数作为代表，这样便可得到m个数，比方r1, r2, ,rm说是作成一个完全剩余系，任意整数模m恰好合同于此完全剩余系中的一个数。例如，0，1，m-1便是这样一个完全剩余系。又如，模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数。 13同余式 含有整数变量的合同式，称为合同方程或同余式 。axb(mod m)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(mod m)称为二次同余式。 14同余式求解一次同余式实际上是

7、解 ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？ 15定理5.3.1 若a和m互质，b任意，则模m恰有一个数x使axb(mod m) 。证明： 存在性。因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asbb(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。唯一性。所谓模m只有一个这样的x，意思是说在模m合同的意义下，解是唯一的。即若axb (mod m)，ayb(mod m)，则xy(mod m)。因为，由axb(mod m)，ayb(mod m

8、)得axay(mod m)，消去和m互质的a乃得xy (mod m)。 16定理5.3.1推论 设P为质数。若a 0 (mod p)，b任意，则模p恰有一个数x使axb(mod p)。 17定理5.3.2若(a, m)=d1，且d|b，则同余式axb (mod m)无解。证明：反证法。若上式可解，则存在，使得ab(mod m)。从而存在q，使得b=a-mq。因为(a, m)=d1 ，故d|(a-mq)，从而d|b，矛盾。 18定理5.3.3若(a, m)=d1 ，且d|b，则同余式axb(mod m) (1)有d个解，分别为 , +m/d, +2m/d, , +(d-1)m/d (2)其中是同

9、余式(a/d)xb/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， +