DOXA · 数学编年史 · 知识详情

《孙子算经》——中国剩余定理

3–5世纪 | 孙子代数·数论突破

image/svg+xml
中国剩余定理:条带互素重叠

知识/定理

《孙子算经》「物不知数」题:求一数除以 3/5/7 分别余 2/3/2——同余方程组解法,后世称中国剩余定理(CRT)。

公式

$N\equiv2\pmod3,\ 3\pmod5,\ 2\pmod7$ ⇒ 最小解 23;一般 CRT:$N\equiv\sum r_i M_i y_i\pmod{M}$。

证明思路

(算法)以「三人同行七十稀」歌诀给出构造性解法;现代证法用互素模的模逆。

应用/例子

历法置闰、快速大数运算(CRT 加速)、密码学。

意义/影响

数论经典定理,以其名号进入世界数学史;物不知数题为最著名古算题。

所属:三 古印度与中国 | 难题证明状态 ↔ 数学难题编年