预备知识

• 剩余系:指对于某一个特定的正整数ｎ，一个整数集中的数mod n所得的余数域。

• 完全剩余系: $设m\in Z+，若r_0,r_1,...r_{m-1}为m个整数，并且两两模m不同余，则r_0,r_1,...r_{m-1}叫作模m的一个完全剩余系。$设m∈Z+，若r0​,r1​,...rm−1​为m个整数，并且两两模m不同余，则r0​,r1​,...rm−1​叫作模m的一个完全剩余系。

• 缩系:设A是mod n的剩余系，若任意A中两个元素相乘mod n后仍为A中的元素,则称A为mod n的缩系

好吧其实后面好像用不上，但总还是有用的。

欧拉函数

• 定义

$\phi \left(n\right)$φ(n)为不超过n且与n互质的数的个数。

显然，若p为质数， $\phi \left(p\right)=p-1$φ(p)=p−1

$\phi \left(p^k\right)=p^k-p^{k-1}$φ(pk)=pk−pk−1　因为与 $p^k$pk不互质的只有p的倍数，而p的倍数有 $P^{k-1}$Pk−1个。

欧拉函数是积性函数。

证明:（需要中国剩余定理）

$n=p_1^{k_1}{p}_2^{k_2}...p_m^{k_m}$n=p1k1​​p2k2​​...pmkm​​

若x,n互质，则x%n, $p_1^{k_1}也互质$p1k1​​也互质

$\{\begin{array}{c}x\equiv a_1 mod p_1^{k_1}\\ x\equiv a_2 mod p_2^{k_2}\\ ...\\ x\equiv a_m mod p_m^{k_m}\end{array}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡　a1​　mod　p1k1​​x≡　a2​　mod　p2k2​​...x≡　am​　mod　pmkm​​​

$x,a_i,p_i^{k_1}均互质$x,ai​,pik1​​均互质

在一组方程中， $a_i$ai​ 有多种取法，需满足gcd( $a_1,p_1^{k_1})=1$a1​,p1k1​​)=1

$\therefore$∴　 $\phi \left(p_i^{k_i}\right)$φ(piki​​)=sizeof{ $a_i$ai​}

根据中国剩余定理，在１～ｎ范围内有唯一ｘ，又gcd(x,n)=1

则x有 $\phi \left(n\right)$φ(n)中取法

对于每一个ｘ，与{ $a_1,a_2,...,a_m$a1​,a2​,...,am​}集合唯一对应

有 $N_{a_1}\ast N_{a_2}\ast ...\ast N_{a_m}$Na1​​∗Na2​​∗...∗Nam​​种方法

= $\phi \left(p_1^{k_1}\right)\ast \phi \left(p_2^{k_2}\right)\ast ...\ast \phi \left(p_m^{k_m}\right)$φ(p1k1​​)∗φ(p2k2​​)∗...∗φ(pmkm​​)

分别对应一个唯一的ｘ

$\therefore$∴　 $\phi \left(p_1^{k_1}\right)\ast \phi \left(p_2^{k_2}\right)\ast ...\ast \phi \left(p_m^{k_m}\right)=\phi \left(n\right)$φ(p1k1​​)∗φ(p2k2​​)∗...∗φ(pmkm​​)=φ(n)

又 $n=p_1^{k_1}{p}_2^{k_2}...p_m^{k_m}$n=p1k1​​p2k2​​...pmkm​​

$\therefore$∴　 $\phi$φ为积性函数

若gcd(a,M)=1,则 $a^{\phi \left(M\right)}\equiv 1 \left(mod M\right)$aφ(M)≡　1　(mod　M)

证明:

设a,M互质,有M的一个缩系为{ $a,2a,...,\phi \left(M\right)a$a,2a,...,φ(M)a},缩系元素个数为 $\phi \left(M\right)$φ(M)个

$\phi \left(M\right)! \equiv \prod ^{\phi \left(M\right)}{a}_i \left(mod M\right)$φ(M)!　≡　∏φ(M)​ai​　(mod　M)

$\phi \left(M\right)! \equiv a^{\phi \left(M\right)}\phi \left(M\right)! \left(mod M\right)$φ(M)!　≡　aφ(M)φ(M)!　(mod　M)

