1071 与 465 走欧几里得算法,经余数 141、42、15、12 抵达最大公约数 3

一路取余直到出现 0;最后一个非零余数就是最大公约数。

方程与代数 · 难度: 经典结论 · 更新于 2026-11-10

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

在计算器里做这道题

下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。

本站为独立第三方工具站,与 Casio、Texas Instruments 及其代理商无隶属、代理或授权关系。型号名与产品名为各权利人商标,仅用于识别机型。

手册中的操作序列依据「本站在线计算器同源布局数据 + 公开产品事实」独立撰写;规格与地区配置以实机与厂商最新资料为准。