一次同余式与孙子定理 知识扫描：1：本节将讨论一次同余方程和由此引申出的重要定理——孙子定理，首先介绍若干概念。

设整系数多项式()10,n n f x a x a x a =+++若有整数c ，满足()()()1212120mod ,mod .(),,f c m c x c m x c c c c c m c c ≡≡则称是满足同余方程的解，记作注：这是因为除以余的数都满足这样方程。

当且仅当都是方程的解，且与模不同余时，我们称是方程的两个不同解。

一般情况，我们说同余方程的解数，即指模m 两两不同余的解的个数。

2：最简单的同余方程是一次同余方程()()()()()()()()()()()mod ,.,/(,/,,,1,,/,,,,mod )ax b m m a a m b a m a m b a m a m a m a mp q b p q b b a m b a m a m a m a m ax b m ≡+=⇒+=≡同余方程有解的充要条件是注：必要性，若有解，则b 可用a,x 的式子表达，所以；充分性，互素则可知因为，则可知有解。

Œ()()()()()()()001,1,1mod ,1mod ,mod ,,1i i i i m a m a m x m ax m x ax a b m a a a m x ab m a m -==='≡≡'≡≡=特别地，在时，同余方程必有解。

事实上：，遍历模的一组完系时，也遍历模的一组完系。

因此，有且仅有一个r 使得r 即同余方程至多有一个解。

进一步，一定存在使得于是即为时，同余方程的解。

j()()()()()()11122211223.1,,0mod 0mod 0mod mod mod mod i i i kk k k k k a b m a x b m a x b m a x b m x c m x c m x c m >+≡⎧⎪+≡⎪⎨⎪⎪+≡⎩≡⎧⎪≡⎪⎨⎪⎪≡⎩设是整数，是正整数，i=1,2,,k,则称下面这k 个同余式为一次同余方程式组，显然，其中若有一个同余方程无解。

则方程组无解。

当其中每个同余方程都有解时，可将求解转化为求若干个下述方程的解。

为了讨论上式的本质，我们先来看k=2的情况。

()()()()()()()()()()()()()()()()()1212121212112121121212121212111212121112121.mod ,m i j ij i j ij m m m x m x m x m x m x x m m x m x m m m m m m m x m x x m x m m x m x x m x ==+=+==+≡++≡+定理：设是模的完全剩余系，是模的完全剩余系，则x 是模的完全剩余系。

（即，分别遍历模，模的完全剩余系时，x 遍历模的完全剩余系。

）证明：此时x 共有个数，因而只需证明它们对两两不同余。

若则()()()()()()()()()()()()()11112122212111212212121121121od =mod =1=1m x x x m x x m x m x x m m m m m x m m x m +≡+=则，同时，则，定理得证！定理刻画了完系的某种结构，表明大模的完系，可以表示为两个较小的模的完系的“组合”。

同时我们应注意到，，，遍历模的完系时也遍历模的完系（这个性质非常常用并且有用）()()()()()()()()()()()()12121212122112121212121212122,,1,,3,,1,ij k k j j kkk k m m m m m x x m m x m x m x m m m m m m m m m m m M j k x M x M x M x x x x m m m x m m m m ===+==≤≤=+++=定理：设分别遍历模，的完全剩余系，则遍历模的完全剩余系。

进一步分析，我们可以得到一般情形的刻画。

定理：设两两既约，再设及那么当，，，分别遍历模，，，的完全剩余系时，遍历模()()()()()()()1111111111112..()2k n n n n n n n n n n n n n n n k mmx x m m m m m m m x m x m x m m m m k ++++++++++==++=+=的完全剩余系。

证明：时，即定理2设k=n 时定理成立。

当k=n+1时，记x 我们有x 注：与互素，x 遍历的完系，遍历模的完系由当时上式成立，命题得证！。

定理4：孙子定理（中国剩余定理）()()()()()()()121122111111222112,,,mod mod mod mod ,,1,1mod 1k k k k k k k j j j j j m m m x c m x c m x c m x M M c M M c M M c m m m m m m m M j k M M m j k ----≡⎧⎪≡⎪⎨⎪⎪≡⎩≡++==≤≤≡≤≤设是两两既约的正整数，那么同余方程：的解是这里孙子定理依旧刻画的是剩余系的结构，请读者将其与定理3进行对比，可以看出，孙子定理是着重刻画一组已定下的较小模的剩余类与一个较大的模的某个剩余类间的关系。