$a^{\phi \left(M\right)}\equiv 1 \left(mod M\right)$aφ(M)≡　1　(mod　M)

当M为质数时，则有 $\phi \left(M\right)=M-1$φ(M)=M−1,即费马小定理

扩展欧拉定理

如果gcd(a,M)!=1,那么 $a^b\equiv a^{b mod \phi \left(M\right)+\phi \left(M\right)} \left(mod M\right)(b\>\phi (M\left)\right)$ab≡ab　mod　φ(M)+φ(M)　(mod　M)(b>φ(M))

证明:

先考虑 $M$M的一个质因子p , $gcd(p,M)=p$gcd(p,M)=p
把 $M$M分解:　 $M=s\ast p^k,gcd(s,p)=1$M=s∗pk,gcd(s,p)=1
可得:　 $p^x\equiv p^{x mod \phi \left(s\right)} mod s (x\>\phi (s\left)\right)$px≡px　mod　φ(s)　mod　s　(x>φ(s))
又 $\because$∵　 $\phi \left(s\right)\mid \phi \left(M\right)$φ(s)∣φ(M)( $\phi$φ是积性函数)
　 $\therefore$∴　 $p^x\equiv p^{x mod \phi \left(M\right)} mod M$px≡px　mod　φ(M)　mod　M
更有　 $p^x\equiv p^{x mod \phi \left(M\right)+\phi \left(M\right)} mod M$px≡px　mod　φ(M)+φ(M)　mod　M

对于任意一个数 $a,gcd(a,M)=b,b≠1$a,gcd(a,M)=b,b≠​1
有 $a=b^{k_1}\ast r_1,gcd(r_1,M)=1$a=bk1​∗r1​,gcd(r1​,M)=1
则 $a^x\equiv {b^{k_1}}^x\ast {r_1}^x mod M$ax≡bk1​x∗r1​x　mod　M
　 $a^x\equiv {b^{k_1}}^{x mod \phi \left(M\right)+\phi \left(M\right)}\ast {r_1}^{x mod \phi \left(M\right)+\phi \left(M\right)} mod M$ax≡bk1​x　mod　φ(M)+φ(M)∗r1​x　mod　φ(M)+φ(M)　mod　M
　 $a^x\equiv {b^{k_1}\ast r_1}^{x mod \phi \left(M\right)} mod M$ax≡bk1​∗r1​x　mod　φ(M)　mod　M
即 $a^x\equiv a^{x mod \phi \left(M\right)+\phi \left(M\right)} mod M (x\>\phi (M\left)\right)$ax≡ax　mod　φ(M)+φ(M)　mod　M　(x>φ(M))
证毕

ok,继续之前的内容

当n= $p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}$p1a1​​p2a2​​...pkak​​时

$\varphi \left(n\right)=\prod _{i=1}^k{p}_i^{a_i-1}(p_i-1)=n\ast \prod _{i=1}^k(1-\frac{1}{p_i})=n\ast \prod _{i=1}^k\frac{p_i-1}{p_i}$ϕ(n)=i=1∏k​piai​−1​(pi​−1)=n∗i=1∏k​(1−pi​1​)=n∗i=1∏k​pi​pi​−1​
可以用此式子递推

递推证明
递推代码

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年01月22日 星期二 15时53分29秒 *******************************/
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+10;
int n=1e6,prime[maxn],vis[maxn],tot,mn[maxn],e[maxn],phi[maxn],d[maxn],mu[maxn];
//e最小质因子的个数,mn最小质因子,phi欧拉函数,d约数个数,mu莫比乌斯函数
void euler_sieve()
{
    mu[1]=1;phi[1]=1;
        for(int i=2;i<=n;i++)
        {
                if(!vis[i]) { prime[++tot]=i;mn[i]=i;e[i]=1;phi[i]=i-1;d[i]=2;mu[i]=-1; }
                for(int j=1;j<=tot and prime[j]*i<=n;j++)
                {
                        vis[prime[j]*i]=1;
                        mn[prime[j]*i]=prime[j];
                        e[prime[j]*i]=1;
                        if(i%prime[j]==0)
                        {
                                phi[i*prime[j]]=phi[i]*prime[j];
                                e[prime[j]*i]=e[i]+1;
                                d[i*prime[j]]=d[i]/(e[i]+1)*(e[i]+2);
                                break;
                        }
                        else phi[i*prime[j]]=phi[i]*(prime[j]-1);
                        mu[i*prime[j]]=-mu[i];
                        d[i*prime[j]]<<=1;
                }
        }
}
int main()
{
}

