第7章同余.pptVIP

定理7.6 任意一个n位数与其各位上的各数字之和对模9同余。 证明 由定理7.6可得a≡ (mod 9)，b≡ (mod 9)，c≡ (mod 9)。又因为ab＝c , 所以 · ≡ (mod 9)。 本节讨论最简单的同余方程组，即由下面给出的一次同余方程组： x≡b1(mod m1) x≡b2(mod m2) (1) … x≡bk(mod mk) 定理7.22 (孙子定理)设m1、m2、…、mk是两两互素的k个正整数，k≥2，并且m＝m1m2…mk，m＝mjMj，1≤j≤k，则一次同余方程组(1)有惟一解：x≡b1M1?M1＋b2 M2?M2＋…＋bkMk?Mk(mod m) (2) 其中，整数Mj?满足Mj?Mj≡1(mod mj)，1≤j≤k。Mj?也称为Mj对模mj的逆，记为Mj－1。 (2)因为(40，6191)＝1，所以方程有惟一解。利用辗转相除法求得使40x＋6191y＝1成立的x、y为x＝1393，y＝－9。于是40·1393＋6191·(－9)＝1，40·1393·191＋6191·(－9·191)＝191，所以x≡1393·191≡6041(mod 6191) (3)因为(258， 348)＝6，而6 131，所以方程无解。 求同余方程4x2＋27x－12≡0(mod 15)的解。 解 取模15的非负最小完全剩余系0、1、2、…、14，直接计算知x＝3、9是解。所以这个同余方程的解为：x≡3，9(mod 15)。 定理7.18(1)若f(x)≡g(x)(mod m)，则同余方程(2)的解与解数与同余方程g(x)≡0(mod m)相同。 (2)若(a，m)＝1，则同余方程(2)的解与解数与同余方程af(x)≡0(mod m)相同。 定理7.19 同余式组a≡b(mod mj)(j＝1，2，…，k)同时成立，当且仅当a≡b(mod [m1，m2，…，mk])。 例2 对任给素数p，f(x)＝(x－1)(x－2)…(x－p＋1)－xp-1＋1的所有系数被p整除。 证明 令g(x)＝(x－1)(x－2)…(x－p＋1)，h(x)＝xp-1－1，则f(x)＝g(x)－h(x)。因为1、2、…、p－1是g(x)≡0(mod p)的p－1个解，由费马定理知它也是h(x)≡0(mod p)的p－1个解，所以f(x)≡0(mod p)有p－1个解，而f(x)是p－2次多项式，由定理7.20得，其所有系数被p整除。 7.5 一次同余式组 * * 7.1 同余及其性质 7.2 剩余类和剩余系 7.4 一次同余式 7.3 欧拉定理与威尔逊定理 7.5 一次同余式组 7.1同余及其性质 定义7.1 给定正整数m，若用m去除两个整数a和b所得余数相同，称a和b对模m同余，记作a≡b(mod m)，并称该式为同余式；否则，称a和b对模m不同余，记作a b(mod m)。 对于给定的b和m，与b模m同余的所有数为：b＋km，其中k＝0，±1，±2，±…。 定理7.1 a≡b(mod m)当且仅当m|(a－b) 证明 若a≡b(mod m)，则有a＝q1m＋r，b＝q2m＋r，0≤r＜m。于是有a－b＝(q1－q2)m，所以m|(a－b)。反之，令a＝q1m＋r1，b＝q2m＋r2，其中0≤r1＜m，0≤r2＜m，则r1－r2＝(a－b)－(q1－q2)m。由题设m|(a－b)，从而m|(r1－r2)。又因为|r1－r2|＜m，故r1＝r2，于是a≡b(mod m)。 定理7.2 同余关系是等价关系，即 (1)自反性 a≡a(mod m)。 (2)对称性 若a≡b(mod m)，则b≡a(mod m)。 (3)传递性 若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)。 定理7.3设a、b、c、d为整数，m为正整数，若a≡b(mod m)，c≡d(mod m)，则： (1)ax＋cy≡bx＋dy(mod m)，x、y为任意整数，即同余式可以相加； (2)ac≡bd(mod m)，即同余式可以相乘； (3)an≡bn(mod m)，n＞0； (4)f(a)≡f(b)(mod m)，f(x)为任