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

裴蜀等式

对于任何整数 $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("无解");
        }
    }
}