《初等数论第四章同余式》由会员分享，可在线阅读，更多相关《初等数论第四章同余式（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 三 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同余式组
