最大公约数的定义

最大公因数 | wikipedia

最大公约数 (gcd, greatest common divisor) 或者最大公因数 (hcf, highest common factor) 指能够整除多个非零整数的最大正整数.

整数序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 的最大公约数记为 gcd⁡(a1,a2,⋯ ,an)\gcd(a_1, a_2, \cdots, a_n), 在不引起歧义的情况下也可以记作 (a1,a2,⋯ ,an)(a_1, a_2, \cdots, a_n).

最大公约数的性质

  1. 任意 a 和 b 的公因数都是 gcd(a, b) 的约数

    证明: 设 d = gcd(a, b), 根据贝祖定理 (线性数论定理), 存在整数 x 和 y 使得 xa + yb = d.
    对于 a 和 b 的任意公约数 c 满足 c|a 并且 c|b, 由整除的线性性可以得到 c | (xa + yb) 即 c | gcd(a, b)

  2. gcd 满足交换律: gcd(a, b) = gcd(b, a)
    结论显然, 证明略

  3. gcd 满足结合律: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
    证明: 实际上有下面两个式子成立
    gcd(a, gcd(b, c)) = gcd(a, b, c)
    gcd(gcd(a, b), c) = gcd(a, b, c)
    下面证明第一个式子成立, 第二个式子同理
    设 d1 = gcd(a, gcd(b, c)), 由贝祖定理存在整数 x 和 y 使得 d1 = xa + y·gcd(b, c). 对于任意 a, b, c 的公约数 e 满足 e|a 并且 e|gcd(b,c), 再由整除的线性性有 e|(xa + y·gcd(b, c)) 即 e|d1, 可知 d1 = gcd(a, b, c).
    同理有 gcd(gcd(a, b), c) = gcd(a, b, c).

贝祖定理: 对任意两个整数 a 和 b, 设 d = gcd(a,b), 那么关于未知数 x 和 y 的线性丢番图方程 (贝祖等式): $$xa + yb = m$$ 有整数解 (×, y), 当且仅当 m 为 d 的整数倍. 裴蜀等式有解时必然有无穷多个解.

应用

求多个数的 gcd

在最大公约数函数 gcd(·) 性质 3 的推导中获得过下面的公式

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

根据这个公式可以进一步得到

gcd⁡(a1,a2,⋯ ,an)=gcd⁡(⋯gcd⁡(gcd⁡(a1,a2),a3)⋯an)\gcd(a_1, a_2, \cdots, a_n) = \gcd(\cdots\gcd(\gcd(a_1, a_2), a_3)\cdots a_n)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;

// 辗转相除法
int dual_gcd(int a, int b){
  return b == 0 ? a : dual_gcd(b, a % b);
}

int multi_gcd(vector<int> & arr) {
  int d = arr[0];
  for(int ai : arr)
    d = dual_gcd(d, ai);
  return d;
}

int main() {
  cout << dual_gcd(9, 12) << endl; // 3
  vector<int> arr = {9, 6, 12};
  cout << multi_gcd(arr) << endl; // 3
  return 0;
}