什么是欧几里得算法？
欧几里得算法（在中国又称"辗转相除法"）是已知最古老的算法之一，由古希腊数学家欧几里得在约公元前 300 年提出。它用来求两个整数的最大公约数（GCD）——也就是能同时整除这两个数、且不留余数的最大那个数。本计算器适用于任意两个非负整数，同时还会给出它们的最小公倍数（LCM）。
如何使用
在标注为 a 和 b 的输入框中分别填入两个数，然后提交即可。计算器会把最大公约数（GCD）作为主结果，把最小公倍数（LCM）作为附加结果一并显示。先后顺序不影响结果——\(\gcd(48, 36)\) 与 \(\gcd(36, 48)\) 完全相等。若输入负数，会按其绝对值处理；若其中一个数为 0，则最大公约数就是另一个数本身。
公式详解
该算法基于一个朴素而巧妙的事实：a 和 b 的任何公约数，同样能整除它们的余数 a mod b。于是我们不断用余数替换较大的那个数：
$$\gcd(a,b) = \gcd(b,\, a \bmod b)$$ 递归的终止条件为 $$\gcd(a,0) = a$$
每一步都会让数字迅速变小，因此即使是很大的数，往往只需几次迭代就能算出结果。算完 GCD 后，最小公倍数即可通过 $$\operatorname{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$$ 求得。
实例演算
求 \(\gcd(48, 36)\)：
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = \mathbf{12}$$
所以最大公约数为 12，最小公倍数 $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = \mathbf{144}$$
常见问题
如果两个数都是 0 怎么办？ 这里规定 0 和 0 的最大公约数为 0；由于不存在任何正的公倍数，最小公倍数也定义为 0。
为什么它比逐个列举因数更快？ 它不去找出所有约数，而是利用求余这一"捷径"，每走一步都能大幅缩小问题规模——其时间复杂度通常为对数级。
能处理非常大的数吗？ 可以。即便是位数很多的数，欧几里得算法依然高效，只需要做少量取模运算即可得到答案。
