扩展欧几里得算法

扩展欧几里得算法，不仅可以得到整数m和n的最大公约数，还可以得到两个整数a和b，满足am + bn = d，其中，d是gcd(m, n)。

为了描述算法和证明方便，引入两个量c和d，其中d是上文指出的最大公约数，c的初始值是m
算法描述如下：
初始化，a = 0，b = 1，a’ = 1，b’ = 0，c = m，d = n // 步骤1
计算q = c / d，r = c % d // 步骤2
if r == 0:
算法结束，d是最大公约数，a和b就是要求的两个数。
else:
c = d，d = r // 这里和普通的欧几里得算法一致
t = a’，a’ = a，a = t - q * a;
t = b’，b’ = b，b = t - q * b;

现在我们来论证下算法的正确性，关于d为啥是最大公约数我们就不再赘述，因为它是普通的欧几里得算法已经明晰的东西了。
在这个算法中，除了要证明am + bn = d，还有一个辅助证明的等式，或者说是顺带证明的东西，a’m + b’n = c
初始化完成，也就是步骤1完成时，需要证明的两个等式显然成立。
如果r等于0，算法结束，不影响等式。
如果说else分支的一堆赋值操作，如果还是成立的，没有破环等式，那么，我们就证得两个等式成立。
先看这三个赋值语句：
c = d
a’ = a
b’ = b
a’m + b’n = c这个等式就被替换成了am + bn = d，左右两边显然是相等的。
那么第一个等式am + bn = d是否依旧成立呢？
d = r
a = a’ - q * a
b = b’ - q * b
步骤2隐含了一个等式c = qd + r，有了这个，推第一个等式就没有任何问题了
am + bn
= (a’ - qa)m + (b’ - qb)n
= (a’m + b’n) - q(am + bn)
= c - qd
= r
= d
也就是说，经过一系列的变换，两个等式依然成立。
总结下，初始时待证明的两个公式成立，循环不变，最终算法结束时，两个公式依旧成立。
证毕。

下面是一小段程序实现扩展欧几里得算法，写的有点啰嗦，但是是算法描述的直接翻译，很直观：

public static long GetGcd(long m, long n, ref long a, ref long b)
{
    a = 0;
    b = 1;
    long ap = 1; // a'
    long bp = 0; // b'
    long q = m / n;
    long r = m % n;
    while (r > 0)
    {
        m = n;
        n = r;
        long t = ap;
        ap = a;
        a = t - q * a;
        t = bp;
        bp = b;
        b = t - q * b;
        q = m / n;
        r = m % n;
    }

    return n;
}