初等数论同余式

1、第四章 同余式 1 基本概念及一次同余式 初等数论中的一个基本 课题是研究同余式(同 余方程)的求解问题。 定义1 设m Z ，f(x) anxn an 1xn 1a0，其中 ai Z，则 f (x) 0 (mod m) 称为模 m的同余式。若 an 0 (mod m)，则 n称为次数。 定义2 若 a是使 f (a) 0 (mod m) 成立的一个整数，则 x a (mod m) 叫做 f (x) 0 (mod m) 的一个解。 定义2的合理性：若 f (a) 0(mod m) ，则剩余类 K a中的任意整数 a 都能使 f (a ) 0(mod m) 成立，故把 K a 中的一切数，即 x

2、 a (mod m) 作为一个解。 b(mod m) 有解的充分必要条件是 它们是 定理 设 (a,m) d，则一次同余式 ax d | b。当此条件成立时，同 余式共有 d个解， x x0 k m (mod m)，k 0,1, ,d 0d 其中 x0是同余式 ax b(mod m) 的任一个解。 证明 (1) 同余式 ax b(mod m) 有解 1， 不定方程 ax my b 有解 d |b 。 (2) 因为不定方程 ax my b 的一切整数解为 x x0 m t， d t Z ，所以， 同余式 ax b(mod m) 的解为 x x0 k m (mod m)， d k 0,1, ,d

3、1，解数为 d。 注 当 (a,m) 1 时，一次同余式有唯一 解 x a ( m) 1b (mod m)。 同余式的解法 1、代入法 (适用于模较小时) 例1 解同余式 3x 1(mod 17) 解 因为 ( 3,17) 1，所以同余式有唯一解 ， 以17的完全剩余系逐一代入 ，得 x 6 (mod 17)。 2、公式法 (适用于模较小时) 例2 解同余式 8x 9 (mod 11) 8 (mod 11)。 解 因为 (8,11) 1，所以同余式有唯一解 ， 从而， x 8 (11) 1 9 810 1 9 ( 3)9 ( 2) ( 2) 4 6 5 6 3、变换系数法 例3 解下列同余式

4、(1) 4x 1(mod 15)； (2) 14x 27 (mod 31)； (3) 103x 57 (mod 211)。 解 (1) 因为 (4,15) 1，所以同余式有唯一解 ， 而 4x 1 16 (mod 15)，故 x 4 (mod 15)。 (2) 因为 (14,31) 1，所以同余式有唯一解 ， 而 14x 27 58 (mod 31)， 7x 29 60 91 (mod 31)， 故 x 13 (mod 31) 。 (3) 因为 (103,211) 1，所以同余式有唯一解 ， 由 103x 57 (mod 211) 可得 206x 114 (mod 211)， 于是 5x 11

5、4 (mod 211) 即 5x 97 (mod 211)， 再由 5x 97 (mod 211) 可得 210 x 97 42 (mod 211)， 于是 x 97 42 65 (mod 211) 故 x 65 146 (mod 211) 。 4、换模法 由ax b (mod m) (1)可得 ax b my，模 a后可得 my b (mod a) ( 2)， 当0 a m时，解 (2)比解 (1)方便，而且若 y0是(2)的解，则 x0 b my0 是(1)的解。 a 例4 解同余式 863x 880 (mod 2151) 解 因 863 是质数，且 863 | 2151，故 (863,2

6、151) 1，从而同余式有唯一解 原同余式可化为 863x 880 2151y，模863后得 2151y 880 (mod 863)， 即 425y 880 (mod 863)，也即 85y 176 (mod 863)， 再化为 85y 176 863z，模85后得 863z 176 (mod 85)， 即 13z 6 (mod 85)， 再化为13z 6 85u，模13后得 85u 6(mod 13)， 即 7u 7 (mod 13)，也即 u 1 (mod 13)， 所以 u 0 1，z0 6 85 1 13 7，y0 176 863 7 85 69，x0 880 2151 69 863

