最大公约数（Greatest Common Divisor，简称GCD），也称最大公因数，是指两个或多个整数共有约数中最大的一个。例如，12和18的公约数有1、2、3、6，其中最大的是6，所以gcd(12, 18) = 6。

如果两个数的最大公约数为1，则称这两个数互质。例如，8和15互质，因为gcd(8, 15) = 1。

辗转相除法，又称欧几里得算法（Euclidean Algorithm），是求两个正整数最大公约数的最古老且最高效的算法，由古希腊数学家欧几里得在《几何原本》中首次描述，距今已有2300多年历史。

核心原理：gcd(a, b) = gcd(b, a mod b)，即用较大的数除以较小的数，取余数，然后用除数和余数重复此过程，直到余数为0，此时的除数即为最大公约数。

举例：求gcd(48, 18)：

1. 48 ÷ 18 = 2 余 12 → 转为求gcd(18, 12)
2. 18 ÷ 12 = 1 余 6 → 转为求gcd(12, 6)
3. 12 ÷ 6 = 2 余 0 → 余数为0，GCD = 6

辗转相除法的正确性基于一个关键定理：如果 a = b × q + r（其中0 ≤ r < b），那么gcd(a, b) = gcd(b, r)。

证明思路：设d是a和b的公约数，则d整除a和b，那么d也整除r = a - b×q。反之，如果d整除b和r，则d也整除a = b×q + r。因此(a, b)的公约数集合与(b, r)的公约数集合完全相同，最大公约数自然也相同。

每次辗转，数字都在变小，最终必然在有限步内达到余数为0，算法必定终止。

求多个数字的GCD利用了GCD运算的结合律：gcd(a, b, c) = gcd(gcd(a, b), c)。

具体做法：先求前两个数的GCD，得到中间结果，再用这个中间结果与第三个数求GCD，依此类推，直到处理完所有数字。本工具会自动展示这个级联计算过程，每个阶段都清晰可见。

例如求gcd(48, 18, 30)：先求gcd(48, 18) = 6，再求gcd(6, 30) = 6，最终结果为6。

对于两个正整数a和b，有重要公式：a × b = gcd(a, b) × lcm(a, b)。

即：LCM(a, b) = |a × b| / GCD(a, b)。这意味着只要知道GCD，就能快速求出LCM。本工具在计算结果时会同步展示LCM，方便您同时获取这两个常用值。

注意：该公式仅适用于两个数。对于多个数的LCM，需要逐对计算：lcm(a, b, c) = lcm(lcm(a, b), c)。

辗转相除法的时间复杂度为O(log min(a, b))，非常高效。即使处理上千位的大整数，也只需几百次除法运算。

最坏情况出现在两个连续的斐波那契数上。例如F(10)=55和F(9)=34，辗转相除需要约9步。一般来说，步数不超过较小数位数的5倍。

这使得辗转相除法成为现代密码学（如RSA算法）中处理大整数GCD的标准方法。

更相减损术出自中国古代数学著作《九章算术》（约公元1世纪），其原理是：用较大数减去较小数，然后用差和较小数重复此过程，直到两数相等。

对比：

• 辗转相除法使用除法取余，步数少，效率高，适用于大数。
• 更相减损术使用减法，步数可能较多（如两数相差悬殊时），但运算更简单。

现代计算中，辗转相除法（欧几里得算法）是标准选择，而更相减损术更多体现了古代数学的智慧。

GCD在数学和计算机科学中有广泛应用：

• 分数化简：分子分母同时除以它们的GCD，得到最简分数。如48/18的GCD=6，化简为8/3。
• 密码学：RSA加密算法依赖大数的GCD计算来生成密钥。
• 节奏分析：音乐中不同节奏型的对齐点可通过GCD计算。
• 网格布局：设计等分网格时，GCD帮助确定最小重复单元。
• 调度问题：多个周期性任务的同步时间点计算。