最大公因数

关于最大公因数的性质与求法。

更相减损术

对于任意的整数 并且 ，有 。

相比于欧几里得算法，更相减损术可以方便的解决高精度最大公因数问题。

证明

对于 的任意公因数 ，有 ，则 。所以 公因数的集合与 公因数的集合相同，即 。

欧几里得算法

对于任意的整数 和不为 的整数 ，有

相比于更相减损术，欧几里得算法速度更快。

证明

若 ，则 ，即 。

若 ，令 ，其中 。即 。对于 的任意公因数 ，有 ，所以 ，故 ，即 。所以 公因数的集合与 公因数的集合相同，即 。

写成代码为

int Gcd(int a, int b) {
  if (b == 0)
    return a;
  return Gcd(b, a % b);
}

裴蜀定理（Bezout）

设 是不全为零的整数，则存在整数 ，使得 。

证明

当 时，。

当 时，因为 ，不妨设 。假设存在一对整数 ，满足 。因为 ，令 ，则有 。

推论

• 互质的充分必要条件是存在整数 ，使得 。
• 有解的充分必要条件为 。
• 设 为 个整数， 是它们的最大公因数，则存在 ，使得 。

扩展欧几里得算法

根据裴蜀定理，可知

写成代码为

int ExGcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int gcd = Exgcd(b, a % b, x, y), tmp = x;
  x = y, y = tmp - y * (a / b);
}

也可以写成

int ExGcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int gcd = Exgcd(b, a % b, y, x);
  y -= x * (a / b);
  return gcd;
}