欧拉函数

· · 算法·理论

定义

欧拉函数，记作\varphi(n),表示[1,n]中的正整数中，与n互质的数的个数

在算数基本定理中，n=p_1^{c_1}p_2^{c_2}...p_k^{c_k},那么有

\varphi(N)=N\times \prod_{p|N}(1-\frac{1}{p})

具体证明如下：

若N是一个质数，那么\varphi(N)=N-1，显然

若N=p^k，则只有p的倍数不与N互质，所以\varphi(N)=p^k-p^{k-1}=p^k\times(1-\frac{1}{p})=N\times(1-\frac{1}{p})

由于欧拉函数是积性函数，所以证毕

性质

1.\forall n>1 [1,n]中所有与n互质的数之和为n\times\varphi(n)/2

2.若a,b互质，则\varphi(ab)=\varphi(a)\times\varphi(b)，积性函数

3.若p为素数，若p\mid n且p^2\mid n，则\varphi(n)=\varphi(n/p)\times p

4.若p为素数，若p\mid n且p^2\nmid n，则\varphi(n)=\varphi(n/p)\times (p-1)

5.\sum\limits_{d\mid n}{\varphi(d)}=n

证明134

1.因为\gcd(n,x)=\gcd(n,n-x)，所以互质的数是成双出现的，他们的平均数为n/2，所以得证性质1

3&4.拆开套公式

证明5

定义f(n)=\sum\limits_{d\mid n}{\varphi(d)}，有f(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)=p^m(等比数列求和)

再证f()是一个积性函数：令\gcd(n,m)=1，则

f(n)=\sum\limits_{d_1\mid n}{\varphi(d_1)}，f(m)=\sum\limits_{d_2\mid m}{\varphi(d_2)}

因为n,m没有除1外的公因数，所以上述d_1,d_2没有交集

\therefore f(n)\times f(m)=\sum\limits_{d\mid nm}{\varphi(d)}=f(nm)

所以f()是一个积性函数，所以得证

计算方法

法1： 使用公式进行计算

法2： 使用欧拉筛获得[1,n]所有数的欧拉函数。具体操作使用性质3&性质4。