欧几里得算法最大公约数计算器

输入计算

数值 1

数值 2

结果

https://example.com

最大公约数

4

最大公约数（GCF，又称 GCD）

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

什么是欧几里得算法？

最大公约数（英文记作 GCD 或 GCF）是能够同时整除两个整数的最大正整数。欧几里得算法，也就是我们常说的"辗转相除法"，是一种历史悠久且效率极高的求解方法，它通过反复做带余除法来得到结果。本计算器可以求出任意两个整数的最大公约数，并展示每一步的除法过程，方便你跟着推演。

欧几里得算法用尽可能大的相等正方形铺满矩形——该正方形的边长就是最大公约数。

如何使用

在数值 1 和 数值 2 中分别输入两个整数。计算器会把较大的数作为被除数、较小的数作为除数，不断相除，直到余数为 0。最后一个非零的除数就是最大公约数。两个数的输入顺序不影响结果，正负号也会被忽略，因为最大公约数只与数值的大小有关。

公式解析

每一步都要算出商和余数：\(a = c \times b + R\)，其中 \(c = \lfloor a / b \rfloor\)（向下取整的商），\(R = a \bmod b\)（余数）。接着把 \(a\) 换成 \(b\)，把 \(b\) 换成 \(R\)，重复这一过程。由于每一步的余数都严格小于上一步的除数，运算必然会终止。当 \(R = 0\) 时，当前的除数就是答案。用递归表示就是：

$$\gcd(a, b) = \gcd(b, a \bmod b),\quad \gcd(a, 0) = a$$

Advertisement

实例演示

求 GCF(816, 2260)。令 \(a = 2260\)，\(b = 816\)。

$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$

当除数为 4 时余数变为 0，所以 GCF(816, 2260) = 4。

每一步用 (b, a mod b) 替换 (a, b)，直到余数为 0；最后一个非零除数即为最大公约数。

常见问题

GCF 和 GCD 是一回事吗？ 是的。英文里 "greatest common factor"（最大公因数）和 "greatest common divisor"（最大公约数）是同义词，本工具两者都能算。

如果其中一个数是 0 怎么办？ \(\gcd(a, 0) = a\)，因为任何数都能整除 0。但如果两个数都是 0，最大公约数则没有定义。

能求三个数的最大公约数吗？ 可以两两运用本工具：\(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\)。