随这道题传下来的口诀给的是一套做法,不是一通搜索。取三个余数 2、3、2,分别乘 70、21、15——这三个数是挑过的:70 ≡ 1 (mod 3) 而在 5 与 7 下余 0,21 ≡ 1 (mod 5),15 ≡ 1 (mod 7)。工作台把 70·2 + 21·3 + 15·2 加到 233;减去两份 3·5·7 = 105,剩下 23,就是最小的答案。反过来验:23 mod 3 是 2,23 mod 5 是 3,23 mod 7 是 2。
定理说的是:模数两两互素时,这组同余在模数之积之下恰有一个解,所以 23 是 0 到 104 之间唯一的答案,其余每个解都是 23 + 105k。这套构造对任意多个同余都成立,而同样的代数出现在离算术很远的地方:它就是中国剩余定理同构 Z/105 → Z/3 × Z/5 × Z/7,是一个数可以同时被几个小模数哈希校验的原因,也是剩余数系算术里那步明确的重建——用它做精确求和——的骨架。
答案
23
口径说明
工作台上的 233 mod 105。第一个链接用口诀的三个系数 70、21、15 造出 233;第三个印出三个余数里的第一个,2。
出处
Sunzi suanjing (Master Sun's Mathematical Manual, c. 400 CE) poses the problem 'there is an unknown number, divided by 3 it leaves 2, divided by 5 it leaves 3, divided by 7 it leaves 2'; the general constructive rule appears in Qin Jiushao's Shushu Jiuzhang of 1247, and the theorem in its modern form belongs to Euler's work on congruences before Gauss put it in the Disquisitiones Arithmeticae of 1801 — which is why the theorem is called Chinese in the West
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。