欧拉定理
Zvelig1205
2021-09-19 17:20:09
## 欧拉定理
### 前置知识
[欧拉函数](https://413020.blog.luogu.org/ou-la-han-shuo-mo-bi-wu-si-han-shu)
[同余系](https://413020.blog.luogu.org/tong-yu)
### 定理内容
若正整数 n 与 整数 a 互质，有：
$$a^{\varphi(n)}\equiv1\pmod n$$
在 $n$ 为素数时， $\varphi(n)=n-1$ ，则有 $a^{n-1}\equiv1\pmod n$ 。这就是 [费马小定理](https://413020.blog.luogu.org/fei-ma-xiao-ding-li) 。
### 引例
求 $3^{83}$ 的最后两位数。
第一眼：找规律
只找最后两位，我们就来枚一下 $3^n$ ：
$$\begin{aligned}
3^{0}&=&1\\
3^{1}&=&3\\
3^{2}&=&9\\
3^{3}&=&27\\
3^{4}&=&81\\
3^{5}&=&243\\
3^{6}&=&729\\
3^{7}&=&2187\\
3^{8}&=&6561\\
3^{9}&=&19683\\
3^{10}&=&59049\\
\end{aligned}$$
不难发现，个位循环 `[1,4,9,7]` ，周期为 4 。
十位循环周期为 20 ，循环体为 `[0,0,0,2,8,4,2,8,6,8,4,4,4,2,6,0,2,6,8,6]` （有兴趣的可以自己算一下）。
那么， $3^{83}$ 的最后两位数就是 27 了。
是不是很麻烦。
~~我觉得是。~~
所以我们要找一个简单的方法。
~~比如欧拉定理。~~
通过对欧拉函数的了解，我们可以很快的求出 $\varphi(100)=100\times(1-\dfrac{1}{2})\times(1-\dfrac{1}{5})=40$
又有 $\gcd(3,100)=1$ ，
所以
$$3^{83}=3^{3}\times3^{80}=3^{3}\times(3^{\varphi(100)})^2\equiv3^3\times1=27\pmod {100}$$
最后两位就是 27 。
是不是很简单？
~~我觉得也不怎么简单~~
关于欧拉定理，还有很多相关题目，比如：
1.求 $2014^{2014^{2014}}$ 的最后两位数。
`Answer=36`
2.求 $1^{2016}+2^{2016}+\cdots+2016^{2016}$ 模 $2016$ 的值。
`Answer=48`
3.求 $8^{7^{6^{5^{4^{3^{2^{1}}}}}}}$ 的最后三位数。
`Answer=008`
有兴趣的可以自己求一下。
### 证明
关于欧拉定理为什么是对的
我们考虑模 n 的最小正缩系：
$\Phi_n=\{c_1,c_2,\cdots,c_{\varphi(n)}\}$
取 $a$ 使得 $\gcd(a,n)=1$ 。
那么 $a\cdot\Phi_n=\{a\cdot c_1,a\cdot c_2,\cdots,a\cdot c_{\varphi(n)}\}$
显然 $a\cdot\Phi_n$ 也是 n 的一个缩系。
显然有：
$$\displaystyle\prod_{i=1}^{\varphi(n)}(a\cdot c_i)\equiv\displaystyle\prod_{i=1}^{\varphi(n)}c_i\pmod n$$
又有：
$$\displaystyle\prod_{i=1}^{\varphi(n)}(a\cdot c_i)=a^{\varphi(n)}\cdot\displaystyle\prod_{i=1}^{\varphi(n)}c_i$$
则：
$$a^{\varphi(n)}\cdot\displaystyle\prod_{i=1}^{\varphi(n)}c_i\equiv\displaystyle\prod_{i=1}^{\varphi(n)}c_i\pmod n$$
又：
$$\gcd(a^{\varphi(n)},\displaystyle\prod_{i=1}^{\varphi(n)}c_i)=1$$
则同余式两边同时除以 $\displaystyle\prod_{i=1}^{\varphi(n)}c_i$ 得：
$$a^{\varphi(n)}\equiv1\pmod n$$
证毕。
### 推论
$$a^{b}\equiv a^{b\bmod \varphi(n)}\pmod n$$
证一下：
由取余的定义
$$x\bmod y=x-\lfloor\dfrac{x}{y}\rfloor\cdot y$$
则：
$$b=\varphi(n)\cdot\lfloor\dfrac{b}{\varphi(n)}\rfloor+b\bmod \varphi(n)$$
即：
$$\begin{aligned}
a^{b}\bmod n&=(a^{\varphi(n)\cdot\lfloor\frac{b}{\varphi(n)}\rfloor}\bmod n)\times(a^{b\bmod \varphi(n)}\bmod n)\\
&=1\times a^{b\bmod \varphi(n)}\bmod n\\
&=a^{b\bmod \varphi(n)}\bmod n
\end{aligned}$$
那么在 $\gcd(a,n)=1$ 时，就算 b 很大，也能求出 $a^b\bmod n$ 的值。
代码如下：
```cpp
#include<cstdio>
#define int long long
using namespace std;
const int inf=1e5+7;
int a,b,n,p,phi,ans;
int _phi(int n)
{
int ans=n;
for(int i=2;i<=n;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
}
if(n>1)ans=ans/n*(n-1);
return ans;
}
int re()
{
int s=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-48;s%=phi;
ch=getchar();
}
return s*f;
}
int ksm(int a,int b,int p)
{
int ans=1;
while(b)
{
if(b&1)ans=(ans*a)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
signed main()
{
scanf("%lld%lld",&a,&n);
phi=_phi(n);
b=re();
ans=ksm(a,b,n);
printf("%lld\n",ans);
return 0;
}
```
限制比较大，只有当 a 和 n 互质时才能用。
### 扩展
[模板](https://www.luogu.com.cn/problem/P5091)
题目没有保证 a 和 n 互质，如果直接交上边的代码会 WA 两个点。
当 a 和 n 不保证互质时，可以用扩展欧拉定理。
即：
$$a^b\equiv
\begin{cases}
a^{b\bmod \varphi(n)}&\pmod n,\gcd(a,n)=1\\
a^b&\pmod n,\gcd(a,n)\ne1,b<\varphi(n)\\
a^{(b\bmod\varphi(n))+\varphi(n)}&\pmod n,\gcd(a,n)\ne1,b\ge\varphi(n)\\
\end{cases}$$
证明（第三条）：
取 $n$ 的一个质因数 $p$ ，使得 $n=p^r\times s$ ，且 $\gcd(p,s)=1$ 。
由欧拉定理，显然 $p^{\varphi(s)}\equiv1\pmod s$ ，显然 $\varphi(n)=\varphi(p^r)\cdot\varphi(s)$ ，那么 $\varphi(n)\equiv1\pmod n$ 。
此时由 $p^{\varphi(n)+r}=p^{\varphi(n)}\cdot p^{r}$ ，得到 $p^{\varphi(n)+r}\equiv p^r\pmod n$ 。
在 $b\ge r$ 时， $p^b\equiv p^{b-r}\cdot p^r\equiv p^{b-r}\cdot p^{\varphi(n)+r}\equiv p^{b+\varphi(n)}\pmod n$ 。
因为 $r\le\varphi(p^r)\le\varphi(n)$ ，所以当 $b\ge2\cdot\varphi(n)$ 时 $b-\varphi(n)\ge r$ ，所以 $p^{b-\varphi(n)}\equiv p^b\pmod n$ ， $p^b\equiv p^{b-\varphi(n)}\pmod n$ 。
即 $p^b\equiv p^{(b\bmod\varphi(n))+\varphi(n)}\pmod n$ 。
最后，将 $a$ 质因数分解后再相乘，得到 $a^b\equiv a^{(b\bmod\varphi(n))+\varphi(n)}\pmod n$ 。
前后的代码极其相似，只不过在快读中加了个 `pd` 。
Code:
```cpp
#include<cstdio>
#define int long long
using namespace std;
const int inf=1e5+7;
int a,b,n,p,phi,ans;
int _phi(int n)
{
int ans=n;
for(int i=2;i<=n;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
}
if(n>1)ans=ans/n*(n-1);
return ans;
}
int re()
{
int s=0;char ch=getchar();
bool pd=0;
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')
{
s=s*10+ch-48,ch=getchar();
if(s>=phi)s%=phi,pd=1;
}
return pd?s+phi:s;
}
int ksm(int a,int b,int p)
{
int ans=1;
while(b)
{
if(b&1)ans=(ans*a)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
signed main()
{
scanf("%lld%lld",&a,&n);
phi=_phi(n);
b=re();
ans=ksm(a,b,n);
printf("%lld\n",ans);
return 0;
}
```
### 例题：
[P1405](https://www.luogu.com.cn/problem/P1405)