裴蜀定理

形式

若 a, b ∈ ℤ，那么对于 ∀x, y ∈ ℤ，gcd (a, b) ∣ a × x + b × y。

此外，一定 ，使得 a × x + b × y = gcd (a, b) 成立。

证明

证明第一点：

证明第二点：

设 a × x + b × y 的最小正整数值为 r，考虑证明 a mod  r = 0。

设 ，则可得 a mod  r = a − p × r​。

代入 r，得到 a mod  r = a − p × (a × x + b × y)。

进一步可得 a × (1 − p × x) + b × (−p × y)，这就是 ax′ + by′​ 的形式。

因为 0 ≤ a mod  r < r，且 r 为 a × x + b × y 的最小正整数值，

所以 a mod  r = 0，即 r 是 a 的因数。

同理可得 r 也是 b 的因数。

所以 r 是 a, b 的公因数，即 r ∣ gcd (a, b)。

又因为 a × x + b × y 都是 gcd (a, b) 的倍数，所以 gcd (a, b) ∣ r。

故 r = gcd (a, b)。

Exgcd

首先考虑欧几里得算法是如何求解 gcd (a, b) 的。

  1. 当 b = 0 时，a 即为 a, b 的最大公约数。
  2. 求出 gcd (b, a mod  b)，设为 g0。
  3. 令 g = g0，g 就是 a, b​ 的最大公约数。

令 d = gcd (a, b) 于是可以仿照这个过程，求解不定方程：

  1. 当 b = 0 时，ax + by = d 的解是 ，y 任意。

  2. 求出 bx + (a mod  b)y = d 的一组解，设为 (x0, y0)。

  3. 令 (x, y) = f((x0, y0))，那么 (x, y) 就是 ax + by = d 的一组解。

    其中 f((x0, y0)) 表示对 (x0, y0) 的一种变换。

现在的问题就是，如何通过 (x0, y0) 得到 (x, y)​。

PS在欧几里得算法中，gcd (a, b) = gcd (b, a mod  b)，故下面的式子中 d 是相等的。

已知 bx0 + (a mod  b)y0 = d，转化形式可得： 将 a, b 提出来，可得 通过待定系数法，可得

具体实现中，在数学上，当最后 b = 0 时 y 可以取任意值，但是如果 y 取得很大的话，中途中可能会超过 int 和 long long 的存储范围。

但是如果最后 b = 0 时 y = 0，那么对于其它的迭代步骤，求解 ax + by = gcd (a, b) 得到的一组解 (x, y) 一定满足：

证明：

PS：这里只考虑 a > b 的情况，显然 a ≤ b 在依次迭代后会变成 a > b 的情况。

首先，当 a mod  b = 0 时，因为 a > b 且 a 是 b 的倍数，所以 a ≥ 2 × b。迭代得到的解 其次，设 bx + (a mod  b)y = gcd (b, a mod  b) 得到的解为 (x0, y0)，满足： 则 ax + by = gcd (a, b) 得到的解 (x, y) 也满足：

  1. ；

  2. 由于 ，，

    所以

又可以发现，设 ax + by = d = k × gcd (a, b)，那么每次得到的解都是在求解 ax + by = gcd (a, b) 时的解的 k 倍，所以不管 d 取多少，在最后的迭代中取 x = k, y = 0 同样是没有问题的。

求出一对解 x0, y0 后，可求出通解为：

时间复杂度与欧几里得算法相同，故时间复杂度为 O(log max {a, b})。

Code

1
2
3
4
5
6
7
8
9
10
11
using lint = long long;

lint exgcd(lint a, lint b, lint &x, lint &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  lint d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}