5.3 合同 一次同余式,5.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是正整数。,5.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)必要而且只要以m除a和b所得的余数相同。,合同的基本性质,性质1 aa。 性质2 若ab,则ba。 性质3 若ab，bc，则ac。 这就是说，合同是一种等价关系。每一个等价类称为模m的一个剩余类。,合同的基本性质,性质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+rsm2 bd+0+0+0(mod m)=bd(mod m)，故acbd(mod m)。,合同的基本性质,性质5 若ab(mod 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。,合同的基本性质,性质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)。,合同的基本性质,性质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，则有和相等完全类似的消去律。,合同的基本性质,合同的基本性质,性质13 设p(x)是整系数多项式，x和y是整数变量，则由xy(mod m)可得 p(x) p(y) (mod m)。,运用性质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|,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代表所有奇数。,同余式,含有整数变量的合同式，称为合同方程或同余式 。 axb(mod m)这种形式的合同式称为一次同余式；类似地，a2x2+a1xb(mod m)称为二次同余式。,同余式,求解一次同余式实际上是解 ax-b=my这样的不定方程。我们这里讨论一次同余式在什么条件下有解？什么条件下无解？什么时候有唯一解（一个剩余类）？什么时候有多解（多个剩余类）？,定理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)得axay(mod m)，消去和m互质的a乃得xy (mod m)。,定理5.3.1,定理5.3.2,定理5.3.3,若(a, m)=d1 ，且d|b，则同余式 axb(mod m) (1) 有d个解，分别为 , +m/d, +2m/d, , +(d-1)m/d (2) 其中是同余式 (a/d)xb/d (mod m/d) (3) 的解。,定理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, 。,定理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，0id-1，使得 li (mod d)。由m/d0和性质9，两边和模同乘m/d 得，(l/d)m (i/d)m (mod m)，故+lm/d +im/d(mod m)。证毕。,求解一次合同方程的方法,我们以解合同式103x57(mod 211)为例. 方法一:定理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所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。,求解一次合同方程的方法,解：由于103与211互质，我们先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示：,求解一次合同方程的方法,因此， 1=（-1）341211+（-1）484103。 由此知，S=（-1）484，所以 x=sb=8457=4788=2123-65-65(mod 211)。,求解一次合同方程的方法,方法二:就是利用合同的性质，使x的系数变成1，即得到解。 对于上例解合同式103x57(mod 211)。由于 211=1032+5， 由合同的性质7有 2103x257(mod 211)。 因为 211x0(mod 211)， 所以由合同的性质5知， 211x-2103x0-257(mod 211)。 即5x-114(mod 211) 97(mod 211)。,求解一次合同方程的方法,由于 211=425+1 由合同的性质7有 425 x4297 21119+65 65(mod 211)。 由合同的性质5知， 211x-425 x0-65(mod 211)。 即x-65(mod 211)。 对于一些例子，使用这种方法是比较快的。比如，解合同式4x1(mod 15)。因为 116(mod 15)， 所以4x1 16 44(mod 15)， 因为4与15互质，由合同的性质10知，合同式两边可以消去4，得到 x4(mod 15)。,求解一次合同方程的方法,方法三:利用Fermat-Euler定理（教材中定理5.4.7），见下例。 例5.2.18 解合同式7x5(mod 10)。 解：因为7和10互质，由Fermat-Euler定理有 7(10)1(mod 10)， 因(10)=4，所以741(mod 10)。由合同的性质7，在7x5(mod 10)两边乘以73，有 737x735(mod 10)， 而737x=74 x x(mod 10)， 735=7275（-1）75 5(mod 10)， 所以所给合同式的解为x 5(mod 10)。,