-
摘要 中国剩余定理是中国古代数学家为世界数学的发展所作出的巨大贡献，它的数学思想在近代数学、当代密码学以及日常生活中都有着广泛的应用和影响.本文研究了对中国剩余定理的推广并用算法进行编程实现.26873
- 上一篇：图像增强的理论研究与应用+源程序
- 下一篇：基于Android的音乐播放器设计
毕业论文关键词 中国剩余定理；推广；算法；编程实现
一、引言
在古代中国的数学历史上，流传着一个韩信点兵的故事：秦朝末年，楚汉相争.有一次，韩信率领1500名将士和楚国大将李峰交战.经过一场苦战，楚军不敌汉军，节节败退返回营地，而汉军也死伤大约四五百人.于是，韩信也整顿兵马返回大本营.当行至一山坡时，忽然有后军来报，说楚军骑兵追来.汉军本来就已十分疲惫，这时队伍一片哗然.韩信兵马行至坡顶，见敌方人数不足五百骑，便立刻点兵迎敌.他命令士兵3人站成一排，多出2名；接着命令士兵5人站成一排，多出3名；他又命令士兵7人站成一排，又多出2名.韩信马上向将士们宣布：我军有1073名战士，而来敌不足五百，况且我们居高临下，以众击寡，一定可以打败敌人.汉军本来就十分信服自己的统帅，这样一来更是认为韩信是神仙下凡、神机妙算.于是士气大振.交战不久，楚军大败而逃.[1]
看完这个故事我相信大家都会有一个疑问，那就是韩信为什么能仅凭士兵的三次排列就能知道士兵人数呢？其实韩信点兵的求解方法，就是中国剩余定理的一次同余式解法.它是中国古代数学的一项重大创造，并且在世界数学史上具有十分重要的地位.因此下面我就对中国剩余定理进行一些介绍和简单的推广，并进行编程实现.
二、中国剩余定理
1 定理内容
中国剩余定理 设 是两两互素的正整数，那么，对任意整数 ，一次同余方程组
（1）
必有解，且解数为1.事实上，设
, （2）
这里 ， 是满足
（3）
的一个整数（即是 对模 的逆）.那么，同余方程组（1）的解是
. （4）
此外， 与 互素的充分必要条件是 与 互素， .[2]
一次同余式组的解法有许多，主要有歌诀法、不定方程解法、同余解法.例如歌诀法是我国古代数学家对这种同余方程组进行了研究，考虑一般解法，并将解法编成一首歌诀:“三人同行七十稀,五树梅花廿一枝,七子团圆正月半,除百零五便得知.”[4]上面所给出的歌诀法只能解决模为3,5,7的同余式组成的同余式组，这样就会具有很大的局限性，一个歌诀只能解决固定了模不固定余数的解.但是从算法的角度，这种算法却是最优的.歌诀法就是古人具有能解一类题的能力，然后把算法规格化，以便后人使用，这是古代人的智慧的体现.在此另外两种解法就不赘述了.
2 举例及编程实现
在进行编程求解时，希望能设计一个算法使得所编的程序可以解决最一般的问题，这样就不得不抛弃一些问题本身的特性，从中国剩余定理求解本身出发，由上面给出可知同余方程组的一般求解方法.由于问题并不是很复杂，只需编写几个自定义函数即可实现.需要用到的函数有：（1）求最大公约数的算法int GCD(int a,int b)用来判断所给的模是否两两互素.（2）扩展欧几里得算法int64 Extend_Euclid(int64 a, int64 b, int64 &x, int64 &y)用来高效求出最大公约数.（3）中国剩余定理的算法实现int64 China_Reminder(int len, int64 *a, int64 *n)即可实现模互素的一次同余方程组的求解.