《孙子算经》运用中国剩余定理巧妙解题_奥数数论问题_奥数知识点-查字典奥数网
 
请输入您要查询的关键词

《孙子算经》运用中国剩余定理巧妙解题

2010-06-29 11:18:05     标签:中国剩余定理

我国古代数学名著《孙子算经》载有一道数学问题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?”这里的几何指多少的意思。翻译成数学语言就是:求正整数N,使N除以3余2,除以5余3,除以7余2。

如何求符合上述条件的正整数N呢?《孙子算经》给出了一个非常有效的巧妙解法。术曰:“三、三数之剩二,置一百四十;五、五数之剩三,置六十三;七、七数之剩二,置三十,并之,得二百三十三。以二百一十减之,即得。凡三、三数之剩一,则置七十;五、五数之剩一,则置二十一;七、七数之剩一,则置十五。一百六以上,一百五减之,即得。”

过了一千多年,到了十六世纪,数学家程大位在他所著的《算法统宗》里把这个问题的解法用歌诀形式表述出来。三人同行七十稀, 五树梅花廿一枝,七子团圆正月半,除百零五便得之。

歌诀的前三句给出了三组数,后一句给出了一个数:

3 70

5 21

7 15

105

三组数的共同特征是:

70除以3余1,除以5、7余0; 21除以5余1,除以3、7余0; 15除以7余1,除以3、5余0。

首先程大位把不同的余数问题统一化为标准的余数问题。然后,他把复杂难解的问题化解为三个易解的问题。70、21、15分别是满足第一、二、三行条件的最小解。

2×70满足原题第一个余数条件,且被5、7整除。

3×21满足原题第二个余数条件,且被3、7整除。

2×15满足原题第三个余数条件,且被3、5整除。

统统相加得和:N=2×70+3×21+2×15=233。

N必然满足原题所有三个余数条件。但N不一定是最小的。歌诀最后一句“除百零五便得知”,这里“除”的意思是“减”,意即从233中减去3、5、7的最小公倍数105的倍数便得到23。这个23就是问题的最小解。这最后一句也可以理解为N除以105的余数就是问题的最小解。

查看全部
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关文章
热门文章
最新文章
猜你喜欢