exgcd

exgcd&逆元

简介

用于求方程形如　ax + by = gcd(a,b) 的一个特解（亦可用此解推出所有解）。

算法

递归求解，其实本质是用方程

bx + (a mod b)y = gcd(b,a mod b)

的解递推出方程

ay0 + bx0 = gcd(a,b)

的解。具体递推关系为

x0 = y, y0 = x - a/b*y

递归的边界条件为当a mod b递归至0，则必有gcd(a,b)=b，则此时方程为

bx = b

则x=1，y为任意值，不妨设它为0.

递推关系的证明很显然，直接将模的形式化为除的形式（a mod b = a - a/b*b），然后以a，b为主元变形后将a，b的系数直接相等，即可得到递推关系。

下面考虑求其它解

设已知一个解(x0,y0)，欲求解(x,y)，则由定义

ax0 + by0 = gcd(a,b) = ax + by

简单变形得

a(x - x0) = b(y0 - y)

由定义，必有

gcd(a,b) | a ，gcd(a,b) | b

则两边同除以gcd(a,b)得

a'(x - x0) = b'(y0 - y)

其中a'与b'互质，则必有

b' | (x - x0)，a' | (y0 - y)

则两边同除以b'，得

a'k = y0 - y

y = y0 - a'k

又有

b'k = x - x0

x = x0 + b'k

则其它解为(x0 + b'k , y0 - a'k)其中k可取任何整数。

下面考虑将方程中的 gcd(a,b)推广至任意整数c

即ax + by = c

首先，这个方程不一定 有解，方程有解条件为

gcd(a,b) | c

且这是一个充分必要条件。

证明如下

gcd(a,b) | a , gcd(a,b) | b

gcd(a,b) | (ax + by)

所以必有

gcd(a,b) | c

才能使方程有解且必有解。

注意到，此方程要么无解，要么有无数解。

tip：观察这个方程的形式，它也是一个直线方程，方程有解的意义便是该直线过整点。

下面考虑有解情况下解的求法，因为

gcd(a,b) | c

设

c = k*gcd(a,b)

然后可以先求方程

ax + by = gcd(a,b)

的解(x0,y0)

则易得原方程解为(kx0,ky0)

应用

求逆元

即求a在mod p剩余系下的逆元x

则ax = 1(mod p)

即ax - 1 = kp

ax - kp = 1

按前面方程的形式判断有解以及求解即可