前面提到的‘中国剩余定理’是老外对我们中国古代数学家对同余理论作的贡献的肯定而命名的，其实它包括两部分，一是《孙子算经》中的定理，二是这里所谫的‘大衍求一术’，但是总的来说，它是对一次同余式组的一类通用解法。

《孙子算经》中有物不知其数问题，它表示成现代数学形式是：

N=R1(Mod 3)
N=R2(Mod 5)
N=R3(Mod 7)

书中给出了这组方程的通解：

N=70R1+21R2+15R3-105P

并副上一首诗歌：
“
三人同行七十（７０）稀，
五树梅花二一（２１）枝。
七子团圆正半月（１５），
除百零五（１０５）便得知。
”

至于为什么要这么算，书中未作任何说明，实际上这一问题还是未解决。真正从完整的计算理论上解决这个问题的，是南宋时期的数学家秦九韶，在他的《数书九章》中提出的所谓‘大衍求一术’就是对这一问题的一般解法。

其实原理非常简单，拿前面的通式说明，为什么R1前的系数是70，用手算一下，它被5和7整除，但是被3除余1，也就是70=1 (mod 3)，于是70R1=R1(mod 3)，而对其它模为0，作成的和不影响其它的数，所以N是问题的解，可以从空间的角度理解，70,21,15就是那个通式方程组的基，随着R1，R2，R3取得不同，解都可以由他们的线性组合构成，而105是3，5，7的最小公倍数，即模他们都为0，是解的循环元。

而所谓的‘大衍求一术’就是求满足x=1(mod M1)且x|M2,x|M3...的x，方法是：先取(M2,M3,...Mk)的最小公倍数a，然后解方程ax=1(mod M1)，那么ax就是我们要求的R1前的系数，整体思想就是这样的，而在秦九韶的方法中非常复杂，但是拿现代的眼光看，这个问题已经解决，即我们熟悉的欧几里德算法（->EUCLID算法与RSA）。不再赘述。

评论