基本概念及一次同余式

1、1基本概念及一次同余式定义 设/(X)= %* + +，其中 w>O,tz,.(z = O,l,«)是整数，又设m > 0,则/(x) = 0(mod/n)(1)叫做模加的同余式。若d”M0(mod»,则叫做同余式(1)的次数。如果兀满足/(竝)三O(modm),则x三兀(mod加)叫做同余式(1)的解。不同余的解指互不同余的解。 当7及都比较小时，可以用验算法求解同余式。如例1同余式X5 + 2x4 + 2x2 -2x+3 = 0( mod 7)仅有解 x 三 1,5,6(mod 7).例2同余式x4-l = 0(modl6)有8个解x 三 1,3,5,7,9

2、,11,13,15 (mod 16)例3同余式x2 +3 = 0( mod 5)无解。定理一次同余式ar = 0 (mod /?),« x 0 (niod m)(2)有解的充要条件是仏加)血若(2)有解，则它的解数为d =(。,加)。以及当同余式(2)有解时，若兀是满足(2) 的一个整数，则它的d = (c/,7)个解是x = x0 + -k (mod m),k =-1(4)a证易知同余式(2)有解的充要条件是不定方程ax = my + b(5)有解。而不定方程(5)有解的充要条件为仏加)=仏-加)0.当同余式(2)有解时，若X。是满足(2)的一个整数，则xQ + k 三b(mod7

3、)，R = OJ,d-l下证x°+£k，R = OJ，,d l对模7两两部同余。设 axQ+k = xQ + Z:F(mod<k <d-l,<kr <d-1 aa则k = k' modJ ,k 三 k'(modd),k = k'. d dd )再证满足（2）的任意一个整数人都会与某一个Xo+k（O<k<d-l）对模加同 余。由axQ 三Z?（mod7）,aY三b（mod7）得ax=cixto（mod加）,斗人三笃X。mod7，d a d 丿(m故存在整数f使得X=X° +争.由带余除法，存在整数使得t =

4、 dq + k,O<k <d-l.于是x = xQ + （dq + k） = xQ + -k（modm）. da个解是例1求同余式故（2）有解时，它的解数为d = （a,7）。以及若是满足（2）的一个整数，则它的（亿加）x = xQ + k(mod m),k = 0、l,，d-l且由三个解。由以上初等变换还可知9x = 12（modl5）（6）9 15、r 0-3、'0-3、r 30、1 0-5 -2-5 -2>2 -5、0 1丿、31丿2 1,3>的解。解 对如卜的整数矩阵作初等列变换故（945） = 3.又因3卩2,故同余式（6）有解,9x2 + 15x(1

5、) = 3,9x(2x4)+ 15x(1)x4 = 12, 9x8 = 12(modl5).故同余式(6)的三个解为x 三 8 +号 R(modl5),k = 0,1,2.x 三 3, &13 (mod 15).例2求同余式64x = 83( mod 105)(7)的解。解 对64,105作辗转相除法。105 = 64x1 + 41,64 = 41x1 + 23,41 = 23x1 + 18,23 = 18x1 + 5,18 = 5x3 + 3,5 = 3xl + 2,3 = 2xl + l,2 = 1x2,故（64,105） = 1,同余式（7）有唯一解。由以上过程还可知l = 3

6、+ 2x(-l)= 3 +(5-3xl)x(-l)= 5x(l) + 3x2= 5x(-l)+(18-5x3)x2= 18x2 + 5x(-7)= 18x2+(23-18xl)x(-7)= 23x(-7)+ 18x9= 23x(-7)+(41-23xl)x9= 41x9 + 23x(-16)= 41x9 + (64-41xl)x(-16)= 64x(-16) + 41x25= 64x(-16) + (105-64x1)x25= 105x25 + 64x(-41)105x25 + 64x(-41) = 1, 105x25x83 + 64x(-41)x83 = 83, 64x(-3403)= 83

7、(modl05).故同余式(7)的解为x 三-3403 (mod 105)即x = 62(modl05).习题1. 求卞列同余式的解：(i ) 256.v = 179(mod337).( ii ) 1215% = 560(mod 2755).(iii) 1296x = 1125(inod935).解(i )因公6337、"25681、<1381、101-14-1、°1Z< 0丿-31/r133、< 13、(10、4-25104-25104*厂319 ；/L7919丿-79*/故(256,337) = 1,于是该同余式有解，且对模337有唯一解。并且 256

8、x104 + 337x(79) = 1,256 x (104 x 179)+ 337 x (-60)xl79 = l 79,256x(104x179)= 179(mod337),但是104x179 = 18616三81(mod 337),故256x81 = 179(337).于是该同余式的唯一解为 x = 81(mod337).(ii)由辗转相除法，可得(1215,2755) = 5,5|560,故该同余式有解.由辗转相除法，还可得1215-(-195) + 2755-86 = 5,在这个等式两边同时乘以112,得1215 (-21840) + 2755 - 9632 = 560.故 1215

9、-(-21840)三 560(mod 2755).因-21840 三 200(mod 2755),故 1215-200 = 560(mod 2755).故该同余式的全部解为2755x 三 200 +k(mod 2755), R = 0,1, , 4.即x = 200,751,1302,1853,2404(mod 2755).2. 求联立同余式x+4y29 三 0 (mod 143), 2x 一 9y+84 = 0( mod 143) 的解。解 由同余式x+4y-29 = 0(mod 143)得x = -4y+29 (mod 143)代入同余式2x - 9y + 84 三 0 (mod 143)

10、得2 (4y + 29)一 9)，+ 84 三 0( mod 143),-17y + 142 = 0(modl43),17y = -l(modl43).对17,143做辗转相除法。因143 = 17x8 + 7,17 = 7x2 + 3,7 = 3x2 + l,3 = 1x3,故(17,143) = 1,且l = 7 + 3x(-2)= 7 + (17-7x2)x(-2)= 17x(-2)+7x5= 17x(-2)+(143-17x8)x5= 143x5 + 17x(-42).故143x5 + 17x(-42) = 1,17x(-42) = l(modl43),17x42 = -l(mod 1

11、43).故由 17y = -l(modl43)可得y = 42 (mod 143).由 y 三 42(mod 143)及 x+4y 29三 0(mod 143)得“4x42-29 三 0(modl43),x = 4( mod 143).于是可得，该联立同余式的解为x = 4 (mod 143), y = 42 (mod 143).3. ( i )设加是正整数,(a,用)= 1,证明x三防仇"”T(mod加)是同余式ax三Z?(mod m)的解。(ii)设p是质数，Ovovp,证明x 三( l) (/i + l)(mod 卩)a是同余式ax = b(mod p)的解。证(i )因加是正

12、整数，(。,加)=1,故同余式妙三b(mod加)有唯一解。由欧拉定理得 ciba1 = bcF"" =Z?(mod/w).故x三baQm1是同余式av三b(mod m)的解°(ii)因卩是质数，Ovavp,故(a,p) = l,同余式ax = Z?(mod p)有惟一解。因(« l)!|(p l) (/? « +1),故(-l)a_1(p _ 1)(p - a +1)三(a 1) !(mod(<7 _ 1)!).易知(-l)E(p 一 1)(一 a +1) (a 1)!三(一 1)1(一 1)(一 (a 一 1) = (a-l)!(mod p).而一1儿p) = l,故(-1)"1 (卩 一 1) (p a +1)三(a 1) !(mod pa 一 1)!).因此(-