求逆元

参考的博客：http://blog.csdn.net/guhaiteng/article/details/52123385

1欧几里得扩展求逆元

乘法逆元

对于缩系中的元素，每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n) 一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

给定模数m，求a的逆相当于求解ax=1(mod m)
这个方程可以转化为ax-my=1

我们要求的是x，那么根据欧几里得扩展化为ax-my=gcd(a,m)的方程求一组解（x,y）

而如果gcd(a,m)==1才有逆元，否则没有

下面我们来证明一个结论：gcd(a,b)==gcd(b,a%b);//这也是辗转相除法求最大公约数的根本

设两数为a、b(a>b)，用gcd(a,b)表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=k^.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。

第一步：令c=gcd(a,b)，则设a=mc，b=nc

第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。

证毕。

以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。

我们再引入扩展欧几里得定理：

定理：对于不完全为 0 的非负整数 a，b，
gcd（a，b）表示 a，b 的最大公约数，必然存在无数组整
数对 x，y ，使得 gcd（a，b）=ax+by。

所以我们可以得出：

a*x1+b*y1==gcd(a,b); b*x2+(a%b)*y2==gcd(a,b); ==> a*x1+b*y1==b*x2+(a%b)*y2;

a*x1+b*y1==b*x2+a*y2-k*b*y2; ==> a*x1+b*y1==a*y2+b*(x2-k*y2);

x1=y2;

y1=x2-k*y2;

我们要求的逆元是x1，怎么求？

我们很容易知道

an*xn+0*yn=gcd(an,0)==an; xn=1; yn=0;

所以用xn,yn倒推出x1,y1;

公式为：

x(n-1)=yn;

y(n-1)=xn-k*yn;

下面是代码实现：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int exGcd(int a,int b,int &x,int &y)
 5 {
 6     if(b==0)
 7     {
 8         x=1;y=0;
 9         return a;
10     }
11     int r=exGcd(b,a%b,x,y);
12     int t=x;
13     x=y;
14     y=t-a/b*y;
15     //printf("%d
",x);
16     return r;
17 }
18 int main()
19 {
20     int x,y;int mod=15,a=14;
21     if(exGcd(a,mod,x,y)==1)
22     {
23         while(x<0)x+=mod;
24         printf("%d
",x);
25     }
26     else
27     printf("xx
");
28     return 0;
29 }

x+=mod是因为求出的x可能小于0

2.费马小定理：

在模为素数p的情况下，有费马小定理 a^(p-1)=1（mod p）那么a^(p-2)=a^-1(mod p) 也就是说a的逆元为a^(p-2)

而在模不为素数p的情况下，有欧拉定理 a^phi(m)=1（mod m） (a⊥m，a和m互质) 同理a^-1=a^(phi(m)-1)

因此逆元x便可以套用快速幂求得了x=a^(phi(m)-1)

但是似乎还有个问题？如何判断a是否有逆元呢?

检验逆元的性质，看求出的幂值x与a相乘是否为1即可

PS:这种算法复杂度为O（log2N）在几次测试中，常数似乎较上种方法大

当p比较大的时候需要用快速幂求解

代码实现：

 1 typedef  long long ll;  
 2 ll pow_mod(ll x, ll n, ll mod){  
 3     ll res=1;  
 4     while(n>0){  
 5         if(n&1)res=res*x%mod;  
 6         x=x*x%mod;  
 7         n>>=1;  
 8     }  
 9     return res;  
10 }

当模p不是素数的时候需要用到欧拉定理

a^phi(p)≡1 (mod p)

a*a^(phi(p)-1)≡1 (mod p)

a^(-1)≡a^(phi(p)-1) (mod p)

所以

(当p为素数的时候phi(p)=p-1,则phi(p)-1=p-2可以看出欧拉定理是费马小定理的推广)

PS：这里就贴出欧拉定理的板子，很少会用欧拉定理求逆元