基础数论--欧拉定理，逆元

1、欧拉定理

欧拉定理，若a与p互质，那么a ^ (phi[n]) ≡ 1 (mod n)

证明：假设x1,x2....x(phi[n])是1~n中与n互质的数

　　　　可以发现，他们是两两不同的。

　　　　将每个数都乘以a，得ax1,ax2....ax(phi[n])

　　　　假设我们已经证明在mod n的情况下，x1*x2*...*x(phi[n])=ax1*ax2*....ax(phi[n])

　　　　又因为x1,x2...x(phi[n])两两互质，所以x1*x2*...*x(phi[n]) ! = 0，所以 a ^ (phi[n]) ≡ 1 (mod n)

　　　　那么我们就只需要证明在mod n的情况下，x1*x2*...*x(phi[n])=ax1*ax2*....ax(phi[n])

　　　　证：ax1,ax2...两两不同

　　　　　　反证，假设axi = axj (mod n)，则a(xi - xj ) = 0，由于

$费马小定理只是欧拉定理的一个特殊情况，当n是质数时，phi[n]=n-1，此时a^(n-1)=1 (mod n)$

$若n是质数且b不能被n整除，那么根据费马小定理，b^(n-1)=1(mod n)，所以b的逆元为b^(n-2)$

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 int qmi(LL a,LL b,LL p){
 5     LL res=1;
 6     while(b){
 7         if(b&1){
 8             res=res*a%p;
 9         }
10         b>>=1;
11         a=a*a%p;
12     }
13     return res;
14 }
15 int main(void){
16     int n;
17     cin>>n;
18     for(int i=0;i<n;i++){
19         int a,p;
20         cin>>a>>p;
21         if(a%p!=0)
22             cout<<qmi(a,p-2,p)<<endl;
23         else
24             cout<<"impossible"<<endl;
25     }
26     return 0;
27 }

　　　　求逆元之二

　　　　若n不为质数的话，b关于n的逆元就不能用费马定理来求了，因为此时不成立

　　　　就只能用费马小定理更加通用的格式欧拉定理来求了

　　　　　　b^(phi[n])=1 (mod n)

　　　　所以我们得先求出phi[n]，再求b的逆元

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 int qmi(LL a,LL b,LL p){
 5     LL res=1;
 6     while(b){
 7         if(b&1){
 8             res=res*a%p;
 9         }
10         b>>=1;
11         a=a*a%p;
12     }
13     return res;
14 }
15 int get_phi(int n){
16     int res=n;
17     for(int i=2;i<=n/i;i++){
18         if(n%i==0){
19             res=res/i*(i-1);
20             while(n%i==0){
21                 n/=i;
22             }
23         }
24     }
25     if(n>1){
26         res=res/n*(n-1);
27     }
28     return res;
29 }
30 int main(void){
31     int n;
32     cin>>n;
33     for(int i=0;i<n;i++){
34         int a,p;
35         cin>>a>>p;
36         int t=get_phi(p);
37         if(a%p!=0)
38             cout<<qmi(a,t-1,p)<<endl;
39         else
40             cout<<"impossible"<<endl;
41     }
42     return 0;
43 }

但是这种方法的时间复杂度是有点难以接受的，达到了O(sqrt(n))，瓶颈是求phi[n]

　　　　求逆元之三

　　　　扩展欧几里得算法可以求出xa+yb=gcd(a,b)

　　　　所以他可以求同余方程 xa=b (mod m) => xa=b+ym => xa+y′ m=b(y′ =-y)

　　　　那么他也可以求逆元a mod n的逆元是a*x=1 (mod n) ，x就称为a的逆元

　　　　　　=> 　x*a + y*n = 1

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 int exgcd(int a,int b,LL& x,LL& y){//尽量写LL，因为怕超int
 5     if(b==0){
 6         x=1,y=0;
 7         return a;
 8     }else{
 9         int d=exgcd(b,a%b,y,x);
10         y=y-(a/b)*x;
11         return d;
12     }
13 }
14 int main(void){
15     int n;
16     cin>>n;
17     for(int i=0;i<n;i++){
18         int a,p;
19         LL x,y;
20         cin>>a>>p;
21         int d=exgcd(a,p,x,y);
22         if(a%p==0){
23             cout<<"impossible"<<endl;
24         }else{
25             cout<<(x/d+p)%p<<endl;//因为x*a + y*n = gcd(a,p) ,所以左右除以一个gcd(a,p)
26         }
27     }
28     return 0;
29 }