论孙子定理和韩信点兵

学 术 论 文

题 目: 论孙子定理和韩信点兵

学号：

学校：

专业：

班级：

姓名：

指导老师：

时间：

摘要：孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国剩余定理。公元1852年，英国基督教士伟烈亚士 ［Alexander Wylie公元1815-1887年］将《孙子算经》「物不知数」问题的解法传到欧洲，公元1874年马蒂生指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一个定理称为「中国的剩余定理」［Chinese remainder theorem］。 关键词：孙子定理，韩信点兵，中国剩余定理

正文：

一，孙子定理：公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”答为“23”。也就是求同余式组x≡2 （mod3），x≡3 （mod5 ），x≡2 （mod7）（式中a≡b （modm）表示m整除a－b ）的正整数解。明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。 ”即解为x≡2×70＋3×21＋2×15≡233≡23(mod105）。

孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。解法的意思就是用70乘3除所得的余数，21乘5除所得的馀数，15乘7除所得的余数，然後总加起来，除以105的余数就是答案。

即题目的答案为 70×2+21×3+15×2

=140+63+30

=233

233-2×105=23

公式：70a+21b+15c-105n

解法中的三个关键数70，21，15，有何妙用，有何性质呢?

首先70是3除馀1而5与7都除得尽的数，所以70a是3除余a,而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。

同理，15c是7除馀c，3与5除得尽的数，总加起来 70a+21b+15c 是3除馀a，5除余b ，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=3*5*7)仍有这样性质，可以多次减去105而得到最小的正数解。

根据此可列表（1）

此定理的一般形式是设mi.mj 为两两互素的正整数，m＝m1，…mk ，m＝miMi，i＝1，2，… ，k 。

则同余式组x≡b1(modm1)，…，x≡bk(modmk) (1)

的解为：

x≡M'1M1b1＋…＋M'kMkbk （modm）。（2）

式中M'iMi≡1 （modmi），i＝1，2，…，k 。

（直至18世纪 C.F.高斯才给出这一定理。孙子定理对近代数学如环论，赋值论都有重要影响。）

定理l(孙子定理) 设k≥2，且m1,m2…mk是两两互素的k个正整数，m=m1m2…mk,m=miMi,i=1,2,….k, 则同余式组(1) 的解是

x≡M'1M1b1＋…＋M'kMkbk （modm）,

其中M'iMi≡1 （modmi），i＝1，2，…，

表1可以改为：

表二：

例l(新论皴问题一) 某数用七数缺一，八数缺二，九数缺四，问本数? 解：x≡1 （mod7） ，x≡2 （mod8） ，x≡4 （mod9）

所以 m=7*8*9=504

即：M1= 72，M2=63，M3=56

M'1M1≡1（mod7），M'2M2≡1（mod8），M'3M3≡1（mod9）

求得 M'1=-3，M'2=-1，M'3=5

解为：x≡-3*72*1＋-1*63*2+5*56*4（mod504）。

即：x≡778（mod504）。

本数为788

定理2：若 b1.b2….bk分别是过m1 ，… ，mk 的完全剩余系，则（2）过摸m=m1m2….mk 的完全剩余系。

（注 特别指出．若M'k满足同余M'iMi≡bi(modmi)对孙子定理同样有正整数解为：x≡M'1M1b1＋…＋M'kMkbk （modm）,）

二．韩信点兵：我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。

例二：韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数 解：b1=1,b2=5,b3=4,b4=10

x≡3*462＋385*5＋330*4+210*10（mod2310）,

x≡6731（mod2310）,

x≡2111（mod2310）,

即得兵数2111

“韩信点兵”形成了一类问题，也就是初等数论中解同余式.这类问题的有解条件和解的方法被称为“中国剩余定理”，这是由中国人首先提出的.

① 有一个数，除以3余2，除以4余1，问这个数除以12余几？

解：除以3余2的数有：

2， 5， 8， 11，14， 17， 20， 23….

它们除以12的余数是：

2，5，8，11，2，5，8，11，….

除以4余1的数有：

1， 5， 9， 13， 17， 21， 25， 29，….

它们除以12的余数是：

5， 9， 1， 5， 9，….

一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5.

如果我们把①的问题改变一下，不求被12除的余数，而是求这个数.很明显，满足条件的数是很多的，它是 5＋12×整数，

整数可以取0，1，2，…，无穷无尽.事实上，我们首先找出5后，注意到12是3与4的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.《孙子算经》提出的问题有三个条件，我们可以先把两个条件合并成一个.然后再与第三个条件合并，就可找到答案.

②一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数. 解：先列出除以3余2的数：

2， 5， 8， 11， 14， 17， 20， 23， 26，…，

再列出除以5余3的数：

3， 8， 13， 18， 23， 28，….

这两列数中，首先出现的公共数是8.3与5的最小公倍数是15.两个条件合并成一个就是8＋15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30，…，

就得出符合题目条件的最小数是23.

事实上，我们已把题目中三个条件合并成一个：被105除余23.

那么韩信点的兵在1000-1500之间，应该是105×10+23=1073人

术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。 」

孙子算经的作者及确实著作年代均不可考，不过根据考证，著作年代不会在晋朝

之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。 简单扼要总结:

1.算两两数之间的能整除数

2.算三个数的能整除数

3.用1中的三个整除数之和减去2中的整除数之差(有时候是倍数)

4计算结果即可

例三：韩信带1500名兵士打仗，战死四五百人，站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：1049 如多一人，即可凑整。幸存人数应在1000~1100人之间，即得出： 3*5*7*10-1=1049（人）

现在传本的《孙子算经》共三卷。卷上叙述算筹记数的纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算法和筹算开 …… 此处隐藏：3123字，全部文档内容请下载后查看。喜欢就下载吧 ……