扩展欧几里得算法

有时我们需要求解类似于 $ax+by=m$ 的不定方程（丢番图方程），扩展欧几里得算法就是求解这样方程的利器。

除此以外我们可以通过简单地变形处理模逆元和线性同余方程。

裴蜀定理/贝祖定理（Bezout’s Lemma）

$\forall a,b \in \mathbb{Z}$ 且 $a,b$ 不同时为零，方程

有整数解，当且仅当

证明：

当 $a,b$ 其一为 $0$ 时，假设 $a=0$ 则 $(a,b)=b$ 显然只有 $b \mid m$ 时 $0x + by=m$ 有解，且为无穷多解（$x$ 为任意值）。

当 $a,b$ 全不为 $0$ 时，设

我们知道 $A \cap \mathbb{N}^+$ 是非空的（其中至少有 $|a|$，$|b|$），由于 $\mathbb{N}^+$ 是良序的，因此我们设 $A \cap \mathbb{N}^+$ 的最小元为

考虑 $A$ 中任意元素 $p=x_1 a + y_1 b$ 对 $d_0$ 的带余除法，则

其中 $q>0,0 \le r < d_0$。

此时

由 $d_0$ 是 $A$ 中最小正元，而 $0 \le r < d_0$ 且 $r \in A$ 则 $r=0$

也就是说

由 $p$ 是 $A$ 中任意元素，则 $d_0 \mid a$，$d_0 \mid b$，从而得出

又有 $(a,b)\mid a,(a,b) \mid b$，则

从而得出

必要性：

当 $ax+by=m$ 有解，则由 $(a,b) \mid a,(a,b) \mid b$ 得出 $(a,b) \mid m=xa+yb$

充分性：

当 $(a,b) \mid m$，此时我们知道 $m=m_0 d_0$，

由 $d_0 = x_0a+y_0b$

则我们至少有解 $x=x_0m_0, y=y_0 m_0$。

如果还想进一步证明解是无数多的，可以看通解形式部分。

通解形式

考虑构造解。 $x$ 增加 $\Delta x$，

由于最终 $x,y \in \mathbb{Z}$ ，而我们已知 $x_0m_0,y_0m_0 \in \mathbb{Z}$，也就是说我们需要 $\Delta x, \Delta y \in \mathbb{Z}$。

对于 $\frac{a}{b}$ 我们可以考虑把分子分母的最大公因数 $(a,b) = d_0$ 除掉得到 $\frac{a'}{b'}$。

此时要满足

由 $(a',b') = 1$ 则

于是我们得到其通解

都是方程的解，且彼此不同（$a,b$ 均不为 $0$ 则显然 $x$ 彼此不同），即解有无穷组。

构造一组特解

上述过程中我们只是证明了解的存在性和解之间的关系，但其实有一个重点问题没有解决，我们如何找到一组 $x_0,y_0$，满足不定方程 $ax+by=(a,b)$。

扩展欧几里得算法算法首次接触难以理解的一个原因是因为这是一个构造算法，因此思维上存在一定的跳跃性。它巧妙地利用了欧几里得算法的过程推导出了一条特解。

首先我们设 $g=(a,b)$

（1）考虑方程 $g \cdot x+0 \cdot y=g$ 我们可以不假思索的给出一组特解

而对应的系数 $a_0,b_0$ 刚好是我们在辗转相除求 $(a,b)$ 过程中的最后一步的系数。其实 $y_0$ 可以选择任意整数，但是选择 $0$ 我们可以将特解限制在较小的范围，见下。

（2）我们发现对于辗转相除的过程，如果 $a'=b,b'=a%b$ 我们发现对于这两组系数，我们有相同的最大公约数 $g$，则

我们递归知道 $x',y'$ 的值之后，可以反过来构造 $x,y$ 则

通过比较系数，我们可以得到一组 $x,y$

因此我们只需要递归求解 $(a,b)$ 然后回溯时求解 $x,y$ 就可以得出原不定方程的一组解了。

特解的范围

这里我们可以进一步研究一下特解的范围，因为反推的过程如果构造的特解过大，就可能因为溢出而无法使用。

我们发现当 $a=0$ 或 $b=0$ 时递归只会进行不超过两层，这样最终解的值为 $x=0,y=1(a=0)$ 或 $x=1, y=0(b=0)$。

同样如果输入 $a=b$ 时递归只会进行两层，这样最终得出的值为 $x=0,y=1$。

如果输入的 $a,b$ 不同，则取模操作不会让两个参数在递归的过程中变得相同（总会是一个比另一个更小）这里我们假设输入的 $a>0,b>0,a\neq b$，来看一下对应的 $a,b,x,y$ 的值：

我们发现除了第 $0$ 行，总有 $|x|<b,|y|<a$ 成立。

这里可以尝试证明一下，假设 $a',b',x',y'$ 是上一层递归的参数和结果，则假设 $|x'| < b', |y'| < a'$ 成立。

我们有

对于 $x$，有

对于 $y$, 有

如果 $x'$ 与 $y'$ 同号则

得证。

至此我们终于可以书写代码了。

代码

void exgcd(LL a,LL b,LL &g,LL &x,LL &y)
{
	if(!b)
    {
        g=a; x=1; y=0;
    }
	else
    {
        exgcd(b,a%b,g,y,x); // 巧妙地利用参数顺序，调整好了对应的 x,y
        y-=a/b*x;
    }
}

扩展欧几里得算法的应用

求解不定方程

显然这个算法可以用来求解形如 $ax+by=m$ 的不定方程嘛。

不过做题的过程一般情况是问解是否存在，寻找 $x,y$ 满足某些条件的特解，或者是问 $x,y$ 满足某些条件时的解的个数。

解是否存在的问题其实根据裴蜀定理和 GCD 就已经足够求解了。对于满足某些条件的特解，相当于我们要先将通解的形式写出来，然后求解通解符合条件的方案。

求解线性同余方程

对于线性同余方程 $ax \equiv b \pmod m$ 我们可以简单的变形为

之后进行求解。我们也可以知道这个方程有解的条件是 $b|(a,m)$。以及根据我们推导的结论，求出的 $|x|$ 会在 $[0,m)$。

求解逆元

更进一步的，其实我们令上面同余方程中的 $b = 1$，于是根据模下乘法逆元的定义求出的 $x$ 即为模下逆元（注意可能是负的，需要调整到 $[0,m)$）。

LL inv(LL a,LL m)
{
    LL g,x,y;
    exgcd(a,m,g,x,y);
    if(g!=1) return -1; // no inverse element
    x%=m; if(x<0) x+=m;
    return x;
}