[数论] 扩展欧几里得算法（exgcd）

SXqwq's Library / 2024-07-08 / 原文

前置知识

欧几里得算法

我们首先了解一下朴素欧几里得算法（辗转相除法）。

定理：$\gcd(a,b)=\gcd(b,a\%b)$、

简要证明

令 $a=kb+r,d|a,d|b$（即 $d$ 是 $a,b$ 的任意一个公因数），且 $a,k,b,r$ 均为正整数，$r\ne 0$.

由 $a=kb+r$ 得 $r=a-kb$. 且 $a\%b=r$.

等式左右同除以 $d$，得 $\frac{r}{d}=\frac{a}{d}-k\frac{b}{d}$.

$∵d|a,d|b$

$∴\frac{a}{d}-k\frac{b}{d}$ 为正整数.

即 $\frac{r}{d}$ 为正整数.

$∴ d|r$

所以对于 $\forall d$,都满足 $d|(a\%b),d|b$,得证.

运用欧几里得算法我们可以在 $O(\log n)$ 的时间复杂度内求出任意两数的 $\gcd$.当然常用的 __gcd 库也运用了欧几里得算法.

__gcd 函数内容供参考

template<typename _Mn, typename _Nn>
    constexpr common_type_t<_Mn, _Nn>
    __gcd(_Mn __m, _Nn __n)
    {
      return __m == 0 ? __detail::__abs_integral(__n)
	: __n == 0 ? __detail::__abs_integral(__m)
	: __detail::__gcd(__n, __m % __n);
    }

裴蜀定理

定理1

有 $a,b\in \mathbb{Z}$，那么一定存在整数 $x,y$ 使得 $ax+by=\gcd(a,b)$.

证明

我们只需证明 已知 $x',y'$ 是方程 $bx+(a\mod b)y=d$ 时的一组特解，能够求出 $ax+by=d$ 的解 即可.

已知

\[a\mod b = a-\lfloor\frac{a}{b}\rfloor \times b \]

显然成立.

将上式代入方程 $bx+(a\mod b)y=d$,得:

\[bx'+ay-\lfloor\frac{a}{b}\rfloor \times by=d \]

提公因式，得:

\[ay+b(x'-\lfloor\frac{a}{b}\rfloor)=d \]

注意到上式与方程 $bx+(a\mod b)y=d$ 是等价的，即得

\[\begin{matrix} \left\{ \begin{array}{lr} x=y', & \\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{array} \right. \end{matrix} \]

由此我们证明，若已知方程 $bx+(a\mod b)y=d$ 的解，能够求出 $ax+by=d$ 的解.而我们在欧几里得算法中,证明了 $\gcd(a,b)=\gcd(b,a\%b)$,递归求解到 $a\%b=0$ 时求解出当前方程唯一解，层层回溯即可求出方程 $ax+by=\gcd(a,b)$ 的解.证毕.

定理2

若方程 $ax+by=c$ 有整数解，则方程满足 $\gcd(a,b)|c$,否则方程无整数解.

证明

设 $a=p\times \gcd(a,b),b=q\times \gcd(a,b)$.

代入方程得:

\[p\times \gcd(a,b)\times x+q \times \gcd(a,b) \times y = c \]

提取公因式，得:

$c=(px+py)·\gcd(a,b)$

已知 $x,y$ 为整数，得:

$\gcd(a,b)|c$.

证毕.

定理3

若 $ax+by=1$ 存在整数解,那么 $\gcd(a,b)=1$,即 $a,b$ 互质.

证明

同样设 $a=p\times \gcd(a,b),b=q\times \gcd(a,b)$.

代入方程得:

\[p\times \gcd(a,b)\times x+q \times \gcd(a,b) \times y = 1 \]

方程两边同除以 $\gcd(a,b)$,得:

\[px+qy=\frac{1}{\gcd(a,b)} \]

因此，若 $\gcd(a,b)>1$,即 $a,b$ 不互质，$px+qy<1$，因为 $p,q$ 为正整数，故方程不存在整数解.证毕.

exgcd

事实上，在裴蜀定理1中，我们的证明过程即为 exgcd 的求解过程。

exgcd 通常解决类似于这样的问题，给定 $a,b\in\mathbb{N^*},d=\gcd(a,b)$,求方程 $ax+by=d$ 的一组整数解.

这里给出 exgcd 的模板代码.

#include <bits/stdc++.h>
#define LL long long
using namespace std;
void exgcd(int a, int b, LL &x, LL &y)//注意 x 跟 y 是引用，因为要修改
{
    if (b == 0) {x = 1; y = 0; return ;} // gcd 算到头，准备回溯
    exgcd(b, a % b, x, y);
    LL p = x; x = y; y = p - ((LL)a / b) * y;//回溯的时候套用裴蜀定理1中推导出来的公式
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a;
	cin>>b;
	LL x = 0, y = 0;
	exgcd(a, b, x, y); 
	cout<<x<<" "<<y<<endl;
	return 0;
}