辗转相除法和裴蜀定理

数论基础第二弹！

内容基本来自 OI-Wiki。

又称欧几里得算法，算法关键在于

$$ \gcd(a,b)=\gcd(b,a\bmod b). $$

证：不妨设 $a>b,a=qb+r$，则 $r=a\bmod b$，设 $d\mid a,d\mid b$，则 $\dfrac{r}{d}=\dfrac{a}{d}-\dfrac{bk}{d}$。

由上式，$\dfrac{r}{d}$ 为整数，即 $d\mid r$，所以对 $a,b$ 的公约数，也是 $b,r$ 的公约数。

反过来，设 $d\mid b,d\mid r$，则 $\dfrac{a}{d}=\dfrac{r}{d}+\dfrac{bk}{d}$。

显然 $\dfrac{a}{d}$ 是整数，即 $d\mid d$，故 $b,r$ 的公约数也是 $a,b$ 的公约数。

既然公约数相同，那么最大公约数也相同。

容易写出递归版：

int gcd(int a, int b) { return b? gcd(b, a % b): a; }

欧几里得算法的最坏时间复杂度为 $O(n)$，这里 $n$ 是输入数据在二进制下的长度。换句话说，复杂度是 $O(\log a)$（默认 $a,b$ 同阶）。

证：

• $a\lt b$ 时，下一次迭代到 $\gcd(b,a);$
• $a\ge b$ 时，下一次迭代到 $\gcd(b,a\bmod b)$，而 $a\bmod b$ 至少让 $a$ 折半，即该过程最多发生 $O(\log a)=O(n)$ 次。

情况一发生后一定会发生情况二，故前者发生次数不多于后者发生次数。

因此最多递归 $O(n)$ 次。

欧几里得算法达到最坏时间复杂度仅当输入数据是斐波那契数列¹的相邻两项。

由于取模的时间常数高（尤其在高精运算中不可忽视），我们可以利用加减法代替乘除。

更相减损术的核心是： $$\gcd(a,b)=\gcd(b,a-b).$$

注意到若 $a\gg b$，时间开销将不可接受，若能进行高效除以 $2$ 的操作（如位运算），可以进行优化。

若 $2\mid a,2\mid b$，则 $\gcd(a,b)=2\gcd\left(\dfrac{a}{2},\dfrac{b}{2}\right);$

不然，若 $2\mid a$（$2\mid b$ 同理），$\gcd(a,b)=\gcd\left(\dfrac{a}{2},b\right).$

由于两次操作内 $a,b$ 之一必将减半，时间复杂度为 $O(\log a).$

设 $a,b$ 是不全为零的整数，对任意整数 $x,y$，满足 $\gcd(a,b)\mid ax+by$，且存在整数 $x,y$，使得 $ax+by=\gcd(a,b).$

前者显然，后者构造即可，下面进行构造。

不妨设 $a\ge b,\gcd(a,b)=1$，使用归纳法，若 $b=0$，此时 $a=1$，显然有一组解 $x=1,y=0;$

不然，假设我们已知 $(a\bmod b,b)$ 为系数时的一组解 $(x_0,y_0)$，尝试推出 $(a,b)$ 为系数的一组解：

$$ \begin{aligned} (a\bmod b)x_0+by_0&=1;\\ (a-\left\lfloor\dfrac{a}{b}\right\rfloor b)x_0+by_0&=1;\\ ax_0+b(y_0-\left\lfloor\dfrac{a}{b}\right\rfloor x_0)&=1. \end{aligned} $$

故解为 $(x_0,y_0-\left\lfloor\dfrac{a}{b}\right\rfloor x_0)$，由数学归纳法，对任意 $\gcd(a,b)=1$，均能构造 $(x,y)$ 使 $ax+by=1$，进而原命题得证。

裴蜀定理的逆定理也成立。

容易写出代码：

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

由于函数在求最大公因数的过程中计算可行解，这种算法被称作扩展欧几里得算法。

有时我们担心，扩展欧几里得算法给出的可行解过大，使得变量发生溢出；幸运的是，可以证明，上述算法给出的解满足 $|x|<b,|y|<a.$

归纳法易证。

裴蜀定理可以扩展到 $n$ 元，以三元为例，考虑三元一次不定方程 $ax+by+cz=d.$

令 $ax+by=(a,b)w$，由二元裴蜀定理，对于所有的 $w\in\mathbb{Z}$，都存在 $a,b\in\mathbb{Z}$ 使等式成立。

原方程变为 $(a,b)w+cz=d$，由二元裴蜀定理，方程有解当且仅当 $((a,b),c)\mid d$，即 $(a,b,c)\mid d$。

运用一次扩展欧几里得算法可以构造出一组 $(w,z)$，进而构造一组 $(x,y,z)$。

类似地，$n$ 元一次不定方程只需运用 $n-1$ 次扩展欧几里得算法即可得到一组解。

对于自然数 $a,b$ 和整数 $n$，$a,b$ 互质，考察不定方程

$$ ax+by=n, $$

其中 $x,y$ 为自然数。若方程有解，简称为 $n$ 可以被 $a,b$ 表示。

记 $C=ab-a-b$，则对任意整数 $n$，$n$ 和 $C-n$ 中，有且仅有一个可以被 $a,b$ 表示；$0$ 可被表示，$C$ 不可被表示；负数不可被表示，大于 $C$ 的数均可被表示。

考虑证明。

设方程的一组解为 $(x,y)$，其中 $0\le y\le a-1$，易知这样的 $y$ 是唯一的。

1. 证明大于 $C$ 的数均能被表示：当 $n>C$， $$ ax=n-by\gt ab-a-b-by\ge ab-a-b-b(a-1)=-a, $$

   即 $x>-1$，此时 $x$ 非负。

2. 证明 $C$ 不可被表示：反证法，设存在自然数 $x,y$ 使 $ax+by=ab-a-b$，则 $$ ab=a(x+1)+b(y+1) $$

   由 $a,b$ 互质，$x+1$ 被 $b$ 整除，$y+1$ 被 $a$ 整除；故 $a$ 不大于 $y+1$，$b$ 不大于 $x+1$，故 $$ ab=a(x+1)+b(y+1)\ge 2ab, $$

   矛盾！

3. 证明若 $n$ 不可被表示，$C-n$ 可被表示：由于已限定 $0\le y\le a-1$，$x<0$，有 $$ C-n=ab-a-b-ax-by=a(-x-1)+b(a-1-y), $$

   显然此时 $-x-1,a-1-y$ 均不小于零。