欧几里得算法解二元一次不定方程总结

本文主要是介绍欧几里得算法解二元一次不定方程总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 一.贝祖定理：若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

这篇关于欧几里得算法解二元一次不定方程总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！