(解答題36道)第四章同余式

1、第四章同余式三、解答題1、設 ( a, m)1 ，k 與 m 是正整數， 又設 x0ka(mod m) ，證明同余方程 xka(mod m) 的一切解 x 都可以表示成xyx0 (mod m) ，其中 y 滿足同余方程 yk1(mod m) 。ka(mod m) 的任意一個解，解：設 x1 是 x0則一次同余方程yx0 x1 (mod m) 有解 y ，再由 yk ayk x0k( yx0 )kx1ka(mod m)得 yk1(mod m) ，即 x1 可以表示成 xyx0 (mod m) ，其中 y 滿足同余方程yk1(mod m) ；反之，易知如此形式的x 是xka(mod)m 的解。2、

2、解同余方程組3x1 mod104x7 mod153x1 mod 2 ,解：這同余方程組的解與同余方程組3x1 mod5 ,4x7的解相同，mod3 ,4x7 mod5但第二個同余方程3x 1 mod5 可化為 x 2 mod5,第四個同余方程 4x7 mod5 可化為 x2 mod5,與 x2mod5矛盾，所以原同余方程組無解 .3、設素數 p2 , 求同余方程 x21 mod pl的解解：同余方程可寫為x1 x10 mod pl由于x1, x1| 2 , 所以上式等價于x1 0 mod pl或 x1 0 mod pl.因此，對任意的 l1解為 x 1,1 mod pl解數為 2.4、求同余式

3、 f (x) x34 x25x 6 0(mod 27)解： f ( x) 0(mod3),f ( x)0(mod3) 無公解20 有唯一解 x 0(mod3)以 x3t1 代入 f ( x) 0(mod9) 得 f (0) 3t1 f (0) 0(mod9)但 f(0)3(mod9) ， f (0)5(mod9)故 36t10(mod 9) ，12t20(mod 3) ， t11(mod3)因此 t1 13t2 , x 39t2 是 f ( x)0(mod9)的唯一解將 x39t 2 代入 f ( x)0(mod 27)得 f (3)9t2 f (3)0(mod 27)但 f(3)0(mod

4、27) ， f(3)8(mod 27)故 89t20(mod 27) ， 8t20(mod3) ， t20(mod3)設 t23t3 , x 3 27t3 , x3(mod 27) 是 f ( x)0(mod27) 的唯一解。5、 45 x21(mod132) .解： 因為 (45,132) 3, 所以同余式有3個解.將同余式化簡為等價的同余方程15x7(mod 44) .我們再解不定方程15 x 44 y7 ,得到一解 (21,7) .于是定理 4.1中的 x0 21 .因此同余式的3 個解為x21(mod 132) ,21 132 (mod132) 65(mod132) ,3132x212

5、(mod132)109(mod132) .3.6、 111x75(mod321) .解：因為 (111,321)3, 所以同余式有3 個解 .將同余式化簡為等價的同余方程37x25(mod107) .我們再解不定方程37 x107 y25 ,得到一解 ( 8,3) .于是定理 4.1 中的 x08 .因此同余式的3 個解為x8(mod 321) ,8 321(mod 321) 99(mod 321) ,3x82321(mod 321) 206(mod 321) .3x1(mod 7)7、 x2(mod 8) .x3(mod 9)解:因為 (7,8,9)=1,所以可以利用定理5.1. 我們先解同

6、余式72x1(mod 7), 63x1(mod 8), 56x1(mod 9) ,得到 x1 4(mod 7), x21(mod 8), x34(mod 9) . 于是所求的解為x724163(1)256( 4)3(mod 494)510(mod 494)478(mod 494).8、判定 2x3x23x 10 mod5 是否有 3 個解解： 2x3x23x10 mod5 等價于 x33x24x3 0 mod5，又 x5xx33x24x3 x23x 56x212x 15 ，其中 rx6x212x15的系數的都不是5 的倍數，故方程沒有3 個解9、解同余式9x5(mod 25).解： 9x 5(

7、mod 25)18x10(mod 25)7 x10(mod 25)4x5(mod25)x5(mod 25)10、同余方程 5x26x49 0(mod 60) 的解的個數 .解：因為603 45所以5x2等價于6x 49 0(mod60)25x6x490(mod3)（ 1）26x490(mod4)5x（ 2）25x6x490(mod5)（ 3）解同余方程（ 1）（ 2）（ 3）得到11x11x21(mod3)22x11x21(mod4)3x1(mod5)1所以原方程的解得個數有2*2*1=4 個。11、解同余式8x9(mod11)解： Q (8,11)1同余式只有一個解11 是素數9 8912、

