乘法逆元

定义

若$ax \equiv 1\pmod b$,则称x是$a$是关于模$b$的逆元，常记作$a^{-1}$.

性质

上式等价于$ax+by=1$,求解逆元即为解方程$ax+by=1$。

$\Longrightarrow$逆元不一定存在：充要条件为$(a,b)=1$
$\Longrightarrow p$是质数，$p$不整除$a$,则$a$模$p$的逆元存在。

$\Longrightarrow$在$[0,b)$范围内，$a$关于模$b$的逆元(若存在)是唯一的。

证明：
反证法
若a有两个逆元$0<x_1<x_2<b$
,
即$ax_1 = ax_2 = 1 \pmod b$.
那么有$b|a(x_2-x_1)$成立
又由于$(a, b) =1$,
因此$b|(x_2-x_1)$
其中$0<x_2-x_1<b$,产生了矛盾。

求解

1. 利用$\operatorname{exgcd}$求逆元

   int inv(int a,int b){ //表示求a在模b意义下的逆元
       int x,y;
       exgcd(a,b,x,y);
       return x;
   }

   为取正数

   int inv(int a,int b){
       int x,y;
       exgcd(a,b,x,y);
       return (x%b+b)%b;
   }

2. 在1的基础上进行倒推
   先求$n!$的逆元，
   然后利用$((n-1)!)^{-1} \equiv n \times (n!)^{-1} \pmod p$,
   即除以$n$,
   就可以求$1 \ldots n$的逆元了
3. 顺推求解
   假设求$i$的逆元
   考虑带余除法$p=iq+r$
   $iq+r \equiv 0 \pmod p$
   两边同乘上$i^{-1}r^{-1}$
   得到$qr^{-1}+i^{-1} \equiv 0 \pmod p$
   $\Longrightarrow i^{-1} \equiv (p-(p/i))(p \bmod i)^{-1} \pmod p i^{-1} \equiv -qr^{-1} \pmod p$
   $\Longrightarrow i^{-1} \equiv -(p/i)(p \bmod i)^{-1} \pmod p$
   $\Longrightarrow inv[i]=-(p-p/i)inv[p \bmod i] \pmod p$