合同一次同余式

1、合同一次同余式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除

2、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+rsm2bd+0+0+0(mod m)=bd(mod m)，故acbd(mod m)。合同的根本性质 性质5 假设ab(mo

3、d 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

4、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，那么有和相等完全类似的消去律。 合同的根本性质 性质12 若p为质数，c0(mod p)，而acbc(mod p)，则ab(mod p)。证明：因为p是质数，c 0(mod p)就表示c和p互质，(c, p)=1，因而性质12不过是性质10的推论。合同的根本性质 性质13 设p(x)是整系数

5、多项式，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个数，所以

6、模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)称为二次同余式。 同余式求解一次同余式实际上是解 a

7、x-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)得

8、axay(mod m)，消去和m互质的a乃得xy (mod m)。 定理推论 设P为质数。若a 0 (mod p)，b任意，则模p恰有一个数x使axb(mod p)。 若(a, m)=d1，且d|b，则同余式axb (mod m)无解。证明：反证法。若上式可解，则存在，使得ab(mod m)。从而存在q，使得b=a-mq。因为(a, m)=d1 ，故d|(a-mq)，从而d|b，矛盾。 假设(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)

9、的解。 证明：由性质11和性质9知, (1)的解是(3)的解， (3)的解也是(1)的解。因为(a, m)=d，所以(a/d, m/d)=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, 。 下面证明(2)式是(1)的d个不同解。因为0 m/d，故0 (2)中每一个式子 m，且互不一样，所以它们之间关于模m互不同余，即(2)为(1)的d个不同解。再考虑(1)只有(2)这d个不同解。即假设数+lm/d

10、是(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)为例.方法一:定理告诉我们假设a和m互质，b任意，那么模m恰有一个数x使axb(mod m)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，假设取模m，那么有asbb

11、(mod m)。取x=sb，那么sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。 求解一次合同方程的方法解：由于103与211互质，我们先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示：k012345rk53210qk220113Sk01202141Tk12414384求解一次合同方程的方法因此， 1=-1341211+-1484103。由此知，S=-1484，所以x=sb=8457=4788=2123-65-65(mo

12、d 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定理教材中定理，见下例。例