欧几里得算法计算器
结果
最大公因数
- 逐步过程
- 1071 = 2 * 462 + 147; 462 = 3 * 147 + 21; 147 = 7 * 21 + 0
辗转相除法（也叫欧几里得算法）能在不分解任何一个数的前提下，求出两个整数的最大公因数。它靠的是一条事实：若 a = q * b + r，那么凡是能同时整除 a 与 b 的数也整除 r，凡是能同时整除 b 与 r 的数也整除 a——所以 (a, b) 与 (b, r) 这两对数的公因数完全相同。把这对数换成更小的那一对，重复。每一轮两个数都在变小，而它们不可能一直小下去，于是一定有一个变成零，另一个就是答案。1071 与 462 的过程是 1071 = 2 * 462 + 147，接着 462 = 3 * 147 + 21，接着 147 = 7 * 21 + 0——最大公因数是 21。三轮，两次减去若干倍，全程没有分解过任何东西。最后这一点才是这套方法值得知道、而不只是值得用的原因：要找一个大数的因数，你得试到它的平方根；而它只拿一个数去除一个手上已有的数，而且数掉得很快。610 与 377 这两个相邻的斐波那契数是最坏的情形，各自只有三位，却要走满十三轮。轮数不由数量级决定。1000000 与 999998 比 610 与 377 大得多，两轮就结束，因为第二步就落在了整数倍上；反过来 610 与 377 要走十三轮。在同样的位数下轮数最多的，永远是相邻的两个斐波那契数，这个结论有名字——拉梅定理——下面那张表专门留了一列轮数，就是这个原因。两个数给的顺序无所谓。先把它们按从大到小摆好是这一页自己的选择而不是方法的要求，也正因为这样，462 与 1071 印出来的三行和 1071 与 462 逐字相同。过程写成带余除法的等式而不是竖式：每一轮是 a = q * b + r，轮与轮之间用分号隔开。把一轮当一句话读——1071 是 2 个 462 再加 147——下一轮就是把这句话里的角色往后挪一格：462 是 3 个 147 再加 21。一轮的余数成为下一轮的除数，除数成为下一轮的被除数。
三组数走一遍算法，以及各自要走多少轮
| 第一个数 | 第二个数 | 轮数 | 最大公因数 |
|---|---|---|---|
| 1071 | 462 | 3 | 21 |
| 48 | 180 | 3 | 12 |
| 36 | 36 | 1 | 36 |
右边两列要合起来读，因为它们并不同步。前两行都走三轮，第三行走一轮——但再看答案那一列：36 与 36 一轮给出 36，而 48 与 180 走三轮给出 12，1071 与 462 走三轮给出 21。数的大小对这两列都不说明任何事。一对数更大不等于算得更久，算得更久也不等于答案更大。轮数那一列说明的是原因：36 与 36 当场就塌缩，因为第二个数整除第一个，循环第一趟就停了；而 48 与 180 是一路淌到 36、再淌到 12 的，中间没有一步是整除。一般情形下最坏的是相邻两个斐波那契数，这也是本页上面的算例用 1071 与 462 这一对（讲这套算法时通常用的那对）而不是用一对更大、反而更快结束的数的原因。
公式
a ＝ q × b ＋ r，则 gcd(a, b) ＝ gcd(b, r)；一直推到 r ＝ 0，此时的 b 就是答案
- a = q * b + r
- 一轮算法，写成一条等式。a 是这一轮里较大的那个数，b 是较小的那个，q 是 b 能整个装进 a 几次，r 是剩下的。这就是本页过程串的记法本身：1071 = 2 * 462 + 147 就是一轮
- a, b
- 被比较的这两个数。它们的身份每一轮都在换——这一轮的 b 变成下一轮的 a，余数 r 变成新的 b。正是因为这样，两个输入框不叫「被除数」与「除数」：第一轮里 1071 是被除数，第二轮里变成 462 了，一个只对某一轮正确的标签在别的轮上就是错的
- q
- 商，即 b 整个装进 a 几次。它永远至少是 1，因为循环开始之前这对数已经按从大到小摆好了——这也是你在这一页上看不到 q = 0 的原因。唯一一轮商不起眼的是最后一轮：余数为零，除法正好整除
- r
- 余数，永远小于 b，也永远不为负。这套算法的停止条件是 r = 0，而它是作为最后一轮印出来的，不是省略掉的：147 = 7 * 21 + 0 这一行就是「找完了，答案是 21」
- gcd(a, b)
- 最大公因数：能同时整除 a 与 b 的最大的整数。答案是最后一轮的 b，直接取自循环，不是另算一遍。1071 与 462 的答案是 21，所以 1071 = 21 × 51、462 = 21 × 22，而没有比 21 更大的数能同时整除两者
- 610 = 1 * 377 + 233
- 最坏情形的开场：相邻的两个斐波那契数。这一串里每一个商都是 1，两个数几乎不见变小，这才让这对数走满十三轮。拉梅定理说的就是：同样位数下没有比这更费轮数的数对
约分是日常用法。要把 462/1071 化成最简分数，你需要这两个数的最大公因数，而这一页把它连同证据一起交出来——21，以及得出它的那三轮。上下同除以 21 得 22/51，而印出来的过程让你能核对这次约分，而不是只能相信它。同样的需要在任何要化简比的地方出现：齿轮比、屏幕宽高比、比例尺图纸，以及任何你想写成比例而不是写成一对数的两个量。第二种用处在编程与课业里，这套算法被当作第一个有意思的算法来讲：它会停、它快、而且它为什么对，一条等式里就看得见。求模逆元的标准做法也是它——扩展版本在同一条路上多带两个数——而模逆元正是 RSA 生成密钥时的那一步。第三种用法是给分解做体检：发现 1071 是 3 × 357、462 是 2 × 3 × 7 × 11 是要干活的，而发现它们的最大公因数是 21 只需要三次除法，所以先跑这一页能告诉你化简会不会轻松。只要答案不要过程时，gcf-calculator 用更短的形式问同一个问题，而且一次能收多于两个数；lcm-calculator 拿这个因数去求最小公倍数，因为 lcm = (a / gcd) * b；remainder-calculator 讲的是单次余数在数可以为负时是什么意思，而这一页不必处理那种情形。
算例
教科书里的那一对：1071 与 462
- 462 装进 1071 几次？两次，2 × 462 = 924，剩下 1071 − 924 = 147
- 现在这对数是 462 与 147：147 装进 462 三次，3 × 147 = 441，剩下 21
- 现在这对数是 147 与 21：21 装进 147 正好七次，剩下 0
- 余数是零，算法停下，答案是 21
这一页的默认输入，也是讲这套算法时通常用的那个例子。结果值得做两项核对。把两个数都除以 21 得 51 与 22，它们没有公因数，这正是 21 之所以「最大」而不只是「一个」公因数的原因。另外注意全程没有分解：要找 1071 的因数得试到 32，而算法只是反复把一个数除以手上已有的那个。三轮，一轮比一轮便宜。
一轮就够：12 与 60
- 先把这对数摆成大数在前：60，12
- 60 = 5 × 12 + 0，也就是 12 整除 60
- 余数当场为零，算法一轮就停
- 答案是 12——两个数里较小的那个，因为它整除较大的那个
最短的一段非平凡过程，也是「最后一轮为什么要印出来」最清楚的例子。60 = 5 * 12 + 0 这一行就是全部答案：它说明余数到了零，而那是这套算法唯一的停止方式。去掉这一行，过程就是空的，读者分不清这是「一轮算完」还是「根本还没跑」。只要一个数整除另一个，最大公因数就是较小的那个。
互质的一对：9 与 20
- 20 = 2 × 9 + 2，于是这对数变成 9 与 2
- 9 = 4 × 2 + 1，于是变成 2 与 1
- 2 = 2 × 1 + 0，算法停下
- 答案是 1，也就是说 9 与 20 除了 1 没有别的公因数
最大公因数是 1 是一个正经答案而不是失败，它有个名字：这两个数互质。它同时也是「9/20 已经是最简分数」的信号，没有可约的余地。注意过程并没有塌缩——两个数谁也没整除谁，算法一路走到 1，走了三步。数一大，互质反而是常态：随手取两个数，它们有公因数的机会掉得很快，而这正是这套方法在密码学里能用来构造模逆元的原因。
局限
两个数都必须是整数，且都在 1 到 1000000 之间。零是拒绝而不是当成特例处理。a 与 0 的最大公因数是 a，那本来是个好答案，但这一页展示不了它：第一轮会是 a = q * 0 + r，而那个 q 不存在。与其印一段中间有洞的过程，这一页选择不收这个输入。负数出于同样的理由被拒绝——印出来的过程假定两个数都至少是 1，而负的操作数需要一条「商与余数分别是什么意思」的规则，这一页在任何地方都没有声明这条规则。1000000 这个上界与算法本身无关，它在大得多的数上照样跑得动；设这个上界是为了路上每一次减法、乘法与取余都在普通的双精度算术里精确，也为了让印出来的过程不至于长到读不下去。两个相当小的数仍然可能走出很多轮——610 与 377 要走十三轮——但轮数实际被这个上界压住了，参考表专门有一列轮数让你看到它的变化。过程印成等式（a = q * b + r，用分号连接）而不是竖式，所以如果你在找那个熟悉的除法括号，这一页不会给你。两个输入是可互换的：这一页在开始之前会把它们按从大到小摆好，所以你没法用这一页看到 3 = 0 * 5 + 3 长什么样，因为那一轮永远不会被产生。如果你的数可以是负的，或者你想看到余数在两种约定下的含义，那个问题是 remainder-calculator 的辖区。
常见问题
- 一句话说，最大公因数是什么？
- 能同时整除两个数、不留余数的最大的整数。1071 与 462 的最大公因数是 21：1071 = 21 × 51、462 = 21 × 22，而 51 与 22 没有公因数，这就是 21 之所以「最大」的原因。注意 3 和 7 也同时整除这两个数——它们是公因数，只是不是最大的那个。这一页的主结果永远是这个数，下面那段过程是它的证据。
- 为什么最后一步总是以 + 0 结尾？
- 因为余数为零是唯一能让这套算法停下来的事。循环把这对数换成更小的一对——第二个数，以及余数——而数每一轮都在变小，所以迟早会到零。147 = 7 * 21 + 0 就是到零的那一轮，最大公因数就是那一轮的除数 21。这一页把它印出来而不是藏起来，是因为一段停在最后一个非零余数上的过程，会把「已经找完了」这件事留给读者自己去发现。
- 两个数输入的顺序有影响吗？
- 没有。这一页在第一轮之前就把它们按从大到小摆好，所以输 462 与 1071 印出来的三行和输 1071 与 462 逐字相同。这是选择而不是算法的性质——gcd(a, b) = gcd(b, a) 保证两种顺序都对——但不摆的话，3 与 5 的第一行会读成 3 = 0 * 5 + 3，那是一次合法的除法，却读起来像「小数除以大数」是这套方法的一部分。这也是两个输入框叫「第一个数」「第二个数」而不是「被除数」「除数」的原因：那两个角色每一轮都要对调。
- 答案是 1 是什么意思？
- 说明两个数除了 1 没有别的公因数，这是一个完整的答案而不是失败。这样的两个数叫互质，本页的 9 与 20 就是一例。它还告诉你一件实用的事：分数 9/20 已经是最简形式，没有可约的。数越大，互质反而越常见，这也是这套方法在密码学里重要的原因——生成 RSA 密钥，就是找出与一个给定的数没有公因数的数。
- 数越大，轮数一定越多吗？
- 不一定，下面那张参考表就是为这件事准备的。1000000 与 999998 两轮就结束，而 610 与 377 各只有三位却要走十三轮。决定轮数的不是大小，而是两个数变小的速度有多慢，而缩小得最慢的是相邻的两个斐波那契数，它们每一轮的余数都接近除数。这条结论叫拉梅定理，它给轮数定了一个只随位数增长的上界，这也是这套算法被认为很快的原因。
- 这和直接把两个数都分解开有什么不同？
- 分解要干的活多得多，而这一页从来不干那个活。要用试除法分解 1071，你得试到它的平方根，也就是 32 上下；算法则是拿一个数去除一个手上已经有的数，三轮就结束。对这么小的数，差别看不出来，但数一大，分解会急剧变难，而辗转相除法几乎不受影响。这道差距正是它到今天还被讲的原因，也是上面那个答案取自循环、而不是另算一遍的原因——两处都算，就得承担「印出来的过程和上面那个数对不上」的风险。
参考资料
- Euclidean Algorithm——递推式 gcd(a, b) = gcd(b, a mod b)、它为什么一定会停的证明，以及它与连分数的联系 — Wolfram MathWorld（美国）
- Greatest Common Divisor——最大公因数的定义，以及为什么 gcd(a, 0) = a 是算法停下的那个基准情形 — Wolfram MathWorld（美国）
- Lamé's Theorem——同样位数下轮数最多的永远是相邻两个斐波那契数，这一条结论 — Wolfram MathWorld（美国）
- 教育部关于印发义务教育课程方案和课程标准（2022 年版）的通知——该通知的附件清单第 5 项是《义务教育数学课程标准（2022 年版）》；最大公因数是小学高年级数与代数领域的内容，原文与学段要求以该附件为准 — 中华人民共和国教育部