扩展欧几里得算法 - Exgcd

· · 个人记录

前置 - 欧几里得算法

\gcd(a,b) = \gcd(b,a\bmod b) \Large \text 证明

令 d = \gcd(a,b)， c = a \bmod b = a - k \times b（k = \left \lfloor \frac{a}{b} \right \rfloor ）。

\therefore 若 \gcd(a,b) = \gcd(b,a \bmod b)，则\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k。 \because \frac{a}{d}-\frac{b}{d}k 为整数 \therefore \frac{c}{d} 为整数 \therefore d \mid c

所以 d 为 b,c 的公因数。

接着：

设 d \mid b,~d\mid (a \bmod b)，我们还是可以像之前一样得到以下式子

$\because$ 左边式子显然为整数 $\therefore \frac{a}{d}$ 也为整数，即 $d \mid a$，所以 $b,a\bmod b$ 的公约数也是 $a,b$ 的公约数。 既然两式公约数都是相同的，那么最大公约数也会相同。 所以得证。 # 扩展欧几里得 - Exented gcd > 主要用来求解线性同余方程和不定方程（这两个是等价的） ## 1.求特解 设一个不定方程为： $ax + nk = b

其中 x 和 k 是未知数。有整数解的充要条件为 \gcd(a,n) \mid b。 可以先用扩展欧几里得算法求出一组 x_0,k_0，也就是 ax_0+nk_0=\gcd(a,n)，然后两边同时除以 \gcd(a,n)，再乘 b。就得到了方程：

a\dfrac{b}{\gcd(a,n)}x_0+n\dfrac{b}{\gcd(a,n)}k_0=b

于是找到方程的一个解。

2.所有整数解

若 \gcd(a,n)=1，且 x_0、k_0 为方程 ax+nk=b 的一组解，则该方程的任意解可表示为：

x=x_0+nt k=k_0-at

并且对任意整数 t 都成立。

实际问题中，往往要求出一个最小整数解，也就是一个特解：

x=(x \bmod t+t) \bmod t

其中有 t=\dfrac{n}{\gcd(a,n)}

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