我国大约在公元三世纪成书的《孙子算经》里，已经提出并很好地解决了这类问题.其中，给出了“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”及其解法.
这一问题可用同余方程组表示：设有物x个，则
我们可以分析、求解如下：
被3，5整除而被7除余1的最小正整数是15；
被3，7整除而被5除余1的最小正整数是21；
被5，7整除而被3除余1的最小正整数是70.
从而，
15×2=30被3，5整除而被7除余2；
21×3=63被3，7整除而被5除余3；
70×2=140被5，7整除而被3除余2.
于是，和30＋63＋140=233必符合题目要求，即为所求.但此数不一定是符合要求的最小正整数，所以，从中减去3，5，7的最小公倍数105的整数倍，即可得到最小正整数解23.
因而，《孙子算经》里给出的解法是：“术曰三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之，得二百三十三，以之减二百一十，即得二十三.”
该问题及解法可推广为：“3除余a，5除余b，7除余c，问数几何？”其解为：x≡70a＋21b＋15c（mod105).
关于该解法公式，明朝程大位的《算法统宗》（1593年)给出了解法歌诀：“三人同行七十稀，五树梅花廿一枝.七子团圆整半月，除百零五便得知.”
更一般的情况，即模两两互质的同余方程组的求解方法，1247年宋朝秦九韶《数书九章》给出了“大衍求一术”，国际上称之为“中国剩余定理”.
定理1 （中国剩余定理)设正整数m1，m2，…，mn（n≥2)两两互质，b1，b2，…，bn是整数，则一元一次同余方程组
有且只有一个解：
其中，
证明 存在性.(www.xing528.com)
∵m1，m2，…，mn（n≥2)两两互质，Mk=M/mk，∴（Mk，mk)=1.
∴存在整数M′k，m′k，使得MkM′k＋mkm′k=1成立.
即存在整数M′k，使得MkM′k≡1（modmk)（k=1，2，…，n).
而当l≠k（l，k=1，2，…，n)时，
∵M=m1m2…mn，Mk=M/mk，∴ml|Mk.
∴MkM′k≡0（modml).
∴b1M1M′1＋b2M2M′2＋…＋bnMnM′n≡bkMkM′k≡bk（modmk).
∵m1，m2，…，mn（n≥2)两两互质，
∴x≡b1M1M′1＋b2M2M′2＋…＋bnMnM′n（modM)是同余方程组的解.
唯一性.
设x≡r（modM)，x≡s（modM)是同余方程组的两个解，则它们满足方程组中的每个方程，即
从而r≡s（modmk).由于m1，m2，…，mn（n≥2)两两互质，m=[m1，m2，…，mn]=m1m2…mn，故r≡s（modM)，这与它们是两个解矛盾，故同余方程组只有一个解.
注 解方程组时取M′1，M′2，…，M′n为绝对值最小的值计算简便.
例1 求解“物不知数”问题.
例2 “韩信点兵”问题：5人一列剩1人，6人一列差1人，7人一列剩4人，11人一列差1人，求兵数.
解 设兵数为x，由题意得
显然，m1=5，m2=6，m3=7，m4=11；b1=1，b2=-1，b3=4，b4=-1.M=2310，M1=462，M2=385，M3=330，M4=210.
答：兵数为2111人.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
