初等数论第四章同余式

《初等数论第四章同余式》由会员分享，可在线阅读，更多相关《初等数论第四章同余式（15页珍藏版）》请在装配图网上搜索。

1、第四章 同余式1 基本概念及一次同余式初等数论中的一个基本课题是研究同余式(同余方程)的求解问题。定义1 设m e Z +, f (x) = a其中a e Z,贝Inn-10if (x)三0 (mod m)称为模m的同余式。若a丰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，都能使 af (a)三0 (mod m)成立，故把K中的一切数，即x三a (mod m)作为一个解。a定理 设(a,m) = d

2、则一次同余式ax三b (mod m)有解的充分必要条件是 d I b。当此条件成立时，同余式共有d个解，它们是x 三 x + k -m (mod m)， 0dk = 0,1,d 1,其中x是同余式ax三b (mod m)的任一个解。0证明同余式ax三b (mod m)有解o不定方程ax + my = b有解o d I b。因为不定方程ax + my = b的一切整数解为x = x + mt， t e Z,所以,同余式解数为d。0dax 三 b (mod m)的解为 x 三 x + k (mod m), k = 0,1,d 1,0d注 当(a,m) = 1时，一次同余式有唯一解x三a車)-ib

3、(mod m)。同余式的解法1、代入法(适用于模较小时)例1解同余式3x三1 (mod 17) 解 因为(3,17) = 1,所以同余式有唯一解，以17的完全剩余系逐一代入，得x三6(modl7)。2、公式法(适用于模较小时)例2 解同余式 8x三9 (mod 11)解 因为(8,11) = 1，所以同余式有唯一解，从而，x 三 8車11)-1 9 三 810-1 9 三(-3)9 - (一2)三(-2)4 - 6 三 5 - 6 三 8 (mod 11)。3、变换系数法例3 解下列同余式(1) 4x 三 1 (mod 15)；(2) 14x 三 27 (mod 31)；(3) 103x 三

4、57 (mod 211)。解 因为(4,=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)。因为(103,211) = 1,所以同余式有唯一解，由 103x 三 57 (mod 211) 可得 206x 三 114 (mod 211)，于是 5x 三 114 (mod 211)即 5x 三 97 (mod 211)，再由 5x 三 97 (mod

5、211) 可得 210x 三 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)方便，而且若y是(2)的解，贝吐=耳竺是(1)的解。00a例4 解同余式 863x三880 (mod 2151)解 因863是质数，且863 J2151，故(863,2151) = 1,从而同余式有唯一解,原同余式可化为 863x = 880 + 2151y，模863

6、后得 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 = 1,06 + 85 -1176 + 863 - 7“z = 7, y = 69,013085880+ 215169863即x三173 (mod 2151)是原

7、同余式的解。5、辗转相除法例5 解同余式 863x三880 (mod 2151)解 因为(863,2151)=1,所以同余式有唯一解 利用辗转相除法可得-496 863 +199 2151 = 1, 模 2151 后得 496 863 三 1(mod2151), 所以 x 三496 880 三 173 (mod 2151)。例6解同余式6x三15 (mod 33)解 因为(6,33) = 3115,所以同余式有3个解， 由原同余式可得 2x三5 (mod 11),解得 x三8 (mod 11), 因此原同余式的解为 x三8, 19, 30(mod33),。2 孙子定理本节讨论同余式组 x三b

8、(modm ), x三b (modm ), x三b (modm )1 1 2 2 k k的求解问题。定理1(孙子定理)设m ,m，,m是两两互质的正整数，m = mmm ,1 2 k 1 2 km = mM , i = 1,2,k,则同余式组 x 三b (modm ), x三b (modm ),i i1122x三b (modm )的解是 x三M Mb + M Mb HbM Mb (modm),kk11 122 2k k k其中 M M 三 1 (mod m ), i = 1,2,k。i ii证明 因为(m ,m ) = 1, i丰j所以(m ,M ) = 1,于是 M x三1 (mod m )

9、i ji iii有一解，设为 M，贝9 M M 三 1 (mod m ), i = 1,2,k,ii ii又因为 m = m M，所以 m IM , i丰ji ij irrrf于是 M M b + M M b Hb M M b 三 M M b 三 b (mod m ),11 122 2k k ki i i ii故 x三M Mb + M M b + M M b (modm) 是原同余式组的解。11 122 2k k k若x ,x是适合同余式组的任意两个整数，12贝9 x 三 x (mod m ), i = 1,2,，k, 于是 x 三 x (mod m),12i12fff因此，原同余式组只有一个

