成都七中高一竞赛数论专题10.中国剩余定理1.(中国剩余定理)设12,,,k m m m 是k 个两两互素的正整数,证明对任意整数12,,,k a a a ,一次同余方程组(mod ),j j x a m ≡1.j k ≤≤必有解,在模1kjj m m==∏的意义下解101(mod )kjj j j x x MM a m -=≡=∑唯一.其中1,j j jm M M m -=是j M 关于模j m 的数论倒数即11(mod ).j j j M M m -≡2.解同余方程组1(mod 7)1(mod8)3(mod 9)x x x ≡⎧⎪≡⎨⎪≡⎩.3.设*,n N ∈证明：存在*,m N ∈使得同余方程21(mod )x m ≡在模m 的意义下至少有n 个根.(请对比拉格朗日定理).4.证明：对任意给定的正整数n,均有连续n个正整数,其中每一个都有大于1的平方因子.5.证明：对任意正整数n,存在n个连续正整数,它们中每一个数都不是素数的幂.6.证明：存在任意长的由不同正整数组成的等差数列,它的项都是正整数的幂,幂指数是大于1的整数.7.设,m n 是自然数,满足对任意自然数,k (,111)(,111)m k n k -=-.证明存在某个整数l 使得11.l m n =高一竞赛数论专题 10.中国剩余定理解答1.(中国剩余定理)设12,,,k m m m 是k 个两两互素的正整数,证明对任意整数12,,,k a a a ,一次同余方程组(mod ),j j x a m ≡1.j k ≤≤必有解,在模1kjj m m ==∏的意义下解101(mod )kj j j j x x M M a m -=≡=∑唯一. 其中1,j j jm M M m -=是j M 关于模j m 的数论倒数即11(mod ).j j j M M m -≡证明：因为(,)1,,i j m m i j =≠所以(,) 1.j j M m =由Bezout 定理知道存在整数,s t 使得 1.j j sM tm +=1(mod ).j j sM m ≡取1.j M s -=于是11(mod ).j j j M M m -≡另一方面,,j jmM m =所以|,.i j m M i j ≠ 于是111(mod )(1,2,,).kjj j i i ii i j MM a M M a a m i k --=≡≡=∑即11(mod )kj j j j x M M a m -=≡∑是一次同余方程组(mod ),j j x a m ≡1j k ≤≤的解.若00,x x '是是一次同余方程组(mod ),j j x a m ≡1j k ≤≤的两个解. 则00(mod ),(mod ).j j j j x a m x a m '≡≡于是00(mod ).j x x m '≡即00|j m x x '-.因为(,)1,.i j m m i j =≠ 所以00|m x x '-,即00(mod ).x x m '≡ 所以中国剩余定理的得证.2.解同余方程组1(mod 7)1(mod8)3(mod 9)x x x ≡⎧⎪≡⎨⎪≡⎩.解：7,8,9两两互素,则由中国剩余定理知道有唯一解.123789504,72,63,56.M M M M =⨯⨯==== 1722(mod 7),M =≡取114(mod 7).M -≡2631(mod8),M =≡-取121(mod8).M -≡-3562(mod 9),M =≡取135(mod 9).M -≡所以x ≡724163(1)156********(mod504).⨯⨯+⨯-⨯+⨯⨯≡≡3.设*,n N ∈证明：存在*,m N ∈使得同余方程21(mod )x m ≡在模m 的意义下至少有n 个根.(请对比拉格朗日定理).证明：对于任意的素数p ,同余方程21(mod )x p ≡可化为(1)(1)0(mod )x x p -+≡.所以恰好有两个不同的解1,1(mod )x p p ≡-. 现在任取s 个不同的奇素数12,,,.s p p p ,这里的s 满足2.s n ≥令12s m p p p =.考虑2s个不同的数组12(,,,)s a a a ,其中{1,1}j j a p ∈-.由中国剩余定理方程组1122(mod )(mod )(mod )s s x a p x a p x a p ≡⎧⎪≡⎪⎨⎪⎪≡⎩有唯一解12(,,,)s x a a a (在模m 的意义下).此解满足212221(mod )1(mod )1(mod )s x p x p x p ⎧≡⎪≡⎪⎨⎪⎪≡⎩,也就是满足21(mod ).x m ≡若两个不同的数组1212(,,,),(,,,)s sa a a a a a ''',则必存在j 使得.j j a a '≠不妨设1, 1.j j j a a p '==- 于是1(mod )j j x a p ≡=与1(mod )j j j x a p p '≡=-不同解. 于是1212(,,,)(,,,)(mod )s sj x a a a x a a a p '''≡/. 从而1212(,,,)(,,,)(mod )s sx a a a x a a a m '''≡/. 这就证明了21(mod )x m ≡至少有2s个解.2.s n ≥所以存在存在*,m N ∈使得同余方程21(mod )x m ≡在模m 的意义下至少有n 个根.4.证明：对任意给定的正整数n ,均有连续n 个正整数,其中每一个都有大于1的平方因子.证明：由于素数有无穷多个,我们可取出n 个互不相同的素数12,,,n p p p ,考虑同余方程组212221(mod )2(mod )(mod )n x p x p x n p ⎧≡-⎪=-⎪⎨⎪⎪=-⎩.因为22212,,,n p p p 显然两两互素,故由中国剩余定理知上述同余方程组有正整数解0.x x =于是连续n 个数0001,2,,x x x n +++分别被平方数22212,,,n p p p 整除.命题得证.5.证明：对任意正整数n ,存在n 个连续正整数,它们中每一个数都不是素数的幂.证明：若能找到n 个连续正整数,它们中的每一个数都有两个不同的素因子,则命题得证. 为此取2n 个不同的素数1212,,,,,,,.n n p p p q q q考虑同余方程组11221(mod )2(mod )(mod )n n x p q x p q x n p q ≡-⎧⎪=-⎪⎨⎪⎪=-⎩因为1122,,,n n p q p q p q 显然两两互素,故由中国剩余定理知上述同余方程组有正整数解0.x x =于是连续n 个数0001,2,,x x x n +++中每一个数都有两个不同的素因子.命题得证.6.证明：存在任意长的由不同正整数组成的等差数列,它的项都是正整数的幂,幂指数是大于1的整数.证明：设m 是任意正整数,由于素数有无穷多个,设k p 表示第k 个素数,12.s p p p p =对任意的正整数k m ≤,显然(,)1k kp p p =,由中国剩余定理知同余方程组0(mod )1(mod )kk kk p a p a p ⎧≡⎪⎨⎪≡-⎩有正整数解 k x a =.于是存在正整数k a 满足|,k kpa p |1k k p a +. 令1212m a aa q m =.则(1,2,,)qk k m =组成了一个m 项的递增的等差数列.注意到|1k k p a +,|,k k p a p 其中由|k kp a p 可知当k n ≠时,|.k n p a 于是*11221111,,,,,1.().k k k k k k k k m k m k k k i a p t a p t a p t a p t a p t a p t t N --++=====+=∈1111121212111212(1)(1)[12(1)(1)]m k k k m k k m k a a a a a a a a a a a a a a a qk m k k k k m k k m k -+-+++==-+=-+12111112[12(1)(1)](12(1)(1)).k k k k k k k m k k k k m k k p t p t p t p t p t p t t t t t p t t k k m k k k m k -+-+=-+=-+所以qk 是正整数的幂,幂指数是大于1的整数. 命题得证.7.设,m n 是自然数,满足对任意自然数,k (,111)(,111)m k n k -=-.证明存在某个整数l 使得11.l m n =证明：设11,11,ijm p n q ==其中,i j 为非负整数,且11,11.p q 寣 为证明结论,只需要证明p q =即可. 若p q >, 考虑同余方程组0(mod )1(mod11)x p x ≡⎧⎨≡-⎩因为(,11)1,p =故由中国剩余定理知上述同余方程组有正整数解0.x x =于是*00|,111(),p x x k k N =-∈于是0(,111)(11,).i m k p x p -==0(,111)(11,).jn k q x q p -=≤<与(,111)(,111)m k n k -=-矛盾.若p q <,考虑同余方程组0(mod )1(mod11)x q x ≡⎧⎨≡-⎩因为(,11)1,q =故由中国剩余定理知上述同余方程组有正整数解0.x x =于是*00|,111(),q x x k k N =-∈于是0(,111)(11,).j n k q x q -==0(,111)(11,).im k p x p q -=≤<与(,111)(,111)m k n k -=-矛盾.所以p q =.于是11.i j m n -=命题得证.。