【初等数论】裴蜀定理&扩展欧几里得算法

裴蜀定理：

对于(a,bin N^*, x, yin Z)，方程(ax+by=k)当且仅当(gcd(a, b)|k)时有解。

证明：

必要性显然。

充分性：只需证明当(k=gcd(a, b))有解。

设(s)为令方程有解的最小(k)值，(gcd(a, b) = d)，首先有(d|s)。

设$t = lfloor frac{a}{s} floor,r = a mod s $

则(r = a - t * s = a - (ax + by)*t = (1-tx)*a + byt)

那么(r)也是(a,b)的线性组合，即存在(x, y)令(ax + by = r)有整数解。

又(r in [0, s))

( herefore r = 0)

即(s|a)，同理(s|b)。

( herefore s|d)，即(s = d)

证毕。

---

扩展欧几里得算法

​ 裴蜀定理告诉我们，方程(ax + by = k)当且仅当(gcd(a, b)|k)时存在无数组整数解。扩展欧几里得算法可以递归求出该方程的一组解，结合各组解之间的关系便有了解该方程的一般方法。

基于欧几里得算法的核心性质：(gcd(a, b) = gcd(b, a mod b) (b eq 0))

如果找到(bx + (a mod b)y = d)的一组解(x_1, y_1)，并且通过待定系数法确定(x,y)和(x_1, y_1)的关系，我们就可以解出(x, y)了。

解：

对于方程(dx + 0*y = d)（边界），显然有一组解((1, 0))

设(gcd(a, b) = d)，对于方程(ax + by = d)，我们递归求解得方程(bx_1 + (a mod b)y_1 = d)的解。

设(lfloor frac{a}{b} floor = q)，则(a mod b = a - q * b)

有(bx_1 + (a - qb)y_1 = d)

即(ay_1 + b * (x_1 - qy_1) = d)

对比系数得( x=y_1,y = x_1 - lfloor frac{a}{b} floor * y_1)。

​函数的递归结构由此确定，最终返回的为方程(ax + by = gcd(a, b))的一组解(x_0, y_0)。

如果(frac{k}{d} = s)，那么(x = sx_0, y = sy_0)。

现在我们着手来考虑方程(ax + by = k (gcd(a, b)|k))通解的形式。

不妨设通过扩欧得到的一组解为(x_0, y_0)，任意解(x = x_0 + Delta x,y = y_0 + Delta y)

消元得(a(x - x_0) + b(y - y_0) = 0)

即(aDelta x = -bDelta y)

设(a = pd, b = qd)

则(frac{Delta x}{Delta y} = -frac{q}{p})

最终得到通解的形式为(x = x_0 + kq, y = y_0 - kp (k in Z))

解毕。

代码：

int exgcd(int a, int b, int& x, int&y) {  
    if (!b) {  
        x = 1, y = 0;  
        return a;  
    }  
    int ret = exgcd(b, a % b, y, x);  
    y -= a / b * x;  
    return ret;//return gcd(a, b)  
}