欧拉系列(详细证明!)
Morning_Glory
2019-07-14 20:38:00
后台显示没炸,前台看着炸公式了,可以点以下链接去看
[也许更好的阅读体验(cnblog)](https://www.cnblogs.com/Morning-Glory/p/11106828.html)
[也许更好的阅读体验(csdn)](https://blog.csdn.net/Morning_Glory_JR/article/details/94155283)
# 文章内容
* 欧拉函数
* 欧拉函数常用性质
* 欧拉定理
* 扩展欧拉定理
* 线性筛法
* 欧拉反演
---
# 欧拉函数
* 定义
欧拉函数是 __小于等于__ x的数中与x __互质__ 的数的 __数目__
符号 $\varphi(x)$
__互质__ 两个互质的数的最大公因数等于1,1与任何数互质
* 通式
$\varphi(x)=x\prod_{i=1}^n(1-\frac{1}{p_i})$
其中$p_i$为$n$的质因子,$n$为$x$的因子个数
---
# 欧拉函数常用性质
* 若 $n$ 为质数,显然$\varphi(n)=n-1$
$\begin{aligned}\end{aligned}$
* __欧拉函数是积性函数__
积性函数: 对于任意 __互质__ 的整数 $a$ 和 $b$ 有性质$f(ab)=f(a)·f(b)$的数论函数。
若$m,n$互质,$\varphi(mn)=\varphi(m)·\varphi(n)$
$\begin{aligned}\end{aligned}$
* 如果$x=2n$($n$为奇数),$\varphi(x)=\varphi(n)$ 即$\varphi(2n)=\varphi(n)$($n$为奇数)
n为奇数时,n与2互质,$\varphi(2)=1$
$\begin{aligned}\end{aligned}$
* 若$p$为质数,则$\varphi(p^k)=p^k-p^{k-1}$
因为与$p^k$不互质的只有$p$的倍数,而$p^k$中$p$的倍数有$p^{k-1}$个
$\begin{aligned}\end{aligned}$
* 当$x>2$时,$\varphi(x)$为偶数
这一点需要了解更相减损术 即$gcd(n,x)=gcd(n,n-x)$
由该公式我们可以知道,所有与$n$互质的数都是成对出现的
$\begin{aligned}\end{aligned}$
* 小于n的数中,与n互质的数的总和为$\varphi(n)*n/2\ \ (n>1)$
由上面的证明(更相减损术)我们知道,每一对与$n$互质的数的和为$n$,共有$\varphi(n)/2$对
$\begin{aligned}\end{aligned}$
* $n=\sum_{d|n}\varphi(d)$即$n$的因数$($包括$1$和它自己$)$的欧拉函数之和等于$n$
这条性质的运用又叫 __欧拉反演__
定义函数
$\begin{aligned}f(n)=\sum_{d|n}\varphi(d)\end{aligned}$
* $f(n)$为积性函数
$\begin{aligned}f(n)·f(m)=\sum_{i|n}\varphi(i)\sum_{j|m}\varphi(j)=\sum_{i|n}\sum_{j|m}\varphi(i)·\varphi(j)=\sum_{i|n}\sum_{j|m}\varphi(i·j)=\sum_{d|nm}\varphi(d)=f(nm)\end{aligned}$
$f(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^k)=1+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k$
$n=p_1^{k_1} ·p_2^{k_2}· \cdots·p_m^{k_m}$
$f(n)=f(p_1^{k_1})·f(p_2^{k_2})·\cdots·f(p_m^{k_m})=p_1^{k_1} ·p_2^{k_2}· \cdots·p_m^{k_m}=n$
$\begin{aligned}\end{aligned}$
---
# 欧拉定理
若$a,m$互质,$a^{\varphi(m)}≡1(mod\ m)$
* 证明
* __剩余系__ 指对于某一个特定的正整数$n$,一个整数集中的数$mod\ n$所得的余数域。
* __完全剩余系__
设$m\in Z+$,若$r_0$,$r_1...$ $r_{m-1}$为$m$个整数,并且两两模$m$不同余,则$r_0$,$r_1...$ $r_{m-1}$叫作模$m$的一个完全剩余系。
* __缩系__ 设$A$是$mod\ n$的剩余系,若任意$A$中两个元素相乘$mod\ n$后仍为$A$中的元素,则称$A$为$mod\ n$的缩系
* 若$a,m$互质,则$m$的一个缩系为
$\{x_1,x_2,x_3...x_{\varphi(m)}\}$
$\{ax_1\%m,ax_2\%m,ax_3\%m...ax_{\varphi(m)}\%m\}$也是$mod\ m$的缩系
于是可以得到
$\sum_{i=1}^{\varphi(m)}ax_i\equiv \sum_{i=1}^{\varphi(m)}x_i\ (mod\ m)$
$a^{\varphi(m)}\sum_{i=1}^{\varphi(m)}x_i\equiv \sum_{i=1}^{\varphi(m)}x_i\ (mod\ m)$
$a^{\varphi(m)}\equiv 1\ (mod\ m)$
* 而当$m$为质数时,$\varphi(m)=m-1$
$a^{(m-1)}≡1(mod\ m)$
这就是我们熟知的 __费马小定理__
* 变式 $a,m$互质$a^b≡a^{b\%\varphi(m)}(mod\ m)$
---
# 扩展欧拉定理
若$b>\varphi(m)$ 即使$a,m$__不互质__,$a^b≡a^{b \%\varphi(m)+\varphi(m)}\left(mod\ m\right)$
* 证明
从$m$中提一个质因子$p$出来 令$m=p^k·s$
有$gcd(p^k,s)=1$,即$p^k,s$互质
根据欧拉定理,我们知道$p^{\varphi(s)}≡1(mod\ s)$
根据欧拉函数是积性函数,我们知道$\varphi(s)|\varphi(m)$所以有$p^{\varphi(m)}≡p^{\varphi(s)}(mod\ s)$
设$p^{\varphi(s)}=xs+1$
那么$p^{\varphi(s)+k}=xm+p^k$
所以$p^{\varphi(s)+k}≡p^k (mod\ m)$,也有$p^{\varphi(m)+k}≡p^k (mod\ m)$
当$b\geq k$时,$p^b≡p^{b-k}·p^k≡p^{b-k}·p^{\varphi(s)+k}≡p^{b+\varphi(m)}(mod\ m)$
又因为$k\leq\varphi(p^k)\leq\varphi(m)$,所以当$b\geq 2\varphi(m)$时,满足$p^b≡p^{b-\varphi(m)}(mod\ m)$
注意是$2\varphi(m)$!
所以可以得到$p^b≡p^{b\%\varphi(m)+\varphi(m)}(mod\ m)$
因此我们可以得到对任意质数$p$都有$b\geq 2\varphi(m),p^b≡p^{b\%\varphi(m)+\varphi(m)}(mod\ m)$
非$m$质因子的$p$,有欧拉定理
将$a$因式分解,可以得到
$a^b≡a^{b\%\varphi(m)+\varphi(m)}(mod\ m)$
* 注意 $b<\varphi(m)$时,公式不一定成立
---
# 线性筛法
类似与筛素数,我们在这里利用欧拉函数是积性函数这个性质来筛$\varphi$
__$\mathcal{Code}$__
```cpp
int cnt;
int prime[maxn],phi[maxn];
bool vis[maxn];
void Euler_sieve (int n)
{
phi[1]=1;
for (int i=2;i<=n;++i){
if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;
for (int j=1;j<=cnt&&i*prime[j]<=n;++j){
vis[i*prime[j]]=true;
if (i%prime[j]==0){ phi[i*prime[j]]=phi[i]*prime[j];break;}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
```
---
# 欧拉反演
本来没有欧拉反演这个名字的,只不过大家习惯性称之为欧拉反演
所谓欧拉反演其实就是利用欧拉函数的一条性质
$\begin{aligned}n=\sum_{d|n}\varphi(d)\end{aligned}$
(上面有证明)
我们试着把$n$换成其他东西试试
$\begin{aligned}gcd(i,j)=\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d|i}\sum_{d|j}\varphi(d)\end{aligned}$
让我们求个东西试试
$\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{i=1}^n\sum_{d|i}\sum_{d|n}\varphi(d)=\sum_{d|n}\sum_{i=1}^n\sum_{d|i}\varphi(d)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}$
把它重写一遍作为结论
$\begin{aligned}\sum_{i=1}^ngcd(i,n)=\sum_{d|n}\frac{n}{d}\varphi(d)\end{aligned}$
感谢
@Everything_will_die
@bcr_233
@Pour
@渣渣lyz
指出错误,已更正,博主最近电脑被控制,不能及时回复,敬请原谅