扩展欧几里德算法总结

内容

获得更好的阅读效果，请到这里

引入

对于一类特殊的丢番图方程，它是恒定有整数解的。它的形式就是：

这其实就是贝祖定理的主要内容。接下来我们来证明一下：

注：下文，

设，则。由于整除的性质，，则有。设为的最小正值，则。

令所以也是的一个线性组合。由于是的线性组合的最小值，，可得。则，同理，则，因此，证毕。

而已知，求的一组可行解的算法叫做扩展欧几里德算法。

流程

我们可以试着求解一下

设

1.当，显然可得。

2.当时：

设

由欧几里德算法，我们可得

则：

由于

我们可以把它给拆开：

由于恒等定理

我们就可以得到了求解的方法。以上的思想是递归定义的，因为的求解过程中，一定会有，所以递归会结束。

当时，即为最大公因数。这时只需要保证的系数即即可，的取值是没有影响的，不妨设。

代码

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

应用

求解丢番图方程

丢番图方程就是引入中的例子，形如一类的方程。我们可以先把等式两边都除以，如果不能整除则就是无解。

那么现在就变成了为了满足扩欧的条件使，可以将等式两遍同时除以c，得到。这样就可以直接利用exgcd求出和的值，然后再乘回去就可以了。

求出来可行解了之后再将不断，不断，解仍然成立。

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;
}

求解模线性方程

结论

同余方程对于未知数有解，当且仅当。且方程有解时，方程有个解。

解法一

求解方程相当于求解方程

设，假如整数和，满足 (用扩展欧几里德得出)。如果，则方程，两边乘以，(因为，所以能够整除)，得到。

所以为的一个解，所以为的解。

的一个解为，且方程的个解分别为。

解法二

首先看一个简单的例子：

解得

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

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

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

我们设解之间的间隔为.

那么有

;

两式相减，得到:

;

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

设和的最大公约数为,那么和的最小公倍数为.

即;

所以.

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

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;
}

求解乘法的逆元

定义

乘法在模p意义下的逆元是什么呢？

可以通俗的理解一下。在模运算法则中，我们只说了

//模运算法则
//
//(A + B) % C = (A % C + B % C) % C
//
//(A - B) % C = (A % C - B % C) % C
//
//(A * B) % C = (A % C) * (B % C) % C
//
//(A / B) % C = ???

最后的那个究竟是什么呢？

其实

因为

所以

由于的特殊性，我们可以求出它。

解法

所以。

同余方程，如果，则方程只有唯一解。

在这种情况下，如果，同余方程就是。

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

对于同余方程的求解就是求解方程

。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的。

int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}