最大公约数

两个整数的最大公约数

在数学中，两个或多个整数（不全为零）的最大公约数 （GCD） 是能够整除每个整数的最大正整数。

辗转相除法的数学证明

辗转相除法，又称欧几里得算法（英语：Euclidean algorithm）。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

$$ \begin{aligned} & \forall a,b \in \Z，|a|+|b| \neq 0，证明 \gcd(a,b) = \gcd(b,a \bmod b) \cr 证明：& 若|a| < |b|，则 \gcd(b,a \bmod b) = \gcd(b,a) = \gcd(a,b) \cr & 若|a| \geq |b|，则 \exist q \in \Z，使得 a = q \cdot b + a \bmod b \cr & \gcd(a,b) \neq 0，等式两边同除以 \gcd(a,b) \cr & \frac{a}{\gcd(a,b)} = \frac{q \cdot b}{\gcd(a,b)} + \frac{a \bmod b}{\gcd(a,b)} \cr & \because \gcd(a,b) \mid a，\gcd(a,b) \mid b \cr & \therefore \gcd(a,b) \mid a \bmod b，即 \gcd(a,b)是 b 和 a \bmod b 的一个公约数 \cr & 故 \gcd(a,b) \leq \gcd(b,a \bmod b) \cr & 同理，\gcd(b,a \bmod b) \neq 0，等式两边同除以 \gcd(b,a \bmod b) \cr & \frac{a}{\gcd(b,a \bmod b)} = \frac{q \cdot b}{\gcd(b,a \bmod b)} + \frac{a \bmod b}{\gcd(b,a \bmod b)} \cr & \because \gcd(b,a \bmod b) \mid b，\gcd(b,a \bmod b) \mid a \bmod b \cr & \therefore \gcd(b,a \bmod b) \mid a，即 \gcd(b,a \bmod b)是 a 和 b 的一个公约数 \cr & 故 \gcd(b,a \bmod b) \leq \gcd(a,b) \cr & 综上 \gcd(a,b) = \gcd(b,a \bmod b) \cr & 证毕 \end{aligned} $$

辗转相除法的编程实现

最大公约数的维基百科 指出在编程实现上特别定义了 $\gcd(0,0)=0$，这保留了裴蜀等式的证明。

循环实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int gcd(int a, int b) {
  int remainder = 0;
  while (b != 0) {
    remainder = a % b;
    a = b;
    b = remainder;
  }
  /* 最大公约数是正整数 */
  if (a < 0) {
    a = -a;
  }
  return a;
}

递归实现：

1
2
3
4
5
6
7
8
9

int gcd(int a, int b) {
  if (b != 0) {
    a = gcd(b, a % b);
  }
  if (a < 0) {
    a = -a;
  }
  return a;
}

算法效率：时间复杂度 $O(h^2)$，$h$ 为数字 $a$ 和 $b$ 的平均位数。

上面的代码可以用二进制最大公约数算法优化，但其时间复杂度仍为 $O(h^2)$。

假设用辗转相除法求自然数 $a$ 和 $b(a>b>0)$ 的最大公约数需要 $N$ 步，那么满足这一条件的 $a$ 和 $b$ 的最小值分别是斐波那契数 $F_{N+2}$ 和 $F_{N+1}$。这可以用数学归纳法证明。

任意多整数的最大公约数

$$ \gcd(a,b,c) = \gcd(a,\gcd(b,c)) = \gcd(\gcd(a,b),c) = \gcd(\gcd(a,c),b) $$