裴蜀定理 && 扩展欧几里得算法求逆元详解

62 阅读 0 评论 41 点赞

我是靠谱客的博主清脆导师，这篇文章主要介绍裴蜀定理 && 扩展欧几里得算法求逆元详解，现在分享给大家，希望可以做个参考。

裴蜀定理：

有一个线性不定方程 ax+by=c

若此方程有解，那么 c=k*gcd(a,b) ，k 为任意正整数

证明：

以下 gcd(a,b) 简称 gcd

$because$ (ax+by) mod gcd=0

又 c mod gcd=0

$therefore$ (ax+by-c) mod gcd=0

$therefore$ ax+by $equiv$ c (mod gcd)

证毕

$therefore$ 当 ax+by=c 成立时，c=k*gcd

特殊的：

当 a，b 互质时，方程满足 ax+by=1

扩展欧几里得算法：

利用扩展欧几里得原理不仅可以实现求逆元，而且还可以得到 gcd(a,b)

递归边界：

当 b=0 时，a=gcd(a,b),x=1,y 取任意数

代码实现：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int extend_gcd(int a,int b,int &x,int &y)
{
    int gcd=a;
    if(b!=0){
        gcd=extend_gcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else{
        x=1;
        y=0;
    }
    return gcd;
}

解决完扩展欧几里得算法之后，也就说我们可以解决逆元问题：当有一个一元线性同余方程 ax $equiv$ 1(mod b) 时，也就是说我们可以将其看作方程 ax+by=1 的解，根据扩展欧几里得原理，很容易得出一组解（x0,y0）

当要求解 ans=（a*b*c）%p 时，我们想将 b 去掉，了解取模运算的都知道，ans/b = (a*c)%p 这是不成立的

所以乘法逆元解决了这个问题，即求解方程 bx $equiv$ 1(mod p) ,这样方程两边同时 *x 这样可以消去 b 的影响