首页 > 数学相关 > 数论应用 > 扩展欧几里得算法
2014
04-09

扩展欧几里得算法

欧几里得算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。基本算法:设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。 证明略去了。

基本代码实现:

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

 扩展欧几里得算法

扩展欧几里德算法是欧几里得算法的扩展。

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式ax + by = \gcd(a, b).。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

用类似辗转相除法,求二元一次不定方程47x+30y=1的整数解。

  • 47=30*1+17
  • 30=17*1+13
  • 17=13*1+4
  • 13=4*3+1

然后把它们改写成“余数等于”的形式

  • 17=47*1+30*(-1) //式1
  • 13=30*1+17*(-1) //式2
  • 4=17*1+13*(-1) //式3
  • 1=13*1+4*(-3)

然后把它们“倒回去”

  • 1=13*1+4*(-3) //应用式3
  • 1=13*1+[17*1+13*(-1)]*(-3)
  • 1=13*4+17*(-3) //应用式2
  • 1=[30*1+17*(-1)]*4+17*(-3)
  • 1=30*4+17*(-7) //应用式1
  • 1=30*4+[47*1+30*(-1)]*(-7)
  • 1=30*11+47*(-7)

得解x=-7, y=11。

基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。

证明:设 a>b。

  推理1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;//推理1

  推理2,ab!=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;

  根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;//推理2

     这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.

   上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

扩展欧几里德的递归代码:

#include <iostream>
using namespace std;

int exgcd(int a,int b,int & x,int & y){
	if(b == 0){
		//根据上面的推理1,基本情况
		x = 1;
		y = 0;
		return a;
	}
	int r = exgcd(b, a%b, x, y);
	//根据推理2
	int t = y;
	y = x - (a/b)*y;
	x = t;
	return r;
}

int main() {
	int x,y;
	exgcd(47,30,x,y);
	cout << "47x+30y=1 的一个整数解为: x=" << x << ", y=" << y << endl;
	return 0;
}

非递归实现,比上面的看上去要复杂了不少,不熟悉的话直接用上面的就可以:

int exgcd(int m,int n,int &x,int &y)
{
    int x1,y1,x0,y0;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}

扩展欧几里德算法的应用

(1)求解不定方程

用扩展欧几里得算法解不定方程ax+by=c;

这个应该比较好理解了,两个可以同乘以k

bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //求得的只是其中一组解
    return true;
}

(2)求解模线性方程(线性同余方程

同余方程 ax≡b (mod n) (也就是 ax % n = b) 对于未知数 x 有解,当且仅当 gcd(a,n) | b (也就是 b % (gcd(a,n))==0 )。且方程有解时,方程有 gcd(a,n) 个解。

求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)

在方程  3x ≡ 2 (mod 6) 中, d = gcd(3,6) = 3 ,3 不整除 2,因此方程无解。

在方程 5x ≡ 2 (mod 6) 中, d = gcd(5,6) = 1,1 整除 2,因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。

证明略去,直接说算法:

首先看一个简单的例子:

5x=4(mod3)

解得x = 2,5,8,11,14…….

由此可以发现一个规律,就是解的间隔是3.

那么这个解的间隔是怎么决定的呢?

如果可以设法找到第一个解,并且求出解之间的间隔,那么就可以求出模的线性方程的解集了.

我们设解之间的间隔为dx.

那么有

a*x = b(mod n);

a*(x+dx) = b(mod n);

两式相减,得到:

a*dx(mod n)= 0;

也就是说a*dx就是a的倍数,同时也是n的倍数,即a*dx是a 和 n的公倍数.为了求出dx,我们应该求出a 和 n的最小公倍数,此时对应的dx是最小的.

设a 和 n的最大公约数为d,那么a 和 n 的最小公倍数为(a*n)/d.

即a*dx = a*n/d;

所以dx = n/d. (d = gcd(a,n) )

因此解之间的间隔就求出来了.

bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //特解
    for(i=1;i<d;i++)
        printf("%d\n",(x0+i*(n/d))%n);
    return true;
}

 (3)求解模的逆元;

同余方程ax≡b (mod n),如果 gcd(a,n)== 1,则方程只有唯一解。

在这种情况下,如果 b== 1,同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

这时称求出的 x 为 a 的对模 n 乘法的逆元。

对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1,x, y 为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

练习题

青蛙的约会

参考:http://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E5%90%8C%E4%BD%99%E6%96%B9%E7%A8%8B

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。