扩展欧几里得算法模板

扩展欧几里得算法

问题：给定两个非零整数$a$和$b$，求一组整数解$(x, y)$ ，使得$ax+by=gcd(a,b)$ 成立（$gcd(a,b)$ 是a、b的最大公约数）。

设
$$
\begin{aligned} ax_1+by_1&=gcd(a, b) \ bx_2+(a%b)y_2&=gcd(b, a%b) \end{aligned}
$$

化简，得递推公式：
$$
\begin{aligned} &x_1=y_2 \ &y_1=x_2-(a/b)y_2 \end{aligned}
$$

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

在得到一组解后，就可以通过下面的式子得到全部解：
$$
\begin{aligned}
x'&=x+\frac{b}{gcd}K \
y'&=y-\frac{a}{gcd}K \
gcd &= gcd(a, b)， K为任意整数
\end{aligned}
$$

方程ax+by=c的求解

问题：求解$ax+by=c$，其中c为任意整数。

$ax+by=c$ 存在解的充要条件是 $c%gcd(a,b)==0$ （即c是$(x,y)$的系数的最大公约数的倍数），且一组解$(x, y)$ 等于$(\frac{cx_0}{gcd},\frac{cy_0}{gcd})$

在得到一组解后，就可以通过下面的式子得到全部解：
$$
\begin{aligned}
x'&=x+\frac{b}{gcd}K = \frac{cx_0}{gcd}+\frac{b}{gcd}K\
y'&=y-\frac{a}{gcd}K = \frac{cy_0}{gcd}-\frac{a}{gcd}K\
gcd &= gcd(a, b)， K为任意整数
\end{aligned}
$$

同余式$ax\equiv c(mod,m)$的求解

同余式：对于整数a、b、m，若$a%m==b%m$ ，即a、b余数相同，则对应的同余式为$a\equiv b(mod,m)$

问题：求解x，$ax\equiv c(mod,m)$ 。

由题可得，
$$
\begin{aligned}
a(x%m)&c%m \
(ax-c)&=my \
ax-my&=c, y=-y \
ax+my&=c \
\end{aligned}
$$
由之前的结论得，当$c%gcd(a,m)0$ 时，方程$ax+my=c$ 有解，该方程的通解为：
$$
\begin{aligned}
x'&=x+\frac{m}{gcd}K \
y'&=y-\frac{a}{gcd}K \
gcd &= gcd(a, m)， K为任意整数
\end{aligned}
$$
对于同余式，改通解有很多解在模m的意义下是相同的，当K取$[0,gcd(a,m))$ 时，所得到的解在模m的意义下不同。

逆元的求解以及$(b/a)%m$ 的计算

（乘法）逆元：设a, b, m是整数，$m>1$ 且 $ab \equiv 1(mod ,m),或,a \equiv \frac{1}{b}(mod , m)$ ，即两数乘积模m后为1，则a和b互为模m的逆元。

问题：假设a、m是整数，求a模m的逆元。

解法一

设x是a模m的逆元，则
$$
(b/a)%m = (b*x)%m
$$
这样可以将除法取模转化为乘法取模，可以解决被除数b非常大（使得b已经去过模，不是原始值）的问题。

因此，求a模m的逆元，就是求解同余式$ax\equiv 1(mod,m)$ ，即求解$ax+my=1$ 。在实际问题中，一般把x的最小正整数解为a模m的逆元。如果$1%gcd(a,m)0, 即gcd(a,m)1$，那么同余式$ax\equiv 1(mod,m)$ 在$(0, m)$ 上有唯一解。

// 求a模m的逆元，使用条件：gcd(a,m)=1
int reverse(int a, int m){
    int x, y;
    int g = exGcd(a, m, x, y);
    return (x%m+m) % m;
}

解法二

如果m是素数，且a不是m的倍数，则可以直接使用费马小定理来得到逆元。

费马小定理：设m是素数，a是任意整数且不是m的倍数（$a\not\equiv 0(mod,m)$），则 $a^{m-1} \equiv1(mod,m)$ 。

由定义可知$a^{m-2}$ 是a模m的逆元，其可由快速幂算法求出。[[../../二分/快速幂|快速幂]]

解法三

如果 $gcd(a,m)\not=1$ ，扩展欧几里得算法和费马小定理均失效，此时a模m的逆元从概念上来讲不存在，但$(b/a)%m$ 仍然是有值的（且为整数），该如何求解？

$$
\begin{aligned}
(b/a)%m&=x \
b/a&=km+x \
b&=kam+ax \
b%(am)&=ax\
b%(am)/a&=x\
(b/a)%m&=b%(am)/a \
\end{aligned}
$$
即$(b/a)%m=b%(am)/a$ ，注意a和m的乘积可能会溢出。