1071 mod 465 是 141。465 mod 141 是 42。141 mod 42 是 15,42 mod 15 是 12,15 mod 12 是 3,最後 12 mod 3 是 0。最後一個非零餘數 3 就是最大公約數,而每一步都站得住,理由相同:任何同時整除 a 與 b 的數也整除 a − qb,所以一對數和它的餘數有一模一樣的因數。這裡全程不需要分解質因數,這才是實用之處——在任何人知道 1071 為什麼是 3·357 之前,3 已經是答案了。
值得盯的是步數。拉梅在 1844 年證明:一對整數的歐幾里得演算法所需步數不超過較小者十進位位數的大約五倍,而最壞情形恰是相鄰的費波那契數——這一頁上的 141、42、15、12、3 縮得很快,正因為沒有一步踩在費波那契鄰居上。同一張餘數表的推廣版本還會順帶給出滿足 3 = 1071s + 465t 的係數,那正是電腦代數系統裡每一段取模除法例程的原料。
答案
3
口徑說明
15 mod 12,最後一個非零餘數。前兩個連結是開頭的兩步,1071 mod 465 = 141 與 465 mod 141 = 42。
出處
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進螢幕——答案就是上面那一行,可以自己核對。