乘法逆元

· · 个人记录

在实数范围内，当a≠0时，一定有a\times\frac{1}{a}=1

在mod P意义下，我们同样想要这么一个的东西使 “ax\equiv1(mod P) ” ，那么这个x就称作a在模P意义下的逆元。

为什么我们需要逆元呢？ 首先，在计算当中，我们可能需要计算形如“\frac {64}{17}\bmod16 ”这种算式。由于除法特殊的性质，“(a/b)\bmod M并不一定等于(a\bmod M/b\bmod M) \bmod M”。这个时候我们就需要用逆元把除法转换成乘法。

或者，当我们计算模意义下的除法的时候，我们通常需要边做边模，这样比较省空间，可以有效防止爆范围，这个时候我们也需要使用逆元来把除法转换成乘法。

总之逆元非常的好用，但是怎么去求呢？

首先我们要知道一个定理：裴蜀定理：

对于整数a,b，设他们的最大公约数gcd(a,b)=d，则一定存在一组整数解使得

那么我们从这个定理又能推出一个定理：对于整数$a,b,c, ax+by=c$有整数解当且仅当 $gcd(a,b)|c$ 。 > 充分性：如果c是$gcd(a,b)$的倍数，那么可以先通过裴蜀定理$ax+by=gcd(a,b)$的一组解$x,y$。然后将$x,y$同乘以$\frac{c}{gcd(a,b)}$，就得到了不定方程$ax+by=c$的一组解。 > > 必要性：如果不定方程有解，因为$a$是$gcd(a,b)$的倍数，$b$同样也是，并且$x,y$都是整数，所以$ax+by$，也就是c，也一定是$gcd(a,b)$的倍数。 > > ——《深进》 > 通过这个定理我们就只需要求出 $ax+by=gcd(a,b)=d$的一组解就好了。怎么求呢？这个时候我们就要使用伟大的扩欧了。 回忆一下求最大公约数用的欧几里得算法（辗转相除法），然后用它的经验求解这个不定方程： 1.当$b=0$时，$ax+by=d$的解就是$x=\frac{d}{a}，y$任意。 2.求出$bx+(a \bmod b)y=d$的一组解，记作$(x_0,y_0)$。 现在我们有了方程的一组解，接下来的问题就是怎么从这组解生成一组新的$(x,y)$。 已知$bx_0+(a \bmod b)y_0=d$，那么可以把$a \bmod b$用$ a-\lfloor \frac{a}{b} \rfloor \times b$来表示，得到 $$bx_0+(a-\lfloor \frac{a}{b}\rfloor \times b)y_0=d$$ 提公因式，得 $$ay_0+b(x_0-\lfloor \frac{a}{b} \rfloor y_0)=d$$ 又因为$ax+by=d

所以有

ay_0+b(x_0-\lfloor \frac{a}{b} \rfloor y_0)=ax+by

这个时候可以发现，只要令(x,y)=(y_0,x_0-\lfloor \frac{a}{b} \rfloor y_0)，这个问题就可以解决了，这样裴蜀定理也就得到了证明。

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
ll a,p;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>a>>p;
        ll x,y;
        exgcd(a,p,x,y); 
        x=(x%p+p)%p;
        cout<<x<<endl;
    return 0;
}

这样我们得出的x就是a在模P意义上的逆元。

或者，如果我们不想用扩欧，也有另一种方法来做。

费马小定理，指的是如果p是一个质数而整数a不是p的倍数，则有

a^{p-1}\equiv 1(modp)

那通过这个定理我们就能知道,

a\times a^{p-2}=a^{p-1}(modp)\equiv1(modp)

所以a^{p-2}(modp)就是a在模P意义下的逆元，那么我们就只需要求a^{p-2}(modp)就好了

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int mod=19260817;
string s,t;
ll a,b;
ll fpow(ll x,ll y){
    ll t=1;
    while(y){
        if(y&1) t=t*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return t;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s>>t;
    for(int i=0;i<s.size();i++) a=(a*10+s[i]-'0')%mod;
    for(int i=0;i<t.size();i++) b=(b*10+t[i]-'0')%mod;
    if(a%mod&&!(b%mod)) cout<<"Angry!";
    cout<<a*fpow(b,mod-2)%mod;
    return 0;
}

这样我们就算出了a在模P意义上的逆元。但是现在问题又来了：怎么证明在0到p的范围内模P的逆元是唯一的？

我们假设

那么就有$a(x_2-x_1)\equiv 0(\bmod p)$。 也就是说$a(x_2-x_1)$是$p$的倍数，但是可以发现$0<x_2-x_1<p，$所以 $x_2-x_1$不是$p$的倍数，于是这个东西就矛盾了。 那么我们就可以证明：在0到$p$的范围内模P的逆元确实是唯一的。