Inverse-Element

逆元定义

$a=\frac{1}{b}\left(modp\right)$a=b1​(mod p)，也就是 $a\ast b=1\left(modp\right)$a∗b=1(mod p)。表示 $a$a为 $b$b在 $modp$mod p意义下的逆元

快速幂求逆元

$a^p=a\left(modp\right)$ap=a(mod p)

用二项式定理证明

$a^p=\left(\right(a-1)+1{)}^p=\sum _{i=0}^p{C}_p^i\ast (a-1{)}^i$ap=((a−1)+1)p=i=0∑p​Cpi​∗(a−1)i

来康康这里面的组合数鸭

$C_n^m=\frac{n!}{m!\ast (n-m)!}$Cnm​=m!∗(n−m)!n!​

可以发现当n是素数的时候，在 $1\le m\le n-1$1≤m≤n−1的项里面都有 $n$n这个因子，所以所以模运算剩下的只有

$C_p^0\ast (a-1{)}^0$Cp0​∗(a−1)0

$C_p^p\ast (a-1{)}^p$Cpp​∗(a−1)p

也就是

$a^p=(a-1{)}^p+1(modp)$ap=(a−1)p+1(mod p)

用数学归纳法就可得

$a^p=a\left(modp\right)$ap=a(mod p)

$a^{p-1}=1\left(modp\right)$ap−1=1(mod p)

$a^{p-2}=\frac{1}{a}\left(modp\right)$ap−2=a1​(mod p)

这样就得到 $a$a在 $modp$mod p意义下的逆元了。