7、173， 即 x 173 (mod 2151) 是原同余式的解。 5、辗转相除法 例5 解同余式 863x 880 (mod 2151) 解 因为 (863,2151) 1，所以同余式有唯一解 利用辗转相除法可得 496 863 199 2151 1， 模2151后得496 863 1 (mod 2151)， 所以 x 496 880 173 (mod 2151)。 例6 解同余式 6x 15 (mod 33 ) 解 因为 (6,33) 3 |15，所以同余式有 3个解， 由原同余式可得 2x 5(mod 11)，解得 x 8(mod 11)， 因此原同余式的解为 x 8，19，30 (mod

8、 33)，。 2 孙子定理 本节讨论同余式组 x b1 (mod m1)，x b2 (mod m2 )， ，x bk (mod mk ) 的求解问题。 定理1(孙子定理) 设m1 ,m2, ,mk是两两互质的正整数， m m1m2 mk， m mi M i，i 1,2, , k，则同余式组 x b1 (mod m1)，x b2 (mod m2 )， ， x bk (mod mk )的解是 x M 1 M 1b1 M 2 M 2b2 Mk Mkbk (mod m)， Mix 1(mod mi) 其中 Mi Mi 1(mod mi)，i 1,2, ,k。 证明 因为 (mi,mj ) 1，i j，

9、所以 (mi,Mi ) 1，于是 有一解，设为 Mi ，则 Mi Mi 1 (mod mi )， i 1,2, ,k， 又因为 m miM i，所以 mj |M i，i j， 于是 M1 M1b1 M 2 M 2b2M k Mkbk Mi M ibi bi (mod mi)， 故 x M1M1b1 M2M2b2MkMkbk(modm) 是原同余式组的解。 若 x1,x2是适合同余式组的任意 两个整数， 则 x1 x2 (mod mi )， i 1,2, ,k，于是 x1 x2 (mod m)， M k M kbk (mod m)。 因此，原同余式组只有 一个解 x M1 M1b1 M 2 M

10、2b2 推论1 设正整数 m1,m2 , , mk 两两互质，则同余式组 a1x b1 (mod m1),a2x b2 (mod m2), ,akx bk (mod mk) 有解的充分必要条件是 同余式 ai x bi (mod mi)，i 1,2, , k 有解。 证明 必要性是显然的，下证 充分性。 因为对 i 1,2, , k ，同余式 aix bi (mod mi )，所以 di |bi，这里di (ai,mi )， 于是有 ci 使 ai ci 1(mod mi )，从而原同余式组等价 于 di d i b1m1b2m2bkmk x c1(mod ), x c2(mod ), , x

11、 c k(mod)，当然有解。 d1d1d 2d2dkdk 推论2 若b1,b2, , bk分别通过模 m1, m2, , mk的完全剩余系，则 x M 1 M 1b1 M 2 M 2 b2M k M k bk (mod m) 通过模 m m1m2 mk的完全剩余系。 k 证明 令x0M i M ibi，则 x0过m1m2 mk个数，这 m个数两两不同余。 i1 kk 这是因为若Mi MibiMi Mibi (mod m)， i 1 i 1 则Mi MibiMiMibi(mod mi )，即bibi(mod mi )，i1,2, k，矛盾。 定理 1 之所以称为“孙子定理” ，因为在我国古代的

12、数学著作孙子算经 （纪元前后）中已经提出了这种形式的问题，并且很好地解决了它。孙子定理 在国外文献和教科书中均称为 “中国剩余定理” ，并且在代数学中被推广成非常 般的形式。 孙子算经 中所提出的问题之一如下： 今有物不知其数， 三三数之剩二， 五五数之剩三，七七数之剩二，问物几何答曰：二十三。 用现在的记号，上述问题相当于求解同余式组 x 2 (mod 3)， x 3 (mod 5)， x 2 (mod 7) 。 孙子算经中所用的方法可以列表如下： 除数 余数 最小公倍数 衍数 乘率 各总 答数 最小答数 3 2 57 2 3522 140+63 +30=233 233- 1052=23 5

