欧拉系列(详细证明!)

Morning_Glory · 2019-07-14 20:38:00 · 算法·理论

后台显示没炸，前台看着炸公式了，可以点以下链接去看

也许更好的阅读体验(cnblog)

也许更好的阅读体验(csdn)

文章内容

欧拉函数
欧拉函数常用性质
欧拉定理
扩展欧拉定理
线性筛法
欧拉反演

欧拉函数

定义

欧拉函数是 小于等于 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}
- $\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)}\} 于是可以得到 $\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}

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

指出错误，已更正，博主最近电脑被控制，不能及时回复，敬请原谅