8、解同余方程組108(mod11)2(mod 3)3(mod 5)2(mod 7)解：利用孫子定理有，m357105, M 135 , M 221, M 315.35M1(mod3)2(mod3)1M 121M21(mod5)M 21(mod 5)15M 31(mod 7)M 31(mod 7)x0235232112151(mod105)23(mod105)13、求整數 n ，它被 3， 5， 7 除的余數分別是1，2， 3。n1(mod 3)解： n 是同余方程組n2(mod 5) 的解 .n3(mod 7)在孫子定理中，取m13, m2 5, m37, m345 105，M 135,M 22

9、1,M 315,M 11,M 21,M 31,則 n 1 35 (1)2 211 315152(mod105)因此所求的整數n52105t ,tz.x3 mod814、求x5 mod3 的解x7 mod5解： M235 30；M 13 5 15而M1M11 mod2 所以 M 11 mod2同理 M210而M2M 21 mod3 所以 M 21 mod3M 36，而 M3 M31 mod5 所以 M 31 mod5.3所以x0M i M i 1 15 3 1 10 5 1 6 7 17 mod 30i 11(mod 3)1(mod 5)15、解同余方程組2(mod 7)2(mo11)解：取 m

10、13, m25, m37, m411 ，都是素數，滿足條件。M1 5 7 11,M2 3 7 11,M33511,M4 357我們來求 M j1.由于 M1 (1) (1) (1)1(mod 3) 知，1M 1M11M 11 (mod 3) ，因此可取 M 111.由M2 (2) (2)11(mod5) 知，1M2M21M 21 (mod 5)因此可取 M 211，由 M33 5 44(mod 7) 知，1M3M314M31 (mod 7)因此可取 M 312.由M 43 5 74 7 6(mod11) 知，1M4M416M41(mod11)因此可取 M 412 .所以同余方程的解為：x(5

11、7 11) 1 1(3 7 11) 1 ( 1)(3 5 11) 2 2(3 5 7) 2 ( 2)(mod35 7 11)，即 x 385 231 660 420 394(mod1155)16、解同余方程 x42x38x90 mod351解：因為 355 7 ，所以同余方程1 等價于同余方程組x42x38x90 mod52.x42x38x90 mod73分別解同余方程2 ，3 得到解x111, x214 mod5x123,x225, x326 mod7這樣，同余方程1 的解 x可由下面的方程組決定：xa1 mod5 , x a2mod7其中 a1 1或 4 ， a23 或 5 或 6 . 利

12、用孫子定理，取m15, m27, m 35M17, M25,7M 11 mod5 ,5 M 21 mod7M 13,M23則 x 21a1 15a2 mod35將 a1，a2所有可能的取值代入上式，得到方程 1 的全部解是x121 115 331 mod 35x221 115 526 mod 35x321 115 66 mod 35x421 415324 mod 35x521 415519 mod 35x621 415634 mod 3517、解同余式8x9 mod11解： Q 8,111同余式只有一個解Q 11 是素數10 x989（8 mod11）.18、解同余方程：31x5 mod17解

13、 ： 若 fx0 modm， 則 fx0b xb xmod m成立，反之，若000f x0b x0b x0mod m ，則 fx00 mod m成立；19、解同余方程 3x144x106x 180(mod 5).解：由 Fermat 定理得， x5x(mod5), 因此，原同余方程等價于2x2x30(mod 5)將 x 0,1,2(mod5)分別代入方程 2x2x 30(mod 5) 中進行檢驗，可得原同余方程的解是： x1(mod5)20、解同余方程 x32x120（mod81 ）解：方程x32x12有一解x0 mod3，（0 mod3）故 x3t1 ， fxx3 -2x 12 ， fx3x

