第四章 同余式§1 习题（P61）1． 求下列各同余式的解 （i ）256179(mod337) x ≡ （ii ）1215560(mod 2755) x ≡ （iii ）12961125(mod 1935) x ≡ 解：（i ）由(256,337)1=，∴有唯一解解不定方程 256337179x y -= ……（1） 先解不定方程 2563371x y += ……（2） 由得30(1)79y =-，40(1)104x =-为（2）之特解104179x '=⨯，79179y '=⨯为（1）之特解1041791861681(mod337) x ∴≡⨯=≡是原同余式之一解。

（ii ）由(1215,2755)5=，5560，∴有5个不同的解。

解不定方程 12152755560x y -= (1)即解等价不定方程243551112x y -= ……（2） 先解： 2435511x y += ……（3） 解得（3）的特解0195x =-，086y =即得（2）的特解0195112x =-⨯，086112y =-⨯ ∴原同余式五个不同解为 195112551200551(mo x K K =-⨯+≡+ 0,1,2,3,4K = （iii ）由(1296,1935)9=，91125 ∴有9个不同解解不定方程 129619351125x y -= ……（1） （1）等价于不定方程 14421512x y -= ……（2） 先解： 1442151x y += ……（3） 解得（3）的一特解 0106x =-，071y =于是得（2）的一特解 0106125x =-⨯，071125y =-⨯∴原同余式的9个不同解为106125215295215(mod 1935) x K K =-⨯+≡+2561 = q 1337 256 813 = q 2256 243 13 6 = q 381 78 3 4 = q 4 13 12 1 q P Q 0 1 2 3 4 13 641 1 4 25 104 01319 790,1,2,,8K =2． 求联立同余式的解4290(mod143) x y +-≡ 29840(m o d 1x y -+≡ 解：解 414329 x y z +-= ……（1） 2914384x y z --=- ……（2） 由（2）2(1)-⨯：14317142z y -=- ……（3） 由(143,17)1=，∴（3）有唯一解。

先解 143171z y += 得解 05z =，042y =- 于是得（3）的一个解 05(142)z =⨯-，0(42)(142)y =-⨯-， 代入得 029442(142)1435(142)776454(m o d 143)x =-⨯⨯-+⨯⨯-=-≡ ∴原联立同余式的解为：4(mod143)42(mod143)x y ≡⎧⎨≡⎩ 3．（i ）设m 是正整数，(,)1a m =，证明()1(mod ) m x ba m ϕ-≡是同余式(mod ) ax b m ≡的解 （ii ）设p 是质数，0a p <<，证明1(1)(2)(1)(1)(mod )!a p p p a xb p a ----+≡-是同余式(mod ) ax b p ≡的解。

证：（i ）由Euler 定理有()1(mod ) m a m ϕ≡，于是有 ()1()(mod ) m m ax aba ba b m ϕϕ-≡=≡ （ii ）由1(1)(2)(1)(1)(2)((1))(1)(1)!(mod ) a p p p a a a p ----+≡----=--即得：112(1)(1)(2)(1)(1)(1)!(1)(1)!(mod ) a a a ax ba p p p a b a a ba p ---≡---+≡-⋅--=-由0(!,)1a pa p a p C <<⇒=⇒=(1)(2)(1)!p p p p a a ---+中!(1)(1)a p p a --+，于是有1(1)(2)(1)(1)(m o d )!a p p p a ab p a ----+-是同余式(mod ) ax b p ≡的解。

4． 设m 是正整数，τ是常数，1m τ<，(,)1m a =， 证明：同余式(mod ) ax y m ≡，0xτ，0my τ<<有解。

证：设[]t τ=，作同余式（1） 12100(m o d )1(m o d )2(m o d )(1)(m o d )(m o d )0(m o d ) t t a m a y m a y m a t y m a t y m a m m -⋅≡⎧⎪'⋅≡⎪⎪'⋅≡⎪⎪⎨⎪'⋅-≡⎪⎪'⋅≡⎪⎪⋅≡⎩ （2）11221100(mod )(mod )(mod )(mod )(mod )0(mod ) t t t t a m a x y m a x y m a x y m a x y m a m m --⋅≡⎧⎪''⋅≡⎪⎪''⋅≡⎪⎪⎨⎪''⋅≡⎪⎪''⋅≡⎪⎪≡⎩由1m τ<，(,)1m a =，则0i y m '<<，1,2,,i t = 并且当,i j i j y y ''≠⇒≠把0，1y '，2y '，…，t y '，m 由小到大排列得： 120t y y y m ''''''<<<<<把同余式组（1）中同余式适当调换次序得同余式组（2），然后把同余式（2）依次相减得同余式组（3）11212111(0)0(mod )()(mod )()(mod )(0)(mod )t t t t t t a x y m a x x y y m a x x y y m a x m y m --⎧''⋅-≡-⎪⎪''''⋅-≡-⎪⎪⎨⎪''''⋅-≡-⎪⎪''-≡-⎪⎩其中，10y ''>，10i i y y +''''->，（1,2,,1i t =-），0t m y ''->把（3）中t +1个正整数1y ''，21y y ''''-，…，i m y ''-相加得： 1y ''+（21y y ''''-）+…+（t m y ''-）= m由1t m +，易见这1t +个正整数中必有一个1mt + 设*1m my t t<+，其对应同余式为**(mod ) ax y m ≡ 其中*x t τ即是说同余式(mod ) ax y m ≡，0xτ，0my τ<<有解。

§2 习题（P65）1、 试解下列各式：（i ）十一数余三，七二数余二，十三数余一，问本数。

(ii) 二数余一，五数余二，七数余三，九数余四，问本数。

解：（i ）解同余式组3(mod11) x ≡，2(mod72) x ≡，1(mod13) x ≡由111372m =⨯⨯，11372M =⨯，21113M =⨯，31172M =⨯ 及同余式113721(mod11) M '⨯≡即 11(mod11) M '≡ 解为 11M '= 211131(mod 72) M '⨯≡即 21(mod72) M '-≡- 解为 21M '=-372111(mod13) M '⨯≡即 3121(mod13) M ≡ 解为 31M '=-由1112223331372311132721111730M M b M M b M M b '''++=⨯⨯-⨯⨯-⨯⨯= ∴同余式组的解为1730(mod 10296) x ≡（ii ）解同余式组1(mod 2) x ≡，2(mod5) x ≡ 3(mod7) x ≡，4(mod9) x ≡由15791(mod 2) M '⨯⨯≡即 11(mod 2) M '≡ 解为 11M '= 22791(mod5) M '⨯⨯≡即 21(mod5) M '≡ 解为 21M '= 32591(mod 7) M '⨯⨯≡即 361(mod 7) M '≡ 解为 31M '=- 42571(mod9) M '⨯⨯≡即 471(mod9) M '≡ 解为 44M '=∴同余式组的解为 57927922593257441417157(mod630)x ≡⨯⨯+⨯⨯⨯-⨯⨯⨯+⨯⨯⨯⨯=≡2、（i ）设1m ，2m ，3m 是三个正整数，证明：1323123[(,),(,)]([,],)m m m m m m m = （ii ）设12(,)d m m =，证明同余式组11(mod ) x b m ≡，22(mod ) x b m ≡ （1） 有解的充要条件是 12 d b b -在有解的情况下，适合（1）的一切整数可用下式求出1,212(mod[,]) x x m m ≡其中1,2x 是适合（1）的一个整数。

（iii ）应用（i ），（ii ）证明同余式组(mod ) i i x b m ≡ 1,2,,i k = （2）有解的充要条件是(,)i j i j m m b b -，,1,2,,i j k =，并在有解的情况下，适合（2）的一切整数可由下式求出：1,2,,12(mod[,,,]) k k x x m m m ≡其中1,2,,k x 是适合（2）的一个整数。

证：（i ）考虑：对于任意实数a ，b ，c 有(min(,),min(,))min((,),)Max a c b c Max a b c = 因为01 若abc ，则右边min(,)a c c ==，左边max(,)c c =02 若acb ，则右边min(,)ac c ==左边max(,)c b c == 03 若cab ，则右边min(,)ac a ==左边max(,)a b a == 由对称性知，对任意实数a ，b ，c 上式恒成立。

设 111t a a t m p p =，121t b b t m p p =，131t c c t m p p =0ia ，0ib ，0ic于是max(min(,),min(,))13231[(,),(,)]i i i i t a c b c i i m m m m p ==∏m i n (m a x(,),)1231([,],)i i i ta b c i i p m m m =∏= （ii ）01 设12(,)d m m =，11m n d =，22m n d =必要性：若0x 是（1）的解011022,x km b x lm b ⇒=+=+ 1221km lm b b ⇒-=-122121(n )d kn l b b d b b ⇒-=-⇒-充分性：若21 d b b -，则不定方程1221m x m y b b -=-有整数解，设x k =，y l =是其一解，令01122x km b lm b =+=+则0x 为（1）的解。