一.贝祖定理：若a，b是整数，存在一对 x , y 使得 ax+by = gcd(a,b)。gcd(a,b)表示a和b的最大公约数。

 

二.欧几里得有个十分有用的定理欧几里得算法（辗转相除法）： gcd(a, b) = gcd(b, a%b) 

 

三.求最大公约数：

  若继续递归向下传递则有  gcd(a, b) = gcd(b, a%b) = gcd(a%b,  b%(a%b))...... =gcd(最大公约数，0) ，利用此可以求出a，b的最大公约数。

利用欧几里得求 ax+by = gcd(a,b)，求a，b的最大公约数gcd(a,b)对应的java代码如下：

// 递归到余数为0,求最大公约数。即：欧几里德算法停止的状态是： 参数a = gcd ， b = 0
public static int gcd(int a,int b) {
        return  b == 0 ? a : gcd(b, a % b);
}

 

四. 扩展欧几里得算法，求ax+by = gcd(a,b)，方程的一组特解：

对于方程ax+by = gcd(a,b)，b为0时，方程为： ax = gcd(a,b) ,因为gcd(a,b)是a和b的最大公约数，故x为1。故b为0时，解为 (1,0)

（注：b为0时，x必为1，因为b为0，y无所谓是多少，反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1）

对于方程ax+by = gcd(a,b)，结合gcd(a,b) = gcd(b,a%b)，又可以推导（推导见代码注释）得到关系：ax+by = a*y1 + b*(x1-(a/b)*y1)

通过以上两点：可以递归算出方程ax+by = gcd(a,b)的一组特解，代码如下：

    public static List<Integer> exgcd(int a,int b){
        List<Integer> list=new ArrayList<Integer>();
        // b为0时，方程为： ax = gcd(a,b) ,因为gcd(a,b)是a和b的最大公约数，故x为1。故解为 (1,0),做为递归最底层，递归出口。
        if (b==0){
            list.add(1);
            list.add(0);
            return list;
        }
        list = exgcd(b,a%b);
         /*
             以下逻辑说明：
             （注意a/b表示a除b的商，a%b 表示a除b的余数）
             ax+by = gcd(a,b) --- 等式1
             x,y表示第一次递归时的值，x1,y1表示第二次递归时的值。
             则有 ：gcd(a,b) = gcd(b,a%b)，同时都代入等式1，有ax+by = b*x1+(a%b)*y1。
             将右边变形一下 b*x1+(a%b)*y1 = b*x1+(a-(a/b)*b)*y1 = a*y1 + b*(x1-(a/b)*y1)
             最终得到ax+by = a*y1+b*(x1-(a/b)*y1)
             也就是说，上一深度的x等于下一深度的y1，上一深度的y等于下一深度的x1-(a/b)*y1。
         */
        int k = list.get(0);
        list.set(0, list.get(1));
        list.set(1, k - a/b*list.get(1));
        return list;
    }

 扩展欧几里得算法，对于ax+by = gcd(a,b) --- （1）式 有以下结论，不定方程的通解：

        x = x0 + (b / gcd) * t

        y = y0 – (a / gcd) * t

 说明：x0,y0 为以上方程的一组特解，t为任意整数。推导过程参考链接：https://blog.csdn.net/syz201558503103/article/details/76512144

 

五.判断二元一次不定方程ax+by = c 是否有解：

       c % gcd(a,b) == 0,成立有整数解，否则无整数解。

 

六.求二元一次不定方程ax+by = c 通解：

　　x = x0 * (c/gcd(a,b)) + b/gcd(a, b) * t

　　y = y0 * (c/gcd(a,b)) -  a/gcd(a, b) * t 

  (注：x0，y0，是ax+by = gcd(a,b)对应的特解，其中t为任意整数)

 

参考链接：https://blog.csdn.net/zhjchengfeng5/article/details/7786595

参考链接：https://blog.csdn.net/weixin_41677899/article/details/84089561

参考链接：https://www.luogu.com.cn/blog/lipeiyuan/kuo-zhan-ou-ji-li-dei-yang-xie