中国剩余定理在做题时的指导在于它能断定同余方程组的模两两互素时，一定有解。

甚至有些时候，我们并不关心解的是什么，而关注是否有解，怎样使其有解。

例题分析例1：解同余方程组()()()()()()()()1234123411mod 31mod 52mod 72mod113,5,7,11,57113711,5311,5731111mod 3,x x x x m m m m M M M M M ≡⎧⎪≡-⎪⎨≡⎪⎪≡-⎩========≡--≡解：取这时，又由()()()()()()()()()()111111121112222311133334141mod 3,=1.2211mod 5,1mod 5,=1.3544mod 7,14mod 7,=2.3576mod11,=2.394mod1155.M MMM M M M M M M M M M M M M x ----------≡≡≡-≡≡≡≡⨯⨯≡≡≡≡⨯⨯≡≡所以可取由所以可取由所以可取由所以可取由孙子定理知同余方程的解为：例2：任意给定的整数n ，证明：一定存在n 个连续正整数，其中每一个都有大于1的平方因子。

证明：由于素数有无穷多个，因而对于任意的n ，均可选出n 个不同的素数12,,,n p p p 。

考虑同余方程组()222212mod ,i n x i p p p p ≡-由于，，，显然两两互素，由中国剩余定理知上述同余方程组有解，于是1,2,,x x x n +++这n 个数分别被22212n p p p ，，，整除，命题得证！评注：在构造同余式时，选择质数的某些形式作为模式十分有效的，再看一个构造的例子。

()()()(){}123200512200511,,n S S k x x x 例：能否找到含有个自然数的集合，使中任意两数互素；中任意个数的和为合数。

分析与解：显然是“年份数据”，为此考虑n 个元素的集合，由于同时满足上述两个条件不易找到一个直接构造，只能一步步地探索。

对于满足的n 元集合石容易构造的，故设我们已找到一个满足的集合下面关心怎样更进一步约束或者变动该集合。

我们当然希望需要控制的“k 数和”变少自然想到了归纳构造。

我们{}{}()()1212111211,,,12n n n nn n n n n nx x x x x x x x x x x k x k C C +++-≥++设已经满足了上述两个条件，下面用推出应为何物。

中含的“k 数和”有2个注：含的数和个数为：()()()()1211122112121211111211121111221,,,,,+++mod ,,, 1.n n n n n n n n n n n n n n n n i i i i S S S T S x T S x T S x x S x x S x x S x x x S T p p p p +++---++++++-++-=-=-=----≡-≡-≠设这些和为则均为定值，我们想让，，，均为合数，这利用中国剩余定理是容易办到的，因为同余方程组：是有解的，其中p 是两两互素的数，且这样我们就让{}(){}()()1+11+11+111+1+11,,2,,1,,1,,1mod .n n i n n n n n n x x x x p x x x kx x x x x x x +≡满足回头看此时是否满足呢？这一点并不确定，从而应当控制一下的值。

由于已经是两两互质，所以若能表示为的形式，则两两互素，这实际上要求()()()1221121112121,2mod 1,2,,21,1mod ,2005n n i n n n n i i n n n p p p p a a a x T p i x a a a x n -+++-≡-=-≡=至此，怎样控制已经非常明确了，我们只需个质数，，，它们均与互素，考虑个同余式由中国剩余定理，这样的存在。

至此完成了归纳构造！特别的，时我们能找到一个适合题目要求的集合。

()()()()()()121121231240,1,21,,,,,,,121,031204132051243061624530n n n n a a a a a a a a a a a a n n n n n n n n -======例：求具有下述性质的，存在，，的排列使得恰好构成模的完全剩余系。

解：首先实验几个较小的，时，显然满足条件，时，满足条件时，，，满足条件，时，，，，满足条件，时，，，，，满足时，经实验没有满足条件的排列，n=7时，，，，，，，满足条件，n=8时，没有满足要求的排列。

通过上述实验，我们猜想n 为质数时，均是满足条件，尽管这可能是不全面的。

()()()()()()()()1121212,3,,,,0mod 1,mod ,11mod .1,10mod ,=0k kk k k k k k k p p p p p p k p b b b k b k p a c p k b a k k p a a a a a a a a p a p p p a a a =≡-≡=-≡-≡=-≡≡≠下面证明这个结论。

事实上，对任意质数，由中国剩余定理，对每个存在使得用表示被除的余数k=2,3,,p 则注：实际上是为了得到令下面证明，，，互不相同从而，，，是模的完系事实上，由有，故。