14、2 -2 ， f (0)12 ,f (0)2解 1223t10(mod 32 ) ，得 t 12(mod3 2 ) ，t123t 2， x632 t2 ， f (6)216， f (6)106 ,解 216106233故 t23t 3 ， x633 t20(mod3 ) ，得 t 20(mod3 )3 t 3 ，再解 21610633t30mod34 ，得 t 3 1 mod34故 t31 3t 4 , x 33 34t 4原方程的解為x33 mod8121、 1、求同余方程9x o 6(mod15) 的所有解 .解：因為 (9,15)3 且 3整除 6所以同余方程9x o6(mod15) 恰

15、有三個解 .先求同余方程3x o 2(mod5) 的唯一解，顯然.3x ? 210 漢12(mod5), x4(mod5)所以原同余方程9x o 6(mod15) 的三個解為x 漢 4(mod15), x9(mod15), x ? 14(mod15)2、求一次同余方程組x o 2(mod 35)?y o 9(mod14)?z o 7(mod 20)?解：由于 35 、 14、 20 兩兩不互質，所以不能直接用孫子定理，原一次同余方程組與一o2(mod5)?o2(mod 7)?o?9(mod 2)次同余方程組?等價?o9(mod 7)x?o7(mod 4)?x?o7(mod5)?x顯然，去掉相同

