欧几里得算法

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

最大公约数gcd(a, b)： 能够同时整除a和b的自然数中最大的一个

如果有gcd(a, b)==1，则有a，b互质

a和b的最大公约数g是a和b的线性和中（绝对值）最小的一个，即所有形如ua + vb（其中u和v是整数）的数中（绝对值）最小的数。
所有ua + vb都是g的整数倍（ua + vb = mg，其中m是整数）。

int Gcd(int a, int b) {     if(b == 0)         return a;     return Gcd(b, a % b); }

通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

当b'==0时， 则a'为gcd(a, b)最大公约数.  所以递归必定存在出口。

由上面证明可得， {x,y} 可由递归得到

    static class ExGcd {
        int gcd;
        int x;
        int y;

        public ExGcd(int gcd, int x, int y) {
            this.gcd = gcd;
            this.x = x;
            this.y = y;
        }
    }

    private static ExGcd exgcd(int a, int b) {
        // a*x + b*y = gcd(a,b)
        if (b == 0) {
            return new ExGcd(a, 1, 0);
        }

        ExGcd re = exgcd(b, a % b);
        // x = y'  ,  y = x' - a/b*y'
        return new ExGcd(re.gcd, re.y, x' - a / b * re.y);
    }

求解不定方程