浅谈拓展欧几里得算法

1、求特解 $x_0,y_0$

普通的欧几里得算法依据是辗转相除法，也就是，比如求$a，b$ 的最大公约数，$a，b$ 进行辗转相除直到 $a-b$ 或者 $b-a$ 等于0，证明此时的原先 $a,b$ 的最大公约数就是当前的 $a$，例子如下：

a = 16, b = 6
a > b, a = a - b = 10
a > b, a = a - b = 4
b > a, b = b - a = 2
a > b, a = a - b = 2
a = b = 2 = gcd(a, b)
可见a > b必须减到a < b截至，
故多步的减法可以合成一个 %
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
1
2
3
4
5
6
7
8
9
10
11

有了上面的了解，我们就可以知道，欧几里得算法的底层原理，那么思考下面一个问题，给出 $a,b$，求出一组特解 $x_0,y_0$ 满足下面表达式。
$a\ast x+b\ast y=gcd(a,b)$
同样的，我们根据辗转相除法的思路，当 $b=0$ 的时候找到最大公约数，此时 $a\ast 1+0\ast y=gcd(a,0)=a$，故此时的 $x=1,y=0$。
假如我们的递归如下：

int exgcd(int a, int b, int x, int y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;  // ？
    return d;
}
1
2
3
4
5
6
7
8
9

$?$ 处为什么可以那样写，我们假定当前层：
$a\ast x+b\ast y=gcd(a,b)$
下一层：
$b\ast y+(a-a/b\ast b)\ast x=gcd(a,b)$
化简：
$a\ast x+b\ast y-a/b\ast b\ast x=gcd(a,b)$
$a\ast x+b(y-a/b\ast x)=gcd(a,b)$

2、求通解 $x,y$

对于一般方程，$a\ast x+b\ast y=c$，当 $gcd(a,b)|c$ 时才有解，我们定义 $d=gcd(a,b)$ 此时的解是：
$x_0=x\ast c/d$，$y_0=y\ast c/d$
对于特解 $x_0,y_0$ 当 $x_0$ 移动 $n$ 格：
$x=x_0+n$
$(x_0+n)\ast a+y\ast b=d$
$y=y0-a/b\ast n$
转化后：
$x=x_0+b\ast n$
$y=y_0-a\ast n$
发现 $x$ 每次变化 $b$ 个单位并不是最小单位，故通解如下：
$x=x_0+b/d\ast k$
$y=y_0-a/d\ast k$

3、求最小正整数解

通解得到之后，如果 $x>0$ 那么最小正整数解就是 $x\%(b/d)$。
否则最小正整数解就是 $(x\%(b/d)+(b/d))\%(b/d)$。
故最小正整数解就是 $(x\%(b/d)+(b/d))\%(b/d)$。