16、的一次同余方程后，此一次同余方程組又與一次同余方程組x o 2(mod 5)?x o 2(mod 7)?x o 7(mod 4)?x o 2(mod 5)?同余方程組 x o 2(mod 7) 等價?x o 7(mod 4)?此時5、7、4兩兩互質，由孫子定理知，原一次同余方程組有唯一解m = 5創(chuàng)74= 140,M1=7?428,M 2= 5? 420,3= 5?735,mi),1i 3, iNMMiMi 海1(mod,求得M1= 2,M2= 6,M3= 3所以 x 捍 228? 22創(chuàng)206 + 7創(chuàng)353 漢1087107(mod140) 為原一次同余方程組的解 .3、解同余方程組3x5

17、y1 mod 72x3 y2 mod 7解: 19 y4 mod7.5 y4 mod7y2 mod7再代入 3x5 y1 mod73x101 mod7x4 mod7即方程組的解是x4, y2 mod74、解同余方程6 x7 mod23 .解：6x7 mod235x732 mod233x248 mod232x8710 mod23x5 mod235、 解同余式 .12x150(mod15)解：因為12,453 5 , 所以同余式有解 , 而且解的個數為3.又同余式等價于4x50(mod15 即 4x515 y .我們利用解不定方程的方法得到它的一個解是10,3 ,即定理 4.1 中的 x010 .

18、因此同余式的3個解為x10 mod45,x1045 mod 4525 mod253x 10245 mod4540 mod253,.6、韓信點兵：有兵一隊，若列成五行縱隊，則末行一人，成六行縱隊，則末行五人，成七行縱隊，則末行四人，成十一行縱隊，則末行十人，求兵數.解： xb1 (mod5), xb2 (mod 6), xb3 (mod 7), xb4 (mod11) ，此時：.m 5 6 7 112310M 16711462M 25711385M 35 611330M 45 6 7210M i M i 1(mod mi ), i1,2,3, 4得M 1 =3,M 2 =1,M 3 =1,M 4

19、 =1故： x 3462b1 385 b2330 b3210 b4 (mod 2310)又 Q b11,b25, b3 4, b4 10 x3462 1385 53304210 1067312111(mod 2310)7、解同余方程x53x140(mod 45) .解：原同余方程等價于同余方程組x53x140(mod 9) ，(1)x53x140(mod 5) .(2)先解同余方程(1).容易驗證，同余方程x53x140(mod3) 的解是 x2(mod3) .令 x23t 并代入方程 (1) ，得到(23t) 53(23t) x140(mod 9) ，(3)容 易 看 出 ， 這 是 一 個

20、 對 于 任 何 整 數 t 都 成 立 的 同 余 式 ， 所 以， 方 程 (3) 的 解 是t0,1,2(mod3) ，于是方程 (1) 的解是.x 2,5,8(mod9) .(4)再解同余方程(2).用 x0,1,2,3,4 去驗證，得到 (2) 的解是x1,2(mod5) .因此，原同余方程的解是下面六個同余方程組的解：xa1 (mod9), a12,5,8 ，xa2 (mod5), a21,2.利用孫子定理解這六個方程組，記m19, m25,m45, M 15, M 29, M 12, M 21則10a1 9a2 (mod 45) .將 a1 和 a2 的不同取值代入，得到所求的解

21、是x110.29.111(mod 45) ，x210.29.22(mod 45) ，x310.59.141(mod 45) ，x410.59.232(mod 45) ，x510.89.126(mod 45) ，x610.89.217(mod 45) .8、解同余方程5x26x490(mod 60) .（理由：考察孫子定理，解同余方程組. ）解：因為 603 4 5 ，所以，原同余方程等價于同余方程組5x26x490(mod 3)LL L15x26x490(mod 4)L L L25x26x490(mod 5)LL L3分別解同余方程1,2,3 ，得到解11x11,x21(mod3),22x11

22、,x21(mod4),3x11 mod5這樣，原同余方程的解可由下面的方程組決定：a1 mod3a2 mod 4a3 mod5其中 a11, 1;a21, 1;a31. 利用孫子定理，令m13, m24, m35, m60M 120,M 215,M 312M 12,M 21,M33則x40a115a236a3 (mod 60)將 a1 , a2, a3 所有可能的取值帶入上式，得到原方程的全部解是x140115136 11(mod60)x140(1)15136119(mod 60)x140115(1)361 31(mod 60)x140(1)15(1)36 111(mod 60)9、判定同余方

23、程 2x33x10(mod 7) 是否有三個解 .（理由：考察素數模的同余方程的解的個數，應用第四節(jié)的Fermat 定理及定理4. ）解：因為 241 mod7 ，所以，原方程與4 2x34 3x40(mod 7)即 x32x30(mod 7) 等價 .由于 x7xx32x 3 x42x23x 412x216x12 ，所以，由定理4 可知，原方程的解數小于3 .10、有一對士兵，若三人一組則余一人，若五人一組，則余2 人，若十一人一組，則余3人，已知這對士兵不超過170 人，問這對士兵有幾人？解：設士兵有x 人，則由題意得x1(mod 3) ， x-2(mod 5)x 3( mod 11) 由

24、孫子定理得 x58(mod 165)故 x58人.12、求一個最小的自然數n，使得它的 1 是一個平方數，它的1 是一個立方數， 它的 1 是一個5次方數.235解：可設 n2 3 5y ，由條件得1 mod2 ,0 mod3 ,0 mod5 ;0 mod2 ,1 mod3 ,0 mod5 ;0 mod2 ,0 mod3 ,mod5 ,由孫子定理得15 mod30 ,10mod30 ,6 mod30 , 故 n15106.2 3 53x5y1 mod 713、解同余方程組2x3 y2 mod 7解： 19y4 mod75 y4 mod7y2 mod7再代入 3x5y1 mod73x101 mo

25、d7x4 mod7即方程組的解是x4, y2 mod714、證明不定方程x13x32x339x44沒有整數解 .證明：取 m 9. 因為 x130 ， 1(mod9) ，于是同余式3334(mod 9)x1x2x3無解，由此知原方程無整數解.15、解同余方程 fx3x24x15 0 mod75.解：因753 52， 先 解 fx0 mod3， 用 逐 一 代 入 法 得 解 x 0 mod3； 再 解fx0 mod52，用逐一代入法得fx0mod5的解 為 x0,2 mod5 ， 對于x0mod5， 令 x5t代 入fx0mod25得 t2 mod5， 于 是x5 2 5t21025t 2 ，

26、即 x10mod25是 f x0 mod25 的一 個解 ，對 于x2 mod5， 令 x25t代 入fx0 mod25得 t4 mod5， 于 是x25 4 5t22225t2 ，即 x22 mod25 是 fx0 mod25 的一個解； 最后構造同余方程組xb1 mod3 ， x b2mod25 ， b10 ， b210, 22 ，由孫子定理得fx0 mod75的兩個解 x10,72mod75.16、設 p 是素數， 0ap ，證明：xb(1)a 1 ( p1)(p2)( pa 1)mod p .a!是同余方程 axb mod p的解 .解：首先易知 b( 1)a 1 ( p 1)( p2

27、)( pa1)是整數，又由a, p1知方程 axb mod p 解唯一，a!故只須將 x b( 1)a 1 ( p1)( p2)( pa1)mod p代入 axb mod p 驗證它是同余方程的解a!即可 .17、證明：同余方程a1x1a2 x2.an xnb mod m 有解的充要條件是a1, a2 ,.,an ,md |b .若有解，則恰有d mn 1 個解， mod m .解：必要性顯然，下證充分性. 當 n 1 時，由定理2 知命題成立. 假設 nk 時結論已真，考慮a1x1a2 x2. an xnb mod m ，令 a1 , a2 ,., an , md1 ， d1 , ak 1d

28、 ，因為同余方程 ak 1xk 1b mod d有解，其解數為 d ，mod d1 ，記 mm1 d1 ，則解數為 dm1 ，mod m .1現(xiàn)在固定一個解xk 1 ，由歸納假定知a1 x1a2 x2 . ak xkb mod m有解，其解數為d1mk1， mod m ， 從 而 a1 x1a2x2. an xnb mod m有解，其解數為dm1d1mk 1d mk， modm . 由歸納原理知命題對于一切n1成立 .18、解同余方程： 3x2 11x200 mod15 .解：因 1053 5 7同余方程 3x211x200mod3的解為 x1 mod3 ，同余方程 3x211x200mod5

29、的解為 x0,3mod5 ，同余方程 3x211x200mod7的解為 x2,6mod7，故原同余方程有4 解， mod105.作 同 余 方 程 組 ： xb1mod3 ， xb2mod5， x b3 mod7， 其 中b1 1,b20,3, b32,6由孫子定理得原同余方程的解為x13,55,58,100 mod105 .x8(mod 15)19、解同余方程組：x5(mod 8)x13(mod 25) 。解：因為 15,8 1| 85， 15,25 5| 813， 8,25 1| 8 5 .故原同余方程組有解，解數唯一mod 15,8,25600 .將第一個同余方程的解x8 15t1, t

30、1Z ，代入第二個同余方程得 t1 3 mod8，即 t23 8t1,t 2Z ， x53 20t2 ，代入第三個同余方程得 t23 mod5，即 t 33 5t2 ,t3 Z ， x413 600t ，所以原同余方程組的解為x413 mod600 .x（）7 mod1520、討論并解答：x（）2 mod 35x（）16 mod 21解：（15，35） 5 且 7（2 mod5）（15，21） 3 且 716（mod3）（21，35） 7 且 216（ mod7）原同余式組等價于x（7 mod 3）x7（ mod 5）x（2 mod 5）（2 mod 7）16（ mod 3）16（ mod 7

31、）（1 mod3）（2 mod5）x（2 mod 7）M 357105，MM21， M3MM 135，M215m1m2m3由，（）得Mi2M1M11 mod 3同理， M ，2=1， M 3，=1x 1 35 2 2 21 1 2 15 （1mod105）142（ mod105） 37（mod105）21、解同余式8x9（mod11）解： x 981 109876541！8915（8mod11）22、解同余式8x9（mod11） （用三種方法解）解： Q（8，11） 1同余式只有一個解.法 1： 11 是素數，1110 x9 89（8 mod11）81 10987654（9） 15 （8 mo

32、d11）法 2： x 9 （ 1）！8法 3：（求解不定方程8x 11y9 ）23、解同余式6 x327x217 x20 0(mod30)解：設 f (x) 6x327x217 x20由定理 3 知解同余式f ( x)0(mod30) 可先分別解以下兩同余式f ( x)0(mod5),f ( x)0(mod6),容易驗證第一個同余式有解x0,1,2(mod5)第二個同余式有解x2,5(mod6)由 孫 子 定 理 ， 當 ( a, a) 取 (0,2),(0,5),(1,2),(1,5),(2,2),(2,5)時，得到12f ( x) 0(mod30)的個解x 6a1 12a2 2,5,11,

33、17, 20, 26(mod30)24、求相鄰的四個整數，它們依次可被22， 32， 52及 72 整除解：設這四個相鄰的整數是x1, x, x 1,x2 ，按要求應滿足x10(mod 22 ) ,x0(mod 32 ) ,x10(mod 52 ) ,x20(mod 72 ) .所以，這是一個解同余方程組問題，這里m122 , m2 32 , m3 52 ,m4 72兩兩既約 . 滿足定理 1的條件 . M132 g52 g72 , M 222 g52 g72 ,M 322 g32 g72 , M 422 g32 g52由2g112M 11g1g11(mod 2 )知1 MM 1(mod 2

34、)1 M 1因此可取 M 111，由 M2102 g721g44(mod 32 ).知11211M 2M24M 1(mod 3 )因此可取M 22g由222223 g 3112M32 g212 g411(mod 5 )知1M11M3(mod 5 )M222M 313M 31 (mod 52 )1624M 31M 31 (mod 52 )因此可取 M 319，由 M4(13)( 24)3g618(mod 72 )知g112118M4(mod 7 )M 4M 4354M 415M 41 (mod 72 )3050M 41M 41 (mod 72 )因此可取 M 4119 ，因而由定理1 知x32

35、g52 g72 g1g122 g52 g72 (2)g022 g32 g72 g9g(1)22 g32 g52 g(19)g(2)(mod 22 g32 g52 g72 )x11025158763420029349(mod 44100)所以滿足要求的四個相鄰整數有無窮多組，它們是 29348 44100t,2934944100 t,2935044100 t,2935144100t , t0, 1, 2,L最小的這樣的四個相鄰的正整數是29348，29349，29350，29351.25、解同余式fx0(mod35) ， fxx42x3 8x 9fx0(mod5)解：上式與同余式組等價，fx0(

36、mod7)容易證第一個同余式有兩個解即：x1，4(mod5) ，第二個同余式有三個解即x3，5，6(mod7) ，故題中所求同余式 f x0(mod35)， f xx42x3 8x9 有 6個解，即同余式組的解x b1 (mod5) ， xb1(mod7) ， b1 1,4， b23,5,6由孫子定理得 x21b1+15b2 (mod35) ，以 b1 ， b2 的值分別代入即得全部解：x31，26，6，2419，34(mod35)26、求同余方程 x21(mod 2l) 的解.解：當 l 1時，解數為 1， x1(mod 2).當 l2時，解數為 2 , x1,1(mod22 )當 l3 時

37、，同余方程可寫為( x1)(x1)0(mod 2l )由于 x 是解時，必可表為x2 y1. 帶入上式得4 y( y1)0(mod 2l ) 即 y( y1)0(mod 2l 2 )所以必有y0, 1(mod 2l 2 )因此，解 x 必滿足 x1, 1(mod 2l1 )所以原方程的解是 x11+2，l 1 , 1,1 2l 1(mod 2l ) 解數為 4 .27、解同余方程組xb1(mod5), xb2(mod6), xb3(mod7), xb4(mod11)解：由題意可知：m5 6 6 7 112310,M16 7 11462M25 7 11385,M35 6 11330,M45 6

38、7210解得1(modmi ), i 1,2,3,4M i M i得M 13,M 21,M 31,M 41x3 462b1385b2330b3210b4 (mod 2310)即為所求1(mod 3)1(mod 5)28、求的整數解2(mod 7)2(mod11).解： Q m13,m25, m37, m411m3 5 7 11 1155由孫子定理得：M 1385,M 2231，M 3165，M 4245385M 1 1(mod3)M 1 1(mod3)231M 2 1(mod5)M 2 1(mod5)165M 3 1(mod7)M 3 2(mod7)245M 4 1(mod11)M 4 3(mod11)x0 1 385 1 ( 1)231 121652(2)2453556(mod1155)所有整數解為：x01155t556(tZ )