欧拉定理

作者: 雨落八千里 | 来源:发表于2019-09-26 23:23 被阅读0次

数论四大定理
欧拉定理
补充：复数、欧拉公式、棣美弗定理
同余方程(组)
关于RSA的学习整理
数论四大定理之欧拉定理
rsa与欧拉定理
super_log(欧拉降幂)
费马小定理与欧拉定理
RSA的数学基础

欧拉函数

欧拉函数 $φ(n)(n∈N ^∗)$ 是小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。

欧拉定理

对于任意互素的 $a$ 和 $n$ ，有 $a^{φ(n)}≡1\ (mod\ \ n)$

参考链接
费马小定理

当 $p$ 为质数，则
$a^{p-1}≡1\ (mod \ \ \ p)$

因为 $φ(p)=p-1$

欧拉函数性质

$φ(1)=1$

对于任何质数 $p$ 都有 $φ(p)=p-1$

如果数 $n=p^x$ ( $p$ 为质数),那么 $φ(n)=p^x-p^{x-1}=p^x*(1-1/p)$
证明：
因为数n只有p这个质因子，所以在1~ $p^x$ 中只要找出没有p这个因子的数的个数就是 $φ(n)$
$φ(n)=p^x-count(p,2p,...xp...,p^{x-1}*p)=p^x-p^{x-1}$

如果数 $n=p*q,gcd(p,q)=1$ ,那么 $φ(n)=φ(p)*φ(q)$ (欧拉函数的积性函数)

任意一个大于 $1$ 的正整数 $n$ 都可以分解一系列质数的积的形式如：
$n=p_1^{k_1}*p_2^{k_2}*...*p_n^{k_n}$ (其中 $p_1,p_2...p_n$ 都是质数)
根据欧拉函数的积性函数
$φ(n)=φ(p_1^{k_1})*φ(p_2^{k_2})*...*φ(p_n^{k_n})$
根据性质3
$φ(p_1^{k_1})=p_1^{k_1}*(1-1/p_1)$
所以可得
$φ(n)=p_1^{k_1}*p_2^{k_2}*...*p_n^{k_n}*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_n)$
所以
$φ(n)=n*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_n)$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ol(int x)
{
    int res=x;
    ll ans=x;
    for(int i=2;i*i<=res;i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
        }
        while(x%i==0)
        {
            x/=i;
        }
    }
    if(x>1)
    {
        ans=ans*(x-1)/x;
    }
    return ans;
}
int main( )
{
    while(~scanf("%d",&n))
    {
        printf("%lld\n",ol(n));
    }
    return 0;
}

扩展欧拉定理(欧拉降幂)

$a^b≡\begin{cases} a^{b\%φ(p)}\ \ (mod \ \ p)\ \ \ \ \ \ \ gcd(a,p)=1\\ a^b\ \ \ \ \ \ (mod\ \ \ p) \ \ \ \ \ \ gcd(a,p)!=1&&b<φ(p)\\ a^{b\%φ(p)+φ(p)}\ \ \ \ (mod\ \ \ p)\ \ \ \ \ gcd(a,p)!=1&&b>=φ(p)\end{cases}$

等式中的 $gcd(a,p)!=1$ 表示 $a,p$ 可以不互质
证明链接

运用:

当 $A^B\%C$ 中的 $B$ d=的数特别大，就要使用欧拉降幂了

洛谷P5091

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a;
char b[20000010];
ll c;
ll ol(int x)
{
    int res=x;
    ll ans=x;
    for(int i=2; i*i<=res; i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
        }
        while(x%i==0)
        {
            x/=i;
        }
    }
    if(x>1)
    {
        ans=ans*(x-1)/x;
    }
    return ans;
}
ll pow(int a,ll n,int mod)
{
    ll ans=1;
    ll base=a;
    while(n)
    {
        if(n&1)
        {
            ans=ans*base%mod;
        }
        base=base*base%mod;
        n>>=1;
    }
    return ans%mod;
}
int main( )
{
    int flag=0;
    scanf("%d %d %s",&a,&c,&b);
    ll phi=ol(c);
    int len=strlen(b);
    ll cnt=0;
    for(int i=0; i<len; i++)
    {
        cnt=cnt*10+b[i]-'0';
        if(cnt>=phi)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
    {
        ll ans=0;
        for(int i=0; i<len; i++)
        {
            ans=(ans*10+b[i]-'0')%phi;
        }
        ans+=phi;
        printf("%lld\n",pow(a,ans,c));
    }
    else//b<φ(p)
    {
        printf("%lld\n",pow(a,cnt,c));   
    }
    return 0;
}