13、 3 35 7=105 73 1 2113 7 2 35 1 1512 程大位在算法统宗 （ 1593）中将这一问题的算法总结成如下歌诀： 人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。 推广为一般的列表算法： 除数 余数 最小公倍数 衍数 乘率 各总 答数 m1 b1 m=m1m2mk M1 M1 M1M1b1 k xMiMibi (mod m) i1 解 m 5 6 7 11 2310， M 1 6 7 11 462，M 2 5 7 11 385， M 3 5 6 11 330， M 4 5 6 7 210， 解同余式 462M 1 1 (mod 5) 得 M1 3 385

14、M2 1 (mod 6) 得 M2 1 330M3 1 (mod 5) 得 M3 1 210M 4 1 (mod 5) 得 M4 1 因此同余式组的解为 x 3 462 b1 1 385 b2 1 330 b3 1 210 b4 (mod 2310)。 例2 韩信点兵：有兵一队， 若列成五行纵队，则末 行一人，成六行纵队， 则末行五人，成七行纵 队，则末行四人，成十 一行纵队，则末行十人 。求兵数。 解 设兵数为 x，则 x 1 (mod 5), x 5 (mod 6), x 4 (mod 7), x 10 (mod 11) 故解为 x 3 462 1 1 385 5 1 330 4 1 21

