数论学习笔记 (4)：扩展欧几里得算法

概述

扩展欧几里得算法 (\(exgcd\)) 可以用来求形如 \(ax+by=c\) 的不定方程的通解。

铺垫 - \(\small\texttt{ax+by=gcd(a,b)}\)的解

\(exgcd\) 的思想是在用辗转相除法递归 \(gcd(a,b)\) 的回溯时求出对应方程 \(ax+by=gcd(a,b)\)的解。

考虑方程 \(ax+by=gcd(a,b)\) 。

看回辗转相除法的代码，我们将他展开一点写。

void gcd(int a,int b){
	if(!b) return a;
	return gcd(b,a%b);
}

注意最后当 \(b=0\) 时，\(gcd(a,b)=gcd(a,0)=a\)，此时当 \(\begin{cases}x=1\\y=0\end{cases}\) 时，\(ax+by=gcd(a,b)\)，于是最终状态下，\(\begin{cases}x=1\\y=0\end{cases}\) 即为其对应方程的解。

接下来，假设我们已经知道了 \(bx+(a\text{ }mod\text{ }b)y=gcd(b,a\text{ }mod\text{ }b)\) 的一组特解 \(\begin{cases}x=x'\\y=y'\end{cases}\)，我们尝试求出 \(ax+by=gcd(a,b)\) 的解。

\(\because ax+by=gcd(a,b)\text{ },\text{ }bx'+(a\text{ }mod\text{ }b)y'=gcd(b,a\text{ }mod\text{ }b)\)

\(\small{且}\text{ }gcd(a,b)=gcd(b,a\text{ }mod\text{ }b)\)

\(\therefore ax+by=bx'+(a\text{ }mod\text{ }b)y'\)

\(\therefore ax+by=bx'+(a-\lfloor\frac{a}{b}\rfloor b)y'\)

\(\small{【变更主元】 得:}\)

\(a(x-y')+b(y-x'+\lfloor\frac{a}{b}\rfloor y')=0\)

\(\small{若想使上式总是成立，只需使：}\)

\(\begin{cases}x-y'=0\\y-x'+\lfloor\frac{a}{b}\rfloor y'=0\end{cases}\)

\(\therefore\begin{cases}x=y'\\y=x'-\lfloor\frac{a}{b}\rfloor y'\end{cases}\)

于是就完成了转换/转移，翻译成代码：

// 不需要知道 gcd(a,b) 是多少，无需返回值
void exgcd(int a,int b,int &x,int &y){ // 传址，直接修改
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int tmp=x;
	x=y,y=tmp-(a/b)*y; // 直接修改
}

简便写法：

void exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x); // 区别：交换x和y的位置，等同于swap(x,y)
	y-=(a/b)*x;
}

扩展 - \(\small\texttt{ax+by=c}\)的解

先来看一个定理：

裴蜀定理：\(ax+by=c\) 有整数解的充要条件是 \(gcd(a,b) \mid c\)

这个定理是显然的，至少你从直觉上就觉得它没问题。

现在我们知道怎么判无解了，那么接下来的探究都建立在 \(ax+by=c\) 有界的情况下，那我们开始吧。

记 \(g=gcd(a,b).\)

\(\therefore g \mid a,g \mid b\)

\(\small{由裴蜀定理：}\)\(g \mid c\)

记 \(a'=\frac{a}{g},b'=\frac{b}{g},c'=\frac{c}{g}.\)

\(\therefore gcd(a',b')=1\)

发现可以用 \(exgcd\) 求出 \(a'x+b'y=1\) 的解\(\begin{cases}x=x'\\y=y'\end{cases}\)！

\(\therefore a'x+b'y=c'\)\(\text{ }\small{的解为}\)\(\begin{cases}x=c'x'\\y=c'y'\end{cases}\)

\(\therefore a'gx+b'gy=c'g\)\(\text{ }\small{即}\text{ }\)\(ax+by=c\)\(\text{ }\small{的解为}\)\(\begin{cases}x=c'x'\\y=c'y'\end{cases}\)

这样我们就找到了一组特解 \(\begin{cases}x=c'x'\\y=c'y'\end{cases}\).

通解即为 \(\begin{cases}x=c'x'+b'k\\y=c'y'-a'k\end{cases}(k \in \mathbb{Z})\).

（证明、代码略）

Tips：
C++ 对负数取模的处理与数学中不一样，如数学中的 \(a\text{ }mod\text{ }b(a \in \mathbb{Z^-})\) 在 C++ 中的值为 \(-(abs(a)\text{ }mod\text{ }b)\).
\(eg:\)
数学：\(-5\text{ }mod\text{ }3=1\)
C++：\(-5\text{ }mod\text{ }3=-2\)
为解决这样的问题，我们一般这么写: ans=(a%b+b)%b