往期文章
导读
孙子定理是中国古代求解一次同余式组的方法。是数论中四大定理之一。又称中国剩余定理。
在数学著作《孙子算经》中,提到一个“物不知数”问题,原文如下:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
孙子算经
《孙子算经》的作者生平和编写年不详,一般认为是东晋时期的作品,比孙武的《孙子兵法》要晚很多。用我们现在学习的数学语言来描述“物不知数”问题:
算经中给出答案是23,23是满足同余方程组的最小正整数。并给出了上述问题的一般解法。
宋代数学家秦九韶在其名著《数书九章》中考虑了更一般化同余方程组的解法。
最终他得到了下面的定理。
孙子定理
定理 假设整数m1,m2, ... ,mn两两互质,则对任意的整数:a1,a2, ... ,an,上述同余方程组有唯一解。
其中
证明
从假设可知,(mi,Mi)=1,故存在整数
另一方面,对i≠j , mj|Mi, 因此
所以
满足
又若x1,x2,是方程组的两个解,则
x1≡x2(mod mi) 1≤i≤n
考虑到(mi,mj)=1(i≠j), 即可知
x1≡x2(mod m)
所以解是唯一的。
□
定理应用
例子1(韩信点兵)
有兵一队,若列成5行纵队,则末行1人;成6行纵队,则末行5人;成7行纵队,则末行4人;成11行纵队,则末行10人,求兵数?
解 此时m=5×6×7×11=2310
M1=462,M2=385,
M3=330,M4=210.
解
联系客服