15、0 10 6731 2111 (mod 2310)。 定理2 同余式组 x bi (mod mi )，i 1,2, , k有解的充分必要条件是 bi bj (mod (mi,mj )，i j 1,2, ,k。 若上述条件成立，则同 余式组对模 m1,m2, ,mk 有唯一解。 例3 解同余式组 x 8 (mod 15), x 3 (mod 10), x 1 (mod 8)。 解 因为 8 3(mod (15,10),8 1(mod (15,8),3 1 (mod (10,8)， 所以同余式组有唯一解 。 先解同余式组 x 8 (mod 15), x 3 (mod 10)。 由x 8 (mod

16、15)可知 x 8 15 y，代入 x 3(mod 10)得 y 1(mod 2)， 代入得 x 23 (mod 30)。 再解同余式组 x 23 (mod 30),x 1(mod 8)， 可得原同余式组的解是 x 113 (mod 120)。 另解 原同余式组可化为 8 (mod 5) 8 (mod 3) 3(mod 5)，即 3 (mod 2) 1 (mod 23) 3 (mod 5) 2 (mod 3) 1(mod 23) 由孙子定理可解得 x 113 (mod 120)。 3 质数模的同余式 本节讨论质数模的同余 式 (1) f(x) 0 (mod p)，其中 f(x) anxn an

17、 1xn 1a 0， p为质数， an 0 (mod p)。 定理1 同余式 (1)与一个次数不超过 p 1的质数模同余式等价。 证明 由多项式的带余除法可 知 f (x) (xp x)q(x) r(x)， (r(x) p 1， 由费马定理可知， x Z，有 xp x 0(mod p)，于是 f (x) r( x) (mod p)， 因此，同余式 (1)与r(x) 0(mod p)等价。 定理2 设k n，而 x i (mod p)，i 1,2, , k是(1)的k个不同的解，则 x Z，f(x) (x 1)(x 2) (x k)fk(x)(mod p)，其中fk (x)是一个 n k 次多项

18、式，首项系数为 an。 证明 由多项式的带余除法可 知 f (x) (x 1)f1(x) r，其中 f1(x)是一 个首项系数为 an的 n 1次多项式， r是一个常数， 因为f( i) 0(mod p)，所以 r 0(mod p)，于是 f(x) (x 1) f1 (x) (mod p)， 令 x i，i 2,3, ,k，则 0 ( i 1)f1( i ) (mod p)， 又 i1 (mod p )， p为质数，故 f1( i ) 0(mod p)，从而由归纳法可得结 论。 定理3 (1) x Z，xp 1 1 (x 1)(x 2) (x (p 1) (mod p)； (2) ( Wils

19、on 定理 )(p 1)! 1 0(mod p)。 证明 (1)因为 (i,p) 1，i 1,2, , p 1，所以由欧拉定理可知 1,2, , p 1都是 x p 1 1 0(mod p)的解，于是由定理 2可知 xp 1 1 (x 1)(x 2) (x (p 1) fk(x) (mod p)，fk ( x)为零次多项式， 首项系数为 1，即 xp 1 1 (x 1)(x 2) (x (p 1) (mod p)。 (2) 在 (1)中令 x 0，则 ( 1)( 2) ( (p 1) 1(mod p)， 当 p 2时，结论显然成立；当 p 为奇质数时， (p 1)! 1 0(mod p)。 定

20、理4 同余式 (1)的解数不超过它的次数 。 证明 (反证法)设 (1)的解数超过 n，则(1)至少有 n 1个解，设为 x i (mod p)， i 1,2, , n 1，于是由定理 2 可知 f (x) an(x 1)(x 2) (x n) (mod p)， 又 f( n1) 0(mod p)，故 an( n1 1)( n1 2) ( n1 n) 0(mod p)， 又因 p为质数， an 0 (mod p )，故必存在 i，i 1,2, , n，有 in 1 (mod p)， 矛盾，因此，结论成立 。 定理5 若n p，则同余式 (1)有n个解的充分必要条件是 f (x)除 xp x所

21、得余式的一切系数都是 p的倍数。 证明 由多项式的带余除法可 知 x p x f (x)q(x) r (x)， (r (x) n， 若(1)有n个解，则由费马定理可 知这 n个解都是 xp x 0(mod p)的解， 于是这 n个解也是 r(x) 0(mod p)的解，但 (r (x) n，故由定理 4可知 r(x)的 系数都是 p的倍数。 反之，若 r (x)的系数都是 p的倍数，则由费马定理 可知 f(x)q(x) 有p个不同的解 实际上是一切整数) ，假设 f (x) 的解数小于 n，而 q(x) 的解数小于等于 p n， 于是 f ( x)q(x) 0 (mod p) 的解数小于 n

22、( p n) p，矛盾，故同余式有 n个解。 质数模同余式 f (x) anxn an 1xn 1 a0 0 (mod p)，an 0(mod p) 的具体解法： 1、简化同余式，一般考虑以下简化方法： (2) 若 (f (x) p ，则可用 xp (1) 若 f (x) 的系数中有大于 p 的数，则可将其化到小于 p； x 去除 f ( x) ，则可得到一个次数较低的与 原同余式等价的同余式； (3) 若 f ( x)关于模 p有一个或几个因式，则也可将原同余式的次数降低； (4) 若 f ( x)已知有一解或几解，则可析出因式将次数降低。 2、将模的完全剩余系中的数逐一代入同余式，检验即可

23、得解。 例 解同余式 f (x) x7 2x6 7x5 x 2 0 (mod 5)。 解 化简系数，得 x7 2x6 2x5 x 2 0(mod 5)， 用x5 x去除，得 r(x) x3 2x2 x 2 0(mod 5)与原同余式等价， 将模 5的完全剩余系 2, 1,0,1,2逐一代入，知原同余式 的解是 x 1,1,2 (mod 5)。 4 高次同余式的解法 定理1 (1)设m1,m2, , mk是k个两两互质的正整数， m m1m2 mk，则 同余式 f (x) 0(mod m)与同余式组 f (x) 0(mod mi )，i 1,2, ,k等价； (2) 若Ti 表示 f (x) 0

24、(mod mi ) 对模mi的解数， i 1,2, ,k，T 表示同余式 f (x) 0(mod m) 对模 m的解数，则 T T1T2 Tk。 证明 (1)设 x0是 f (x) 0(mod m) 的解，则 f (x0) 0 (mod m) ， 由同余性质 6可知 f(x0) 0(mod mi)，i 1,2, ,k； 反之，若 x 0是同余式组 f(x) 0(mod mi)，i 1,2, , k的解，则 f (x0) 0(mod mi)，i 1,2, , k ，由同余性质 5可知 f (x0) 0(mod m)。 因此，同余式 f (x) 0(mod m)与同余式组 f (x) 0(mod

25、mi )，i 1,2, ,k等价。 (2)设 f (x) 0(mod mi )的Ti个不同的解为 x bit (mod mi )，ti 1,2, ,Ti， i 1,2, , k，则同余式组 f (x) 0 (mod mi )，i 1,2, ,k 的解即为下列同余式 组的解 xb1t(mod m1), xb2t(mod m2), xbkt(mod mk )，ti1,2,Ti， i 1,2, ,k，共有 T1T2 Tk 个同余式组，由孙子定 理可知，每个同余式组 对 模 m恰有一解，故有 T1T2 Tk个解，并且由孙子定理 之推论 2可知这 T1T2 Tk 个解对模 m两两不同余，因此， f (x

26、) 0(mod m)的解数为 T1T2 Tk。 例1 解同余式 f (x) x4 2x3 8x 9 0(mod 35)。 解 原同余式与同余式组 f (x) 0(mod 5)， f ( x) 0 (mod 7)等价， 而同余式 f (x) 0(mod 5) 的解为 x 1,4 (mod 5)， 同余式 f (x) 0(mod 7) 的解为 x 3,5,6 (mod 7)， 故原同余式有 6个解，它们分别是下列 同余式组的解： x 1 (mod 5)x 4(mod 5) x 3,5,6(mod7) x 3,5,6 (mod 7) 由孙子定理可得 6个解为： x 6,19,24,26,31,34

27、(mod 35)。 定理2 设 x x1 (mod p)，即 x x1 pt1， t1 Z 是 f (x) 0 (mod p) 的一 解，并且 p| f ( x1 )，则 x x1 pt1 恰好给出了 f (x) 0(mod p )的一解 (对模 p 来说 )： x x p t ， t Z，即 x x (mod p )，其中 x x1 (mod p )。 证明 对 作数学归纳法。 当2时，要求由 x x1 pt1 给出 f (x) 0(mod p2 )的一解，也即要求 满足 f (x1 pt1) 0 (mod p2)的t1。 由泰勒展开可知f (x1) pt1 f (x1) 0 (mod p2

28、)， f (x1 ) 于是 t1 f (x1 )1 (mod p)， p 因为 p | f1 (x)，即 (p, f1 ( x) 1，所以同余式对模 p有唯一解： t1 t1 (mod p)， 即 t1 t1 pt2，t 2 Z，代入 x x1 pt1 得 x x1 p(t1 pt2 ) x2 p 2t2，t2 Z，其中 x2 x1 (mod p)。 假设结论对之情形成立 ，即 x x1 pt1 恰好给出了 f (x) 0(mod p 1) 的 一解： x x 1 p 1t 1， t 1 Z， x 1 x1 (mod p)， 将其代入 f (x) 0 (mod p )由泰勒展开，得 1 f (

29、x 1) p t 1 f (x 1) 0 (mod p )， f (x 1 ) 于是 t 1 f ( x 1)11 (mod p)， p1 因为 x 1 x1 (mod p)，所以 f (x 1 ) f (x1) (mod p)，从而 p | f (x 1)， 故上面同余式有唯一解 ：t 1 t 1 (mod p)，即 t 1 t 1 pt ， t Z， 代入 x x 1 p 1t 1 得 f (x) 0(mod p 1) 的一解： x x 1 p 1(t 1 pt ) x p t ，t Z，其中 x x1 (mod p)。 因此，结论普遍成立。 例2 解同余式 f ( x) x4 7 x 4 0 (mod 27)。 解 首先求得