最大公约数（Greatest Common Divisor, GCD）详解
一、定义
最大公约数，又称最大公因数或最高公因数，是两个或多个整数共有的最大的那个正整数约数。对于任意两个非零整数a和b，如果存在一个整数d，使得d是a和b的约数，且d大于或等于a和b的其他所有公共约数，则称d为a和b的最大公约数。
二、性质
- 交换律：gcd(a, b) = gcd(b, a)。即求两个数的最大公约数与这两个数的顺序无关。
- 结合律：gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)。即三个数的最大公约数可以分步求解。
- 分配律：gcd(ab, ac) = |a| * gcd(b, c)，其中|a|表示a的绝对值。
- 与0的关系：任何数与0的最大公约数是该数本身（0除外），因为0不是任何非零整数的约数。
- 相等关系：如果gcd(a, b) = a，那么说明a是b的约数，或者a=b（两数相等时）。
- 互质关系：如果gcd(a, b) = 1，则称a和b互质，即它们没有其他公共的正整数约数除了1以外。
三、计算方法
列举法：直接列出a和b的所有约数，然后找出其中最大的一个。这种方法适用于较小的数。
辗转相除法（欧几里得算法）：这是计算两个整数最大公约数的一种高效方法。具体步骤如下：
- 用较大数除以较小数，得到余数r；
- 然后将前一步的除数作为新的被除数，余数r作为新的除数，继续除法是直到余数为0为止；
- 此时的前一个除数即为所求的最大公约数。
例如，求gcd(48, 18)：
- 48 ÷ 18 = 2 余 12
- 18 ÷ 12 = 1 余 6
- 12 ÷ 6 = 2 余 0
- 因此，gcd(48, 18) = 6。
更相减损术：这也是一种古老的求最大公约数的方法，尤其适用于古代没有除法运算的情况下。其原理是基于以下事实：两个正整数的最大公约数等于其中较小的数和两数之差的最大公约数。具体步骤是反复用较大的数减去较小的数，直到两数相等，这个相等的数就是它们的最大公约数。
四、应用
最大公约数在数学、计算机科学、密码学等领域有着广泛的应用。例如，在分数化简中，需要找到分子和分母的最大公约数以进行约分；在数组去重、排序等算法设计中，也会用到最大公约数的概念来优化算法性能。此外，在密码学中，最大公约数也是某些加密算法的重要基础之一。