欧拉反演

$\begin{array}{c}{\displaystyle \sum _{i=1}^{n}gcd(i,n)=\sum _{d\mid n}\frac{n}{d}\phi \left(d\right)}\end{array}$i=1∑n​gcd(i,n)=d∣n∑​dn​φ(d)​
证明:
首先有 $\begin{array}{c}{\displaystyle n=\sum _{d\mid n}\phi \left(d\right)}\end{array}$n=d∣n∑​φ(d)​

即n的因数(包括1和它自己))的欧拉函数之和等于n

证明

设 $\begin{array}{c}{\displaystyle f\left(n\right)=\sum _{d\mid n}\phi \left(d\right)}\end{array}$f(n)=d∣n∑​φ(d)​,有 $f$f是积性函数。

$\begin{array}{c}{\displaystyle f\left(n\right)\cdot f\left(m\right)=\sum _{i\mid n}\phi \left(i\right)\sum _{j\mid m}\phi \left(j\right)=\sum _{i\mid n}\sum _{j\mid m}\phi \left(i\right)\cdot \phi \left(j\right)=\sum _{i\mid n}\sum _{j\mid m}\phi (i\cdot j)=\sum _{d\mid nm}\phi \left(d\right)=f\left(nm\right)}\end{array}$f(n)⋅f(m)=i∣n∑​φ(i)j∣m∑​φ(j)=i∣n∑​j∣m∑​φ(i)⋅φ(j)=i∣n∑​j∣m∑​φ(i⋅j)=d∣nm∑​φ(d)=f(nm)​

$f\left(p^k\right)=\phi \left(1\right)+\phi \left(p\right)+\phi \left(p^2\right)+\cdots +\phi \left(p^k\right)=1+(p-1)+(p^2-p)+\cdots +(p^k-p^{k-1})=p^k$f(pk)=φ(1)+φ(p)+φ(p2)+⋯+φ(pk)=1+(p−1)+(p2−p)+⋯+(pk−pk−1)=pk

$f\left(n\right)=f\left(p_1^{k_1}\right)\cdot f\left(p_2^{k_2}\right)\cdot \cdots \cdot f\left(p_m^{k_m}\right)=p_1^{k_1}\cdot p_2^{k_2}\cdot \cdots \cdot p_m^{k_m}=n$f(n)=f(p1k1​​)⋅f(p2k2​​)⋅⋯⋅f(pmkm​​)=p1k1​​⋅p2k2​​⋅⋯⋅pmkm​​=n

把n=gcd(i,j)代入得

$\begin{array}{c}{\displaystyle gcd(i,j)=\sum _{d\mid gcd(i,j)}\phi \left(d\right)=\sum _{d\mid i}\sum _{d\mid j}\phi \left(d\right)}\end{array}$gcd(i,j)=d∣gcd(i,j)∑​φ(d)=d∣i∑​d∣j∑​φ(d)​

$\begin{array}{c}{\displaystyle \sum _{i=1}^{n}gcd(i,n)=\sum _{i=1}^n\sum _{d\mid i}\sum _{d\mid n}\phi \left(d\right)=\sum _{d\mid n}\sum _{i=1}^n\sum _{d\mid i}\phi \left(d\right)=\sum _{d\mid n}\frac{n}{d}\phi \left(d\right)}\end{array}$i=1∑n​gcd(i,n)=i=1∑n​d∣i∑​d∣n∑​φ(d)=d∣n∑​i=1∑n​d∣i∑​φ(d)=d∣n∑​dn​φ(d)​

即 $\begin{array}{c}{\displaystyle \sum _{i=1}^{n}gcd(i,n)=\sum _{d\mid n}\frac{n}{d}\phi \left(d\right)}\end{array}$i=1∑n​gcd(i,n)=d∣n∑​dn​φ(d)​