欧拉定理及扩展欧拉定理
lunivia
·
·
算法·理论
整除
若 n\bmod p=0 则 p|n，即 p 可以被 n 整除。
同余
若 a,b 除于 p 的余数相同，则记为 a\equiv b\pmod p。
通常情况下 p\in \mathbb{N^\ast}。
欧拉函数
$\varphi(n)$ 是积性函数，即满足 $\gcd(n,m)=1,\varphi(nm)=\varphi(n)\times\varphi(m)$。
单个欧拉函数求法：
$$\varphi(n)=n\prod\limits_{p|n}(1-\frac{1}{p_i})$$
```
int GetPhi(int n) {
int ans = n;
for(int i = 2;i * 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;
}
```
证明：
设 $a=p^k(k\in\mathbb{N^{\ast}})$ 且 $p$ 是质数，则显然 $a$ 与 $p,2p,\dots,p^{k-1}p$ 不互质，那么 $\varphi(a)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$。
将 $n$ 唯一分解：
$$n=\prod\limits_{p|n}p_i^{k_i}$$
则由积性函数得：
$$\varphi(n)=\prod\limits_{p|n}\varphi(p_i^{k_i})=\prod\limits_{p|n}p_i^{k_i}(1-\frac{1}{p_i})=n\prod\limits_{p|n}(1-\frac{1}{p_i})$$
由于欧拉函数是积性函数，所以可以直接线性筛。
```
void Sieve(int siz,int p[],int phi[]) {
int ncnt = 0;
vector<int> vis(siz + 5);
phi[1] = 1;
for(int i = 2;i <= siz;i++) {
if(!vis[i]) {
p[++ncnt] = i;
phi[i] = i - 1;
}
for(int j = 1;j <= ncnt && i * p[j] <= siz;j++) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j]; //p[j]是i*p[j]的最小质因子
break;
}
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
```
## 欧拉定理
若 $\gcd(a,p)=1,a^{\varphi(p)}\equiv 1\pmod p$。
证明：
这里不包含 $p=1$ 的情况。
由于 $\varphi(p)<p$，那么由上面的方法可得 $a,2a,\dots,\varphi(p)a$ 在模 $p$ 后互不相同。
$$\prod\limits_{i=1}^{\varphi(p)}A_i\equiv\prod\limits_{i=1}^{\varphi(p)}(A_ia)\pmod p$$
$$\varphi(p)!\equiv \varphi(p)!a^{\varphi(p)}\pmod p$$
$$a^{\varphi(p)}\equiv 1\pmod p$$
特别的，当 $p$ 是质数时 $\varphi(p)=p-1$，这就等价于 $a^{p-1}\equiv 1\pmod p$ 也就是费马小定理。
### 扩展欧拉定理
$$a^b=\begin{Bmatrix}a^{b\bmod\varphi(p)},\gcd(a,p)=1\\a^b,\gcd(a,p)\ne1,b<\varphi(p),\pmod p\\a^{b\bmod\varphi(p)+\varphi(p)},\gcd(a,p)\ne1,b\ge \varphi(p)\end{Bmatrix}$$
简单来说就是若 $\gcd(a,p)\ne 1,b\ge\varphi(p)$ 则 $a^b\equiv a^{b\bmod\varphi(p)+\varphi(p)}\pmod p$，这可用于 $b$ 很大时降次。
证明：
第一行式子由欧拉定理易得，不证。
第二与第三行：
我们取 $m|p$ 且 $m$ 是质数，令 $k=\frac{p}{m}$。
由欧拉定理得：$a^{\varphi(m)}\equiv 1\pmod m$。
因为 $\varphi(m)|\varphi(p)$，所以 $a^{\varphi(p)}\equiv 1\pmod m$。
同时乘 $a^k$，得到 $a^{\varphi(p)+k}\equiv a^k\pmod p$。
所以 $a^b\equiv a^{b-k+k}\equiv a^{\varphi(p)+b}\pmod p$。
因为 $b\ge\varphi(p)$，所以这个结论显然成立。
所以 $a^b\equiv a^{\varphi(p)+b}\pmod p$。
这就可以证明 $n$ 为质数的幂次方时的情况。剩余的用唯一分解定理即可简单证明。
[模板](https://www.luogu.com.cn/problem/P5091)
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>T Pow(T a,T b,T p,T ans=1){for(;b;b/=2){ans=((b&1?a:1)*ans%p),a=a*a%p;}return ans;}
int a,b,m,v;
inline int Read() {
int x = 0,f = 0;
char c = getchar();
for(;c < '0' || c > '9';c = getchar());
for(;c >= '0' && c <= '9';c = getchar()) {
x = (x << 3) + (x << 1) + (c ^ 48);
if(x >= v) f = 1;
x %= v;
}
return f ? x + v : x;
}
int GetPhi(int n) {
int ans = n;
for(int i = 2;i * 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;
}
signed main() {
cin >> a >> m;
v = GetPhi(m);
b = Read();
if(b < v) cout << Pow(a,b,m) << '\n';
else cout << Pow(a,b % v + v,m) << '\n';
return 0;
}
```