欧拉定理和费马小定理

欧拉定理: 设 m 是大于 1 的整数，如果  a  是满足 (a,m)== 1 的整数，则 a ^f(m)=1 ( mod m )

证明: 取 r₁, r₂, r₃, ... , r_f(m) 为比 m 小且与 m 互素的数， 有 ( r_i, m )== 1, 因为 (a,m)== 1, 故有 (a*r_i, m)= 1。

可以证明 a*r_i != a*r_j ( mod m ) (i!= j )，因为假设上式成立，则有 r_i== r_j ( mod m ) (i!= j )，而这个式子是不成立的。由此我们可以得出： (a* r₁)( a* r₂)...(a*r_f(m) )== r₁r₂...r_f(m)  (mod m )

故 r₁* r₂* ... * r_f(m)* (a^f(m)-1)== 0 ( mod m )

又  r₁* r₂* ... * r_f(m) == 1 (mod m)   所以 (a^f(m)-1)== 0 ( mod m )。

 

费马小定理：设 p 是一个素数，则对任意整数 a, 我们有 a^p== a ( mod p )

证明: 我们分两种情况考虑

1) 若 p| a，则同时有 p| a^p，显然 a^p== a ( mod p )。

2) 若 (p, a)== 1，所以 (p, a^p-1)= 1，则由欧拉定理有 a^p-1== 1 ( mod p )，两端同乘 a，则得到:

     a^p== a ( mod p )。

 

推论: 设 a, p, n 为正整数，则有 a^p== a^{p % f(n)+ f(n)}  ( mod n )。

 

Hnu 11694 Fibnacci Numbers

代码：

#include <iostream>
using namespace std;
__int64 a,x,n;
__int64 mod;

int Eular(int n){
    int ret=1;
    for(int i=2;i*i<=n;++i)
    if(n%i==0){
        n/=i;ret*=i-1;
        while(n%i==0){
            n/=i;ret*=i;}
    }
    if(n>1)ret*=n-1;
    return ret;
}

void inline mult(__int64 x[4][4], __int64 y[4][4]){
    __int64 z[4][4];
    for(int i=0;i<4;++i)
    for(int j=0;j<4;++j){
        z[i][j]=0;
        for(int k=0;k<4;++k)
        z[i][j]=(z[i][j]+x[i][k]*y[k][j])%mod;
    }
    for(int i=0;i<4;++i)
    for(int j=0;j<4;++j)
    y[i][j]=z[i][j];
}

int main(){
    while(cin>>a>>x>>n){
        if(a==0&&x==0&&n==0)return 0;
        __int64 d[4][4], ans[4][4]={0};
        d[0][0]=1;d[0][1]=1;d[0][2]=1;d[0][3]=2;
        d[1][0]=0;d[1][1]=1;d[1][2]=1;d[1][3]=2;
        d[2][0]=0;d[2][1]=1;d[2][2]=0;d[2][3]=0;
        d[3][0]=0;d[3][1]=1;d[3][2]=0;d[3][3]=1;
        
        __int64 sn=0;
        mod=Eular(n);
        if(x==1)sn=1;
        else if( x==2)sn=5;
        else{
            for(int i=0;i<4;++i) ans[i][i]=1;x-=2;
            while(x>0){
                if(x&1)mult(d,ans);
                mult(d,d);x/=2;
            }
            sn= (ans[0][0]*5%mod+ans[0][1]*4%mod+ans[0][2]+ans[0][3]*2)%mod;
        }
        sn+=mod;
        __int64 as=1,t=a;
        while(sn){
            if(sn&1)as=as*t%n;
            t=t*t%n;sn>>=1;}
        cout<<as<<endl;
    }
    return 0;
}