隨這道題傳下來的口訣給的是一套做法,不是一通搜尋。取三個餘數 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
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進螢幕——答案就是上面那一行,可以自己核對。