欧拉函数总结

欧拉函数

定义

欧拉函数表示的是小于\(x\)的与\(x\)互质的整数个数
特殊的\(\phi(1)=1\)

计算方法

\(\phi(x)=x*\prod(1-1/p_i) (P_i表示的是x的质因数)\)
这个公式表示的是对于\(x\)的一个质因数,有\(x/p_i\)个比\(x\)小的\(p_i\)的倍数
所以对于\(p_j\)，也有\(x/p_j\)个数是ta的倍数,但是这样直接减去会减多,所以只用再减去\(p_i*p_j\)的倍数就行了

性质

1.如果p是质数,那么\(\phi(p)=p-1\)
2.如果p是质数,\(n=p^k\),那么\(\phi(p^k)=p^k-p^{k-1}\)

证明：n有唯一的质因数\(p\),所以根据公式\(\phi(p^k)=p^k*(1-1/p)=p^k-p^{k-1}\)

3.欧拉函数是积性函数,即\(\phi(n)*\phi(m)=\phi(n*m)\)

证明:n,m互质所以n和m的质因子都不相同

1. 小于n的数中与n互质的数的和为\(\phi(n)*(n/2)\)

证明:需要用到一个事实是\(gcd(n,m)=1则gcd(n,n-m)=1\),所以如果一个数m与n互质,则n-m也与n互质

5.\(n=\sum_{d|n}{\phi(d)}\)

6.\(\phi(ab)(gcd(a,b)不一定互质)=\frac{\phi(a)\phi(b)gcd(a,b)}{\phi(gcd(a,b))}\)

证明:对\(a,b\)分解质因数,如果一个质因数只在\(a或b\)中出现,那么ta只会在\(ab\)中出现,如果一个质因数在\(a,b\)中同时出现,那么ta在\(ab\)和\(gcd(a,b)\)中都会出现,所以我们根据公式只有那些同时在\(a,b\)中出现的质因数才会被算重,所以直接除掉就好了

欧拉函数总结

原文：https://www.cnblogs.com/beretty/p/10389045.html