扩展的欧几里德算法

刺骨的言语ヽ痛彻心扉 2022-04-22 11:18 192阅读 0赞

**扩展欧几里得算法**  
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然  
存在整数对 x，y ，使得 gcd（a，b）=ax+by。

**简介扩展欧几里得算法**  
扩展欧几里得算法的功能就更强大了，它可以用来求二元一次方程的通解，还可以用来求乘法逆元。  
在此顺便简介一下乘法逆元：  
若有 a\*x ≡ 1 （mod m），则称 x 为a关于m的乘法逆元，等价式 a \* x+m \* y = 1  
这就也是个二元一次方程了，ExGcd可搞。

**算法实现**  
我们依旧递归实现，因为上一次的x，y与下一次的x，y的值有关，所以我们从x=1，y=0（此时b=0）的情况开始递归上来，套公式就好了。（a，b下去，x，y上来）  
伪代码：

int exGcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;y=0;
            return a;
        }
        int r=exGcd(b,a%b,x,y);
        int t=x;x=y;y=t-a/b*y;
        return r;
    }

**求解 x，y的方法的理解**  
设 a>b。  
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；  
2，a>b>0 时  
设 ax1+ by1= gcd(a,b);  
bx2+ (a mod b)y2= gcd(b,a mod b);  
根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);  
则:ax1+ by1= bx2+ (a mod b)y2;  
即:ax1+ by1= bx2+ (a - \[a / b\] \* b)y2=ay2+ bx2- \[a / b\] \* by2;  
\**（a mod b = a - \[a / b\]b；\[a / b\]代表a整除b）*  
也就是ax1+ by1 == ay2+ b(x2- \[a / b\] \*y2);  
根据恒等定理得：x1=y2; y1=x2- \[a / b\] \*y2;  
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.  
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。  
由引理我们知道：ax+by = z，z为gcd（a，b）若干倍，所以我们先求解ax+by = gcd（a，b），再将求出的解乘以 z/gcd（a，b）就好了。  
java 实现代码如下：

public static long[] extend_gcd(long a,long b){
    	    long ans;
    	    long[] result=new long[3];
    	    if(b==0)
    	    {
    	    	result[0]=a;
    	    	result[1]=1;
    	    	result[2]=0;
    	        return result;
    	    }
    	    long [] temp=extend_gcd(b,a%b);
    	    ans = temp[0];
    	    result[0]=ans;
    	    result[1]=temp[2];
        	result[2]=temp[1]-(a/b)*temp[2];
    	    return result;
    	}

--------------------

返回的数组中，第一个值是最大公约数，第二个值表示C++语言实现中的x，第三个值表示y。

原文：[https://blog.csdn.net/zs064811/article/details/55000930][https_blog.csdn.net_zs064811_article_details_55000930]  
原文：[https://blog.csdn.net/leader\_one/article/details/75222771][https_blog.csdn.net_leader_one_article_details_75222771]

[https_blog.csdn.net_zs064811_article_details_55000930]: https://blog.csdn.net/zs064811/article/details/55000930
[https_blog.csdn.net_leader_one_article_details_75222771]: https://blog.csdn.net/leader_one/article/details/75222771