互质与欧拉函数

互质

我们定义两个正整数 (a,b) ，若 (a,b) 的最大公因数为 (1)

对这类特殊的数对，我们称呼为互质

即 (a,b) 互质 (Leftrightarrow gcd(a,b)=1)

简化剩余类

考虑 (n) 的 (n) 个剩余类，其中对于所有与 (n) 互质的剩余类称为简化剩余类

可以证得，简化剩余类的数量为 (displaystyle sum_{i=1}^n[gcd(i,n)=1])

我们从每个简化剩余类中抽出一个数，分别命名为 (a_{1cdots m}) （即代表有 (m) 个简化剩余类）

易得到 (forall 1leq ileq m,gcd(a_i,n)=1)

欧拉函数

欧拉函数 (oldsymbol varphi(n)) 定义为：小于等于 (n) 的正整数中，与 (n) 互质的数的个数

我们引入符号 ([condition]) 为一个值：当 (condition) 为真时，值为 (1) ；否则为 (0)

因此可以这么写： (displaystyle oldsymbolvarphi(n)=sum_{i=1}^n[gcd(i,n)=1])

欧拉函数的性质

首先，根据定义，不难得出 (oldsymbolvarphi(1)=1)

而根据质数的定义，还容易得出 (oldsymbolvarphi(p)=p-1,pin Prime)

因为所有比它小的数中，只有 (1) 是它的因数，其它的都与它互质；而 (gcd(1,p)=1)

我们考虑质数的正整数次方：对于质数 (p) 的 (k) 次方 (p^k)

显然：小于等于它的数一共 (p^k) 个，只有含有质因数 (p) 的数与它不互质，这些数为：

(p,2p,3pcdots p^{k-1}cdot p) 共 (p^{k-1}) 个

故 (oldsymbol varphi(p^k)=p^k-p^{k-1},pin Prime,kin Z_+)

同时还能得到递推式： (oldsymbol varphi(p^{k+1})=p^{k+1}-p^k=p(p^k-p^{k-1})=pcdot oldsymbolvarphi(p^k))

接下来我们证明欧拉函数的积性性质：

即 (gcd(M,N)=1Rightarrowoldsymbolvarphi(NM)=oldsymbol varphi(N)cdotoldsymbolvarphi(M))

证明：

考虑到 (N) 有 (oldsymbolvarphi(N)) 个简化剩余类， (M) 有 (oldsymbolvarphi(M)) 个

则设 (N) 的简化剩余类中各取一个数，构成集合 (A) ； (M) 中的构成集合 (B)

因此 (gcd(aM+bN,M)=gcd(bN,M)=gcd(b,M)=1,ain A,bin B)

同理 (gcd(aM+bN,N)=1)

考虑到若 (gcd(a,c)=1,gcd(b,c)=1,gcd(a,b)=1)

则 (a,b,c) 所含的质因数互不相同，因此 (gcd(ab,c)=1)

因此，回归到上面：

由于 (gcd(aM+bN,M)=1,gcd(aM+bN,N)=1,gcd(M,N)=1)

因此 (gcd(aM+bN,MN)=1)

而 (a) 一共有 (oldsymbol varphi(N)) 个不同的取值，每个都满足 ((aM+bNmod MN)) 互不相同且 (gcd(aM+bN,NM)=1)

(b) 一共有 (oldsymbolvarphi(M)) 个不同取值，也满足上式

故根据乘法原理：一共有 (oldsymbolvarphi(N)cdotoldsymbolvarphi(M)) 个数使得 (MN) 互质

因此 (oldsymbolvarphi(NM)=oldsymbolvarphi(N)cdotoldsymbolvarphi(M))

欧拉函数的积性性质可以形成新的推论：

(displaystyle oldsymbolvarphi(prod_{i=1}^mp_i^{c_i})=prod_{i=1}^moldsymbolvarphi(p_i^{c_i}))

据此可演化出了欧拉函数的求法与筛法

欧拉函数的求法

设 (displaystyle n=prod_{i=1}^mp_i^{c_i}) 则

(displaystyle oldsymbolvarphi(n)=prod_{i=1}^moldsymbolvarphi(p_i^{c_i})=prod_{i=1}^m(p_i^{c_i}-p_i^{c_i-1})=(prod_{i=1}^mp_i^{c_i})cdot(prod_{i=1}^m(1-{1over p_i}) ))

代入 (n) 的定义得 (displaystyle oldsymbolvarphi(n)=nprod_{i=1}^m{p_i-1over p_i})

用类似于质因数分解的方法即可 (O(sqrt n)) 求出

sieve(sqrt(n));
int copy=n,ans=1;
for(int i=1;i<=cntprime;i++){
    if(copy%prime[i]!=0) continue;
    ans*=prime[i]-1;
    copy/=prime[i];
    while(copy%prime[i]==0){
        copy/=prime[i];
        ans*=prime[i];
    }
}
if(copy!=1) ans*=copy-1;

欧拉函数的筛法

设 (nin Z_+,pin Prime)

若 (p^kmid n,p^{k+1} mid n,kin Z_+)

则 (oldsymbolvarphi(n imes p)=oldsymbolvarphi({nover p^k} imes p^k imes p)=oldsymbolvarphi({nover p^k})cdotoldsymbolvarphi(p^{k+1})=oldsymbolvarphi({nover p^k}) imes pcdotoldsymbolvarphi(p^k))

故 (oldsymbolvarphi(n imes p)=pcdotoldsymbolvarphi(n))

若 (p mid n) 则 (oldsymbolvarphi(n imes p)=oldsymbolvarphi(p)cdotoldsymbolvarphi(n)=(p-1)cdotoldsymbolvarphi(n))

总结起来就是： (oldsymbolvarphi(p imes n)=oldsymbolvarphi(n) imes egin{cases} p,pmid n \ \ p-1,p mid n end{cases})

使用线性筛可以 (O(n)) 求出

int prime[MAXN],fc[MAXN],phi[MAXN],cntprime;
phi[1]=1;
for(int i=2;i<=n;i++){
    if(fc[i]==0){
        prime[++cntprime]=i;
        fc[i]=i;
        phi[i]=i;
    }
    for(int j=1;j<=cntprime&&j<fc[i]&&j*i<=n;j++){
        fc[i*prime[j]]=prime[j];
        phi[i*prime[j]]=phi[i]*(prime[j]-1);
    }
    phi[i*fc[i]]=phi[i]*fc[i];
    fc[i*fc[i]]=fc[i];
}