乘法逆元入门略解
Hexarhy
·
·
个人记录
乘法逆元入门略解
1. 定义
对于正整数 a，如果存在 a\times a'\equiv 1(\bmod\ p)，那么 a' 就是 a 在模 p 意义下的逆元。这里只考虑 p 为质数，情况简单。
推广一下，逆元就是**取消另一给定元素运算的元素**。例如加法逆元是这个数的相反数。
### 2. 性质
#### 2.1 存在唯一性
对于正整数 $a$，模 $p$ 之后有且仅有一个逆元。
证明唯一性：
假设 $a$ 有两个不相等的逆元 $a',a''(a'<a'')$，那么：
$$
a\times a'\equiv a\times a''\equiv1(\bmod\ p)
$$
设 $k=a''-a'$，那么：
$$
a\times(a''-k)\equiv a\times a''(\bmod\ p)$$
$$a\times a''-a\times k\equiv a\times a''(\bmod\ p)$$
$$
a\times k\equiv0(\bmod\ p)
$$
$\because a\not=0\therefore k\equiv 0(\bmod\ p)$，即 $a'\equiv a''(\bmod\ p)$，与假设矛盾，原命题成立。
#### 2.2 完全积性函数
对于正整数 $a,b$，$inv(a)\times inv(b)\equiv inv(ab)$。
证明：
$$
\because a\times inv(a)\equiv b\times inv(b)\equiv 1(\bmod\ p)$$
$$\therefore a\times inv(a)\times b\times inv(b)\equiv 1\times 1(\bmod\ p)$$
$$\therefore ab\times inv(a)\times inv(b)\equiv1(\bmod\ p)$$
$$\because ab\times inv(ab)\equiv 1(\bmod\ p)\small\text{，且根据逆元的存在唯一性}$$
$$\therefore inv(a)\times inv(b)\equiv inv(ab)
$$
#### 2.3 分数取模
对于正整数 $a,b$，$a\times inv(b)\equiv \dfrac{a}{b}(\bmod\ p)$。
证明：
$$
\because b\times inv(b)\equiv1(\bmod\ p)$$
$$\therefore b\times inv(b)\times a\equiv a(\bmod\ p)$$
$$\therefore a\times inv(b)\equiv \dfrac{a}{b}(\bmod\ p)
$$
也就是说，$\dfrac{a}{b} \bmod p$ 的值，可以用逆元求出。
$$
\dfrac{a}{b}\equiv a\times inv(b)(\bmod\ p)
$$
### 3. 解法
#### 3.1 费马小定理
前置知识：**费马小定理**
> 若 $a$ 为正整数，$p$ 为质数，且 $a\perp p$，那么 $a^{p-1}\equiv 1(\bmod\ p)$。
那么 $a\times a^{p-2}\equiv 1(\bmod\ p)$。
根据乘法逆元的唯一存在性，$inv(a)=a^{p-2}$。快速幂求出即可。
时间复杂度 $O(\log p)$。参考代码为分数取模。
```cpp
int qpow(int base,int k)
{
int res=1;
while(k)
{
if(k&1)
res=1ll*res*base%MOD;
k>>=1;
base=1ll*base*base%MOD;
}
return res;
}
int main()
{
a=read();b=read();
cout<<1ll*a*qpow(b,MOD-2)%MOD<<endl;
return 0;
}
```
#### 3.2 扩展欧几里得
找 $a\times inv(a) \equiv 1(\bmod p)$ 的 $inv(a)$，写成方程的形式来看看。
设 $x=inv(a)$。
$$
a\times x\bmod p=1\bmod p$$
$$(a\times x-1) \bmod p=0
$$
即，$p|(ax-1)$，设 $(ax-1)=-py$。
$$
ax-1=-py$$
$$ax+py=1
$$
$a\perp p,\gcd(a,p)=1$，这个方程恰好就是扩展欧几里得的标准形式。
时间复杂度近似于 $O(\log p)$。参考代码为分数取模。
```cpp
ll exgcd(ll a,ll b,ll& x,ll& y)
{
if(!b)
{
x=1;y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
a=read();b=read();
ll x=0,y=0;
exgcd(b,MOD,x,y);
cout<<(1ll*(x%MOD+MOD)%MOD*a%MOD)<<endl;
return 0;
}
```
#### 3.3 欧拉定理
前置知识：**唯一质数分解定理**。
任何一个整数 $n>1$ 都可以唯一地分解为一组质数的乘积。
$$
n=2^{k_1}\times 3^{k_2}\times 5^{k_5}\times \cdots=\prod ^{\infty}_{i=1}p_i^{k_i}
$$
**欧拉函数** $\varphi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数个数。
**性质：** 当 $a\perp b$，$\varphi(a)\varphi(b)=\varphi(ab)$。
**欧拉定理**：如果正整数 $n\perp a$，那么，
$$
a^{\varphi(n)}\equiv 1(\bmod\ n)
$$
运用到这里，就有：
$$
a\times inv(a)\equiv a^{\varphi(p)}(\bmod\ p)$$
$$\therefore inv(a)=a^{\varphi(p)-1}(\bmod\ p)
$$
我们可以在 $O(\sqrt n)$ 的时间内求出 $\varphi(p)$。
根据唯一分解定理，设 $n=\prod^m_{i=1} p_i^{k_i}$，则：
$$
\varphi(n)=n\times \prod^m_{i=1} (1-\dfrac{1}{p_i})
$$
证明：
首先考虑 $\varphi(p^k)$，其中 $p$ 是质数，$k$ 是非负整数。
如果要让 $\gcd(p^k,t)\not=1$，只能使 $t$ 为 $p$ 的倍数，即$t=p,2p,3p,\cdots,p^{k-1}\cdot p$，总共 $p^{k-1}$ 个。所以：
$$
\varphi(p^k)=p^k-p^{k-1}=p^k(1-\dfrac{1}{p})
$$
由于各质数幂之间互质，此时欧拉函数满足积性函数性质，得：
$$
\varphi(n)=\varphi(\prod p_i^{k_i})$$
$$\varphi(n)=\prod^m_{i=1}\varphi(p_i^{k_i})$$
$$\varphi(n)=\prod^m_{i=1}p_i^{k_i}\times \prod^m_{i=1}(1-\dfrac{1}{p_i})$$
$$\varphi(n)=n\times \prod^m_{i=1}(1-\dfrac{1}{p_i})
$$
接下来就可以根据这个等式求 $\varphi(p)$。我们可以在 $O(\sqrt n)$ 内枚举 $n$ 的质因数 $p_i$。令 $res=n$，枚举到每个 $p_i$， $res$ 就乘上 $(1-\dfrac{1}{p_i})$。当然也可以选择乘上 $\dfrac{p_i-1}{p_i}$。
为了方便判断是否全部 $p_i$ 都枚举到，我们可以不断除以 $p_i$，防止重复计算并除掉合数，并在最后特判一下。
最后再用快速幂即可。
时间复杂度 $O(\log\varphi(p)+\sqrt n)$。参考代码为分数取模。
```cpp
ll phi(ll x)
{
ll res=x,t=x;
for(ll i=2;i*i<=t;i++)
{
if(x%i==0)
{
res=res/i*(i-1)%MOD;
while(x%i==0)
x/=i;
}
}
if(x>1)
res=res/x*(x-1)%MOD;
return res;
}
ll qpow(ll base,ll k)
{
int res=1;
while(k)
{
if(k&1)
res=1ll*res*base%MOD;
base=1ll*base*base%MOD;
k>>=1;
}
return res;
}
int main()
{
a=read();b=read();
cout<<1ll*a*qpow(b,phi(MOD)-1)%MOD<<endl;
return 0;
}
```
#### 3.4 线性递推
一波奇妙的推式子。
现在求 $k$ 的逆元。
令 $a\times k+b=p$。
$$
\because b\times inv(b)\equiv 1(\bmod\ p)$$
$$\therefore (p-a\times k)\times inv(b)\equiv 1(\bmod\ p)$$
$$\therefore p\times inv(b)-a\times k\times inv(b)\equiv 1(\bmod\ p)$$
$$\therefore -a\times k\times inv(b)\equiv 1(\bmod\ p)$$
$$\because a\times k+b=p$$
$$\therefore a=p\ \mathrm{div}\ k,b=p\bmod k$$
$$\therefore -(p\ \mathrm{div}\ k)\times inv(p\bmod k)\equiv \dfrac{1}{k}(\bmod\ p)$$
$$\therefore -(p\ \mathrm{div}\ k)\times inv(p\bmod k)\equiv inv(k) (\bmod\ p)
$$
$\mathrm{div}$ 是整除。
$p\bmod k<k$，所以我们可以递推。显然边界就是 $inv(1)=1$。$1$ 在模任意正整数下逆元都是 $1$。
但是 $ -(p\ \mathrm{div}\ k)$ 是负数，在模 $p$ 意义下，我们会加上 $p$ 。也就是说：
$$
inv(k)\equiv(p-p\operatorname{div}k)\times inv(p\bmod k)(\bmod\ p)
$$
时间复杂度 $O(p)$。参考代码为求出 $[1,p-1]$ 范围内所有整数的逆元。
```cpp
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN=3e6+5;
ll n,p;
ll inv[MAXN];
int main()
{
scanf("%lld%lld",&n,&p);
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
for(int i=1;i<=n;i++)
printf("%lld\n",inv[i]);
return 0;
}
```
### 4. 参考资料
1. [知乎-初等数论笔记 Part 1： 欧拉定理](https://zhuanlan.zhihu.com/p/35060143)。
2. [洛谷日报第 #30 期](https://www.luogu.com.cn/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan#)。
3. [洛谷日报第 #205 期](https://www.luogu.com.cn/blog/1239004072Angel/post-shuo-xue-sheng-fa-ni-yuan)。