中国剩余定理

AUTHOR: Locez
VERSION: 1

什么是中国剩余定理?


中国剩余定理是数论中关于一元线性同余方程组的定理,说明了一元线性同于方程组有结的准则以及求解方法。《孙子算经》中有一题:

1
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

这个题目翻译过来的意思就是:

1
一个整数除以 3 余 2, 除以 5 余 3, 除以 7 余 2,求这个整数是什么?

同时这也是韩信点兵的故事的来源,韩信让士兵们依次按 3 人一排,5 人一排, 7 人一排进行排列整队,每次只数最后一排的人,便可算出总人数

而韩信点兵与上面的题目同理,数最后一排的人数,也即数余数。3, 5, 7 这种小的数可以枚举,也可以有口诀,但是当这些除数很大,要怎么求解这些一元线性同余方程组,就是中国剩余定理要解决的了。

Read More