点击: 回复:23896 关闭此页
转贴 中国剩余定理
楼主 8307 | 发表于2007-04-28 17:02:38
中国剩余定理!
我国汉代有一位大将,名叫韩信。他每次集合部队,都要求部下报三次数,第一次按1~3报数,第二次按1~5报数,第三次按1~7报数,每次报数后都要求最
后一个人报告他报的数是几,这样韩信就知道一共到了多少人。他的这种巧妙算法,人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。
这种问题在《孙子算经》中也有记载:“今有物不知其数:三三数之余二,五五数之余三,七七数之余二,问物几何?” 它的意思就是,有一些物品,如果3个3个的数,最后剩2个;如果5个5个的数,最后剩3个;如果7个7个的数,最后剩2个;求这些物品一共有多少?这个问
题人们通常把它叫作“孙子问题”,
西方数学家把它称为“中国剩余定理”。到现在,这个问题已成为世界数学史上闻名的问题。
到了明代,数学家程大位把这个问题的算法编成了四句歌诀:
三人同行七十稀,五树梅花廿一枝;
七子团圆正半月,除百零五便得知。
用现在的话来说就是:一个数用3除,除得的余数乘70;用5除,除得的余数乘21;用7除,除得的余数乘15。最后把这些乘积加起来再减去105的倍数,就知道这个数是多少。
字串4
《孙子算经》中这个问题的算法是:
70×2+21×3+15×2=233
233-105-105=23
所以这些物品最少有23个。
根据上面的算法,韩信点兵时,必须先知道部队的大约人数,否则他也是无法准确算出人数的。你知道这是怎么回事吗?这是因为,
被5、7整除,而被3除余1的最小正整数是70。
被3、7整除,而被5除余1的最小正整数是21;
被3、5整除,而被7除余1的最小正整数是15;
所以,这三个数的和15×2+21×3+70×2,必然具有被3除余2,被5除余3,被7除余2的性质。
以上解法的道理在于:
被3、5整除,而被7除余1的最小正整数是15;
被3、7整除,而被5除余1的最小正整数是21;
被5、7整除,而被3除余1的最小正整数是70。
因此,被3、5整除,而被7除余2的最小正整数是 15×2=30;
字串6
被3、7整除,而被5除余3的最小正整数是 21×3=63;
被5、7整除,而被3除余2的最小正整数是 70×2=140。
于是和数15×2+21×3+70×2,必具有被3除余2,被5除余3,被7除余2的性质。但所得结果233(30+63+140=233)不一定是满足
上述性质的最小正整数,故从它中减去3、5、7的最小公倍数105的若干倍,直至差小于105为止,即 233-1O5-105=23。所以23就是被3除余2,被5除余3,被7除余2的最小正整数。
[ 本帖最后由 草儿 于 2008-7-5 23:39 编辑 ]
1楼 8307 | 发表于2007-04-28 17:03:03
我国古算书中给出的上述四句歌诀,实际上是特殊情况下给出了一次同余式组解的定理。在1247年,秦九韶著《数书九章》,首创“大衍求一术”,给出了一次 同余式组的一般求解方法。在欧洲,直到18世纪,欧拉、拉格朗日(Lagrange,1736~1813,法国数学家)等,都曾对一次同余式问题进行过研 究;德国数学家高斯,在1801年出版的《算术探究》中,才明确地写出了一次同余式组的求解定理。当《孙子算经》中的“物不知数”问题解法于1852年经 英国传教士伟烈亚力(Wylie Alexander,1815~1887)传到欧洲后,1874年德国人马提生(Matthiessen,1830~1906)指出孙子的解法符合高斯的 求解定理。从而在西方数学著作中就将一次同余式组的求解定理称誉为“中国剩余定理”。
[ 本帖最后由 8307 于 2007-4-28 17:04 编辑 ]
2楼 刘东北 | 发表于2007-04-28 17:05:02
大哥,你太有才了,这个好,没见过.
谢谢.
3楼 8307 | 发表于2007-04-28 17:07:10
没见过了吧,晕死,看看理论的东西远比算什么号好~
4楼 麻烦 | 发表于2007-04-28 17:28:42
让我开了眼界,第一次听说剩余定理,谢谢搂住
5楼 gugong | 发表于2007-04-28 20:24:56
6楼 mok618 | 发表于2007-04-28 20:29:53
拉格朗日定理时曾相识。
7楼 gugong | 发表于2007-04-28 20:47:20
8楼 515151 | 发表于2007-04-28 21:31:23
这个好,没见过.
9楼 刘可 | 发表于2007-04-29 09:56:35
地球人都知道啊
-------小学五年级的数学题目
[
本帖最后由 刘可 于 2007-4-29 10:01 编辑 ]
11楼回帖是美德!!
12楼 万里挑一 | 发表于2007-10-05 06:51:43
光看好不行啊,要感谢楼主的话就的用于实战
13楼 171887 | 发表于2008-02-07 22:42:29
喂
怎么运用啊
请老师把研究成果再行发布给乐采网的采民享用
14楼 轮到500万 | 发表于2008-03-04 19:04:17
是啊,与实战怎么结合啊大兄弟
15楼 马彩神 | 发表于2008-05-20 17:50:33
,可是不会用
16楼 双色球弥勒佛 | 发表于2008-06-13 09:38:27
这好象是我国的姓陈的那个人算的吧
17楼东西 是好就是不会运用
18楼太有才了
19楼 简单点嘛 | 发表于2010-10-23 21:01:19
以前曾看过类似“隔墙猜数”的书
20楼 吉飞 | 发表于2011-06-03 07:14:59
怎么运用阿,没看明白
22楼剩余定理
24楼 牛牤不流氓 | 发表于2019-11-25 00:15:36
谢谢楼主的提示。
25楼 dxp555 | 发表于2019-11-28 16:42:05
与实战怎么结合啊
26楼大哥你这说了半天,是想说什么,和双色球有什么关系
27楼 bdggch | 发表于2020-03-13 22:20:01
具体怎么用昵。