【x义x讲坛】浅谈模质数意义下的乘法逆元

\color{green}\Large\texttt{『菜鸡的blog』}

我们直接切入正题吧。

问题一：什么是乘法逆元呢？

简单来说就是这样：在\pmod p意义下，如果a*a' \equiv 1，那么我们就说a'是a的逆元。当然啦，反过来，a也是a'的逆元。

（如果a,p不互质的话a是没有逆元的）

（在p不是素数的时候情况比较复杂，所以这一篇先介绍p为素数时的情况）

问题二：逆元有什么性质？

逆元的性质可真是多了去了，比较重要的有一下几个：

（在这些性质中，一般都有一个特例：0，所以我们就不谈a=0的情况了）

1.存在唯一性

对于a来说，它只会有一个，且一定有一个逆元。

这是为什么呢？

我们先假设a有两个不相等逆元：a'和a''，那么一定有：

a*a'\equiv a*a''\equiv1\pmod p

不妨设a'<a''且a''-a'=k，那么

a*(a''-k)\equiv a*a'' \pmod p a*a''-a*k\equiv a*a''\pmod p a*k\equiv0\pmod p

由于a\neq 0，所以k\equiv 0\pmod p，即a'\equiv a''，与假设矛盾，所以a只能有一个逆元。

至于逆元的存在性，读者自己思考一下吧。（就是你懒！）

2.完全积性函数

为了接下来方便，我们把a的逆元表示为inv[a]吧。

这个性质是说：

两个数的逆元的积等于这两个数积的逆元，inv[a]*inv[b]\equiv inv[a*b]。

这点也不难证：

显然

a*inv[a]\equiv b*inv[b]\equiv 1 \pmod p

那么

a*inv[a]*b*inv[b]\equiv1*1 \pmod p

所以

(a*b)*(inv[a]*inv[b])\equiv1 \pmod p

这不就是(a*b)的逆元的定义吗！

3.a*inv[b]\equiv a/b \pmod p

显然

b*inv[b]\equiv 1 \pmod p

两边都乘以a得

a*b*inv[b]\equiv a \pmod p

也就是

a*inv[b]\equiv a/b \pmod p

这个结论非常重要！

有时候我们需要算出a/b mod p的值，用朴素的方法，我们只能在a上不断加p，直到它能被b整除为止。当a,b,p都很大的时候，这种方法就只能凉凉了，但如果有了逆元，我们就可以非常方便，快捷地求解。

4.卖个关子

不要打我

问题三：逆元怎么求呢？

嗯，逆元确实不错，但怎么求呢？

（单个）求法一：枚举法

枚举k，检查是否满足a*k\equiv1 \pmod p。

太蠢了……

（单个）求法二：费马小定理

费马小定理：当p为素数时，a^{p-1}\equiv1 \pmod p。

那么a*a^{p-2}\equiv1 \pmod p。

再看看，这是不是又是逆元的定义？快速幂求出a^{p-2}即可。

（单个）求法三：扩展欧几里得

寻找a*x\equiv1 （mod p）的解inv[a]其实就相当于寻找方程a*x+p*y=1的解。

再一看：a,p一定互质，这不就是扩展欧几里得算法的标准形式吗！

（批量）求法四：欧拉筛

刚才讲的都是求单个a的逆元，但如果我们要求出1~p-1所有数的逆元呢？

还记得逆元是完全积性函数吗？所以对于每个合数a，我们把所有它的因子的逆元筛出来再相乘即可。

所以我们可以直接把所有素数筛出来，对它们求逆元（二或三），再把它的逆元乘给它的倍数就可以了。

代码如下：（这里用的是快速幂，貌似扩欧比它更快）

#include <bits/stdc++.h>
using namespace std;
const int N=25000528;
int p,n;
int vis[N],pri[N];
int inv[N];
int mi(int i,int j)  //分治快速幂
{
    if (!j) return 1;
    long long now=mi(i,j>>1);
    now=now*now%p;
    if (j&1) now=now*i%p;
    return (int)now;
}
int main()
{
    cin>>n>>p;
    vis[1]=1,inv[1]=1;
    for (int i=2;i<=p-1;i++)
    {
        if (!vis[i]) pri[++pri[0]]=i,inv[i]=mi(i,p-2);
        for (int j=1;j<=pri[0];j++)
        {
            if (i*pri[j]>=p) break;
            inv[i*pri[j]]=inv[i]*inv[pri[j]];
            if (i%pri[j]==0) break;
        }
    }
    for (int i=1;i<=n;i++)
    printf("%d\n",inv[i]);
    return 0;
}

不能过P3811……换成扩欧可能有救。

求法五：线性递推

现在我们要求k的逆元。

令a*k+b=p。

b*inv[b]\equiv1 \pmod p

把b换种表达，p-a*k：

(p-ak)*inv[b]\equiv1 \pmod p

那么

p*inv[b]-a*k*inv[b]\equiv1 \pmod p

在\pmod p意义下p\equiv0，则

-a*k*inv[b]\equiv1 \pmod p

观察ak+b=p，我们发现：a=p/k,b=p\% k（除号指整除），则最终

-(p/k)*inv[p \% k]*k\equiv1 \pmod p

即

-(p/k)*inv[p\%k]\equiv inv[k] \pmod p

神奇吧~

这就得出了性质4，也是我们今天最后一个求法线性递推的原理了。

这个东西可以以线性递推的方式求1至n所有数的逆元，也可以以递归的方式求单个数的逆元。（不过似乎和exgcd一样也是辗转相除？）

实际使用的时候记得加上p来去掉负号。代码如下：（可过P3811）

#include<bits/stdc++.h>
using namespace std;

int N,p;
int inv[25000528];

int main()
{
    cin>>N>>p;
    inv[1]=1;
    for (int i=2;i<=N;i++)
    inv[i]=(long long)(p-p/i)*inv[p%i]%p;
    for (int i=1;i<=N;i++) printf("%d\n",inv[i]);
    return 0;
}

【谢谢观看】

后记

感觉好多东西都没写到啊……

还有，建议这一篇的各个式子再消化一下。毕竟，一下子来这么多数学公式确实很难接受。

后记的后记（2019/8/6）

本次博客第一次大改。主要是标题字体字号修得更适合阅读，以及\LaTeX的问题，然后在开头放了一个本人博客的链接。

不知道你们有没有发现之前本博客的居中是拿\quad拼出来的……然后看看大概是中间位置就算居中了……

怎么莫名感觉之前的自己比现在强呢