裴蜀等式与扩展欧几里得算法

裴蜀等式

对于任何整数$a$、$b$和它们的最大公约数$d$，关于未知数$x$和$y$的线性丢番图方程称为裴蜀等式

$$ax+by=m$$有整数解时当且仅当$m$是$d$的倍数

裴蜀等式有解时必然有无穷多个整数解，每组解$x$、$y$都成为裴蜀数，$x$和$y$可用扩展欧几里得算法$(Extended\ Euclidean\ algorithm)$求得

特别地，$ax+by=1$有整数解，当且仅当$a$和$b$互素

拓展欧几里得算法

欧几里得算法地终止状态是$a=gcd,b=0$，那么此时方程$ax+by=gcd$的解$x=1,y$为任意数

当然，上面说的是最终状态，但是我们能否从最终状态反推初始状态？

假设当前要求的是$a$和$b$的最大公约数，并求出$x$和$y$，使得$ax+by=gcd····(Formula\ 1)$

而我们已经求出了下一状态$b$和$a\%b$的最大公约数，并且也求出了一组解$x_1$和$y_1$，使得$b\times x_1 + (a\%b)\times y_1 = gcd$

那么这两个状态之间是否存在某种关系呢？

我们知道$a\%b = a - (a/b)\times b$（这里的/指的是整除），那么可以进一步得到：

$$ \begin{equation}\begin{split} gcd&=b\times x_1+(a-(a/b)\times b)\times y_1 \\ &=b\times x_1+a\times y_1 - (a/b) \times b \times y_1\\ &=a\times y_1 + b\times (x_1-a/b\times y_1)···(Formula\ 2) \end{split}\end{equation} $$

对比$Formula\ 1$和$Formula\ 2$，我们发现一个递推式

$$ \begin{equation}\begin{split} &x = y_1\\ &y = x_1 - a/b\times y_1 \end{split}\end{equation} $$

其中，$x$和$y$分别是递归时第$i$层$ax+by=gcd$的一组解，$x_1$和$y_1$分别是递归时第$i+1$层$ax_1+by_1=gcd$的一组解

我们上面推到的其实都是$ax+by=d$的解，$d=gcd(a,b)$，对于一般的情况$m$为$d$的倍数，则有$ax+by=m$的解为$x \times \frac{m}{d}$和$y \times \frac{m}{d}$

public class exgcd {
    static long x, y;
    static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long x1 = x;
        x = y;
        y = x1 - (a / b) * y;
        return res;
    }
    /*
     * 线性方程 ax + by = m 当m为gcd(a,b)的倍数时有整数解
     */
    static long linearEquation(long a, long b, long m) throws Exception {
        long d = exgcd(a, b);
        if (m % d != 0)
            throw new Exception("无解");
        long n = m / d;
        x *= n;
        y *= n;
        return d;
    }
    
    public static void main(String[] args) {
        try {
            linearEquation(2, 7, 1);
            System.out.println(x + " " + y);
        } catch (Exception e) {
            System.out.println("无解");
        }
    }
}