当前位置:文档之家› 中国剩余定理

中国剩余定理

中国剩余定理(Chinese remainder theorem),
又称孙子定理。

初等数论里面的一个定理。

名字里自带“中国”,要不要那么高调233。

出处是《孙子算经》:
“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”“答曰二十三”
孙子定理
孙子定理,又称中国剩余定理。

孙子定理是中国古代求解一次同余式组(见同余)的方法。

是数论中一个重要定理。

又称中国余数定理。

一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如下:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。

问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。

《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。

公元前后的《孙子算经》中有“物不知数”问题:“今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几何?”答为
“23”。

明朝程大位用歌谣给出了该题的解法:“三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知。


以现代的说法,是找出三个关键数70,21,15。

解法的意思就是用70乘3除所得的余数,21乘5除所得的馀数,15乘7除所得的余数,然後总加起来,除以105的余数就是答案。

相关主题