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
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。