10、解x三M M b + M M b + bM M b (mod m)。11 122 2k k k推论1设正整数m ,m，,m两两互质，则同余式组1 2 kax三b (modm ),a x三b (modm ),a x三b (modm )1 1 1 2 2 2 k k k有解的充分必要条件是同余式ax三b (mod m ), i = 1,2,k有解。 iii证明 必要性是显然的，下证充分性。因为对i = 1,2,k，同余式a x三b (mod m )，所以d I b，这里d = (a ,m )，iiii iii i于是有ci使”三1(mod沪，从而原同余式组等价于iix 三 c 廿(mod i),

11、x 三 c犷(mod1dd2 d1 1 2手)，,x三c冷(mod)，当然有解。2kk推论2若b , b ,b分别通过模m , m ,m的完全剩余系，则12k12kfffx 三 M M b + M M b HF M M b (mod m)11 122 2k k k通过模m = m mm的完全剩余系。12k证明 令x =工M M b，贝Ijx过m mm个数，这m个数两两不同余。0i i i012k这是因为若工M M bi i ii=1i=1ZffM M b (mod m)，i i ii=1i = 1,2,k,矛盾。fffff/则 M M b 三 M M b (mod m )，即 b 三 b (m

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

13、X7235X2X2140+63+30=233233-105X2=23537X3121X1X3723X5115X1X2程大位在算法统宗(1593)中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。推广为一般的列表算法：除数余数最小公倍数衍数乘率各总答数m1b1m二吧mkM1M1MM b1 1 1x 三乞 M M b (mod m)iiir=111234解 m = 5 - 6 - 7 -11 = 2310, M = 6 - 7 -11 = 462, M = 5 - 7 -11 = 385,12M 二 5 6 11 二 330, M 二 5 6 7 二

14、 210, 34f得M = 31f得M = 12f得M = 13f得M = 14f解同余式 462M 三1 (mod 5)1f385M 三 1 (mod 6)2f330M 三 1 (mod 5)3f210M 三 1 (mod 5)4因此同余式组的解为x 三 3-462-b1+1 - 385 - b +1 - 330 - b +1 - 210 - b (mod 2310)。234例2 韩信点兵：有兵一队,若列成五行纵队,则末行一人,成六行纵队, 则末行五人,成七行纵队,则末行四人,成十一行纵队,则末行十人。求兵数解 设兵数为x,贝Vx 三 1 (mod 5), x 三 5 (mod 6), x

15、三 4 (mod 7), x 三 10 (mod 11) 故解为 x 三 3 - 462 -1 +1 - 385 - 5 +1 - 330 - 4 +1 - 210 -10 三 6731 三 2111 (mod 2310)。定理2同余式组x三b (mod m ), i = 1,2,k有解的充分必要条件是iib 三 b (mod (m , m ), i 丰 j = 1,2,k。i ji j若上述条件成立，则同余式组对模m ,m ,m 有唯一解。12k例3 解同余式组 x 三 8 (mod 15), x 三 3 (mod 10), x 三 l(mod8)。解 因为 8 三 3(mod (15,10

16、),8 三 1(mod (15,8),3 三 1(mod (10,8), 所以同余式组有唯一解。先解同余式组 x三8 (mod 15), x三3 (mod 10)。由x 三 8 (mod 15)可矢口 x = 8 +15y,代入x 三 3 (mod 10)得 y 三 1 (mod 2), 代入得 x三23 (mod 30)。再解同余式组 x三23 (mod 30), x三1 (mod 8),可得原同余式组的解是x三113(mod120)。另解 原同余式组可化为x 三 8 (mod 5)x 三 3 (mod 5) x 三 2 (mod 3)x 三 1 (mod 23)x 三 8 (mod 3)

17、x 三 3 (mod 5)，即x 三 3 (mod 2)x 三 1 (mod 23)由孙子定理可解得x三113(mod120)。3 质数模的同余式本节讨论质数模的同余式(1)f (x)三 0 (mod p),其中f (x) = a xn + a xn-i hb a , p为质数，a 丰 0 (mod p)。nn-10n定理1同余式与一个次数不超过p -1的质数模同余式等价。证明 由多项式的带余除法可知f (x) = (xp - x)q(x) + r(x)， d(r(x) p -1, 由费马定理可知，Vx g Z,有 xp 一 x三0 (mod p),于是 f (x)三r(x) (mod p)，

18、 因此，同余式与r(x)三0 (mod p)等价。定理2设k n,而x = a (mod p), i = 1,2,k是的k个不同的解，贝ViVxg Z, f (x)三(x-a )(x-a )(x-a )f (x) (mod p),其中f (x)是一个n k12k kk次多项式，首项系数为a。n证明 由多项式的带余除法可知f (x) = (x-a )f (x) + r,其中f(x)是一1 1 1个首项系数为a的n -1次多项式，r是一个常数，n因为/(a )三 0 (mod p), 所以 r 三 0 (mod p),于是 f (x)三(x -a )f (x) (mod p),i11令 x = a

19、 , i = 2,3,k,贝U 0 三(a -a )f (a ) (mod p),ii 11 i又a羊a (mod p), p为质数，故f (a )三0 (mod p从而由归纳法可得结论。i 11 i定理3 (1) Vx g Z, xp-1 一 1 三(x 一 1)(x 一 2)(x - (p 一 1) (mod p)；(2) (Wilson 定理)(p 一 1)!+1 三 0 (mod p)。证明 因为(i, p) = 1, i = 1,2,p -1,所以由欧拉定理可知1,2,p -嘟是xp-1 -1三0 (mod p)的解，于是由定理2可知xp-1 一 1 三(x 一 1)(x 一 2)(

20、x - (p 一 1)f (x) (mod p), f (x)为零次多项式，kk首项系数为1,即 xp-1 一 1 三(x 一 1)(x 一 2)(x - (p 一 1) (mod p)。(2)在(1)中令 x = 0,贝9(-1)(-2)(-(p 一 1)三一1(mod p),当p = 2时，结论显然成立；当p为奇质数时，(p -1)!+1三0 (mod p)。定理4 同余式(1)的解数不超过它的次数。证明(反证法)设的解数超过n,则至少有n +1个解，设为x = a (mod p), i = 1,2,n +1,于是由定理2可知if (x)三 a (x-a )(x-a )(x-a ) (mo

21、d p)，n 12n又 f (a )三 0 (mod p),故 a (a -a )(a -a )(a -a )三 0 (mod p)，n十1n n十11 n十12n十1n又因p为质数，a = 0 (mod p),故必存在a， i = 1,2,n,有a =a (mod p)，niin 十 1矛盾，因此，结论成立。定理5若n p,则同余式有n个解的充分必要条件是f (x)除xp -x所 得余式的一切系数都是p的倍数。证明 由多项式的带余除法可知xp -x = f (x)q(x) + r(x), d(r(x) n, 若有n个解，则由费马定理可知这n个解都是xp -x三0 (mod p)的解， 于是这

22、n个解也是r(x)三0 (mod p)的解，但6(r(x) p，则可用xp - x去除f (x),则可得到一个次数较低的与 原同余式等价的同余式；(3)若f (x)关于模p有一个或几个因式，则也可将原同余式的次数降低； 若f (x)已知有一解或几解，则可析出因式将次数降低。2、将模的完全剩余系中的数逐一代入同余式，检验即可得解。例 解同余式 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

23、 5)与原同余式等价，将模5的完全剩余系-2,-1,0,1,2逐一代入，知原同余式的解是x三-1,1,2 (mod 5)。4 高次同余式的解法定理1设m , m，,m是k个两两互质的正整数，m = mmm，贝V12k12k同余式f (x)三0 (mod m)与同余式组f (x)三0 (mod m ), i = 1,2,k等价；i(2)若T表示f (x)三0 (mod m )对模m的解数，i = 1,2,k， T表示同余式iiif (x)三0(mod m)对模m的解数，则T = TT -T。1 2 k证明 设x是f (x)三0 (mod m)的解，则f (x )三0 (mod m)，00由同余性

24、质6可知f (x )三0 (mod m )， i = 1,2,k；0i反之，若x是同余式组f (x)三0 (mod m )， i = 1,2,k的解，则0if (x )三 0 (mod m )， i = 1,2,k，由同余性质5可知 f (x )三 0 (mod m)。0i0因此，同余式/(x)三0 (mod m)与同余式组/(x)三0 (mod m )， i = 1,2,k等价。i(2)设f (x)三0 (mod m )的T个不同的解为x三b (mod m )， t = 1,2,T，iiiti iiii = 1,2,k,则同余式组f (x)三0 (mod m )， i = 1,2,k的解即为

25、下列同余式i组的解 x 三 b (mod m ), x 三 b (mod m )，,x 三 b (mod m )， t = 1,2,T，1t12t2ktk ii12ki = 1,2,-,k,共有TT个同余式组，由孙子定理可知，每个同余式组对1 2 k模m恰有一解，故有TT丁个解，并且由孙子定理之推论2可知这TTT1 2 k1 2 k个解对模m两两不同余，因此，f (x)三0(mod m)的解数为TT -T。1 2 k例1 解同余式 f (x) = x 4 + 2 x 3 + 8 x + 9 三 0 (mod 35)。解 原同余式与同余式组f (x)三0(mod5), f (x)三0 (mod7

26、)等价，而同余式 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 (mod 7) x 三 3,5,6 (mod 7)由孙子定理可得6个解为：x三6,19,24,26,31,34 (mod 35)。定理2 设 x 三 x (mod p),即 x = x + pt, t e Z 是 f (x)三 0 (mod p)的一1 1 1 1f解，并且p J f (x )，则x = x + p

27、t恰好给出了 f (x)三0 (mod pa)的一解(对模1 1 1pa 来说)：x = x + pat , t e Z, 即卩 x 三 x (mod pa)，其中 x 三 x (mod p)。aa aaa 1证明对a作数学归纳法。当a = 2时，要求由x = x + pt给出f (x)三0 (mod p2)的一解，也即要求 11满足 f (x + pt )三 0 (mod p2)的t。1 1 1由泰勒展开可知f (x ) + pt f (x )三0 (mod p2)，1 1 1于是 t f(x )三 _ i)(mod p)，11pfff因为p J f (x)，即(p, f (x) = 1所以

28、同余式对模p有唯一解：三t (mod p)，1 1 1 1f即 t = t + pt， t e Z，代入 x = x + pt 得1 1 2 2 1 1fx = x + p(t + pt ) = x + p21， t e Z,其中 x 三 x (mod p)。1 1 2 2 2 2 2 1假设结论对之情形成立，即x = x + pt恰好给出了 f (x)三0 (mod pa-1)的11一解：x = x + pa-it ， t e Z， x 三 x (mod p)，a-1a-1 a-1a-11将其代入f (x)三0 (mod pa)由泰勒展开，得f (x ) + pa-1t f (x )三 0

29、(mod pa )，a -1a -1a -1于是 t f(x )三-/a-1)(mod p)，a -1a -1p a -1,f因为 x 三 x (mod p )，所以 f(x )三 f(x ) (mod p),从而 p J f (x )，a -11a -11a -1故上面同余式有唯一解:： 三t(mod p),即t = t + pt , t e Z,a -1 a -1a -1 a -1a a代入 x = x + pa-1t 得 f (x)三 0 (mod pa-1)的一解：a -1a -1fx = x + pa-1 (t+ pt ) = x + pat , t e Z,其中 x 三 x (mo

30、d p)。a -1a -1aaa aa 1因此，结论普遍成立。例2 解同余式 f (x) = x 4 + 7 x + 4 三 0 (mod 27)。解首先求得f (x)三0 (mod 3)的解为x三1 (mod 3),并且f丰0 (mod 3)；将x = 1 + 3t代入f (x)三0 (mod 9)得到f+ 3t f三0 (mod 9),艮卩113 + 6t 三 0 (mod 9),解得 t 三 1 (mod 3)，11令 t = 1 + 3t，则 x = 1 + 3t = 1 + 3(1 + 3t ) = 4 + 9t 是 f (x)三 0 (mod 9)的一解;1 2 2 1 2 2将

31、x = 4 + 9t 代入 f (x)三 0 (mod 27)得到 f (4) + 9t f(4)三 0 (mod 27)，2 2 2即 18 + 180t 三 0 (mod 27)，解得 t 三 2 (mod 3)，22令 t = 2 + 3t，则 x = 22 + 27t 是 f (x)三 0 (mod 27)的一个解，2333因此，原同余式的解为 x三22 (mod 27)O例3 解同余式 f (x) = x3 - 2x + 6三0(mod53)。先讨论x三1 (mod 5),将x11得 f + 5t f (1)三 0 (mod 52)，即1令 t =-1 + 5t，贝y x =-4 +

32、 25t ,1 2 2 2解 首先求得f (x)三0 (mod 5)有两个解：x三1,2 (mod 5)。=1 + 5t 代入 f (x)三 0 (mod 52)三-1 (mod 5)，15 + 5t 三 0 (mod 52)，解得 t1将 x =-4 + 25t 代入 f (x)三 0 (mod 53) 22得 f (-4) + 25t f (-4)三 0 (mod 53),卩卩一50 + 25 - 46t 三 0 (mod 53)，22解得 t 三 2 (mod 5),令 t = 2 + 5t，则223是f (x)三0 (mod53)的一个解；x = 46 + 125t，即 x 三 46 (mod 53)33ff再讨论 x 三 2 (mod 5),将 x = 2 + 5t 代入 f (x)三 0 (mod 52)1 1 1得 f (2) + 5t f (2)三 0 (mod 52),卩卩 10 + 50t 三 0 (mod 52),此同余式无解; 11因此，原同余式的解为x三46 (mod 53)。解法总结：Vm e Z+, m = ppa2pak，要解同余式 f (x)三0 (mod m),只需解12kf (x)三0 (mod pa,.), i = 1,2,k,从而转化为解质数模的同余式。i