乘法逆元

定义#

若,则称x是是关于模的逆元，常记作.

性质#

上式等价于,求解逆元即为解方程。

逆元不一定存在：充要条件为
是质数，不整除,则模的逆元存在。

在范围内，关于模的逆元(若存在)是唯一的。

证明： 反证法
若a有两个逆元 ,
即.
那么有成立
又由于,
因此 其中,产生了矛盾。

求解#

1. 利用求逆元

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

   cpp
   为取正数

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

   cpp
2. 在1的基础上进行倒推
   先求的逆元，
   然后利用, 即除以,
   就可以求的逆元了
3. 顺推求解 假设求的逆元
   考虑带余除法
   
   两边同乘上
   得到