欧拉函数
前置知识
-
积性函数
对于函数
f ，若有任意两互质的正整数m,n ，使得f(mn)=f(m)f(n) ，则称该函数是积性的。若
f 是积性函数，那么对于正整数n=\prod p_i^{a_i} ，其中p_i 是互不相等的素数，则有：f(n)=\prod f(p_i^{a_i}) 。
定义
对于任意正整数
学过剩余系的大佬已经有所察觉，事实上，欧拉函数一般用于表示
性质
-
性质
1 ：欧拉函数是积性函数，但不是完全积性函数。
证明：
本蒟蒻的证明不严谨，可以上网搜搜，较为复杂难懂就不放上来了。
-
性质
2 ：若
x 为质数，则有：\phi(x)=x-1 证明：
太过显然，不证。
-
性质
3 ：若
x 为正奇数，则有：\phi(2x)=\phi(x) 证明：
因为
2 与任意奇数互质，所以由性质1 可知：\phi(2x)=\phi(2)*\phi(x) 又因为
\phi(2)=1 ，所以:\phi(2x)=1*\phi(x)=\phi(x) 证毕。
-
性质
4 ：若
p 为质数，a 为任意正整数，则有：\phi(p^a)=(p-1)p^{a-1} 证明：
显然小于等于
p^a 的正整数共有p^a 个。由于
p^a 的质因子均为p ，所以其中与p^a 不互质的数共有p^{a-1} 个，分别为：p,2p...p^{a-1}p 。由容斥原理知，与
p^a 互质的正整数数目即为：p^a-p^{a-1} 。转换为欧拉函数：
\phi(p^a)=p^a-p^{a-1}=(p-1)p^{a-1} 证毕。
-
性质
5 ：对于任意正整数
x ，都有：\phi(x)=n\prod\frac{p_i-1}{p_i} 其中
p_i 为x 的质因子。证明：
由性质
1 知欧拉函数是积性函数，那便有：\phi(x)=\prod\phi(p_i^{a_i}) 由性质
4 知：\phi(p_i^{a_i})=(p_i-1){p_i}^{a_i-1} 综上：
\phi(x) =\prod\phi(p_i^{a_i}) =\prod(p_i-1){p_i}^{a_i-1} =\prod{p_i}^{a_i}(1-\frac 1{p_i}) =n\prod({1-\frac 1{p_i}}) =n\prod\frac{p_i-1}{p_i} 证毕。
-
性质
6 ：对于质数
p ，若有p\mid n 且p^2\mid n ，则有：\phi(n)=\phi(n/p)*p 反之，若有
p\mid n 且p^2\nmid n ，则有：\phi(n)=\phi(n/p)*(p-1) 可以用于线性求欧拉函数。
证明：
对于第一种情况，利用性质
5 展开后比较两项可发现，分数部分没有变化，这是因为p 的指数大于1 。于是：
\frac {\phi(n)}{\phi(n/p)}=\frac{n}{n/p}=p 整理后原式成立。
对于第二种情况，易发现分数部分产生变化的只有
p 项。同第一种情况的推法，就能得出原式了。 -
性质
7 ：\phi(ab)=\phi(a)*\phi(b)* \frac{\gcd(a,b)}{\phi(\gcd(a,b))} 用于转换
\phi 里带乘积的式子。证明：
大力推式子，定义
d=\gcd(a,b) 。$\phi(a)=a*\prod\limits_{p_i\in P,p_i\mid a} \frac {p_i-1}{p_i}$，$\phi(b)=b*\prod\limits_{p_i\in P,p_i\mid b} \frac {p_i-1}{p_i}$，$\frac{d}{\phi(d)}=\frac {d}{d*\prod\limits_{p_i\in P,p_i\mid d} \frac {p_i-1}{p_i}}=\prod\limits_{p_i\in P,p_i\mid d} \frac {p_i}{p_i-1}$。 只需证明 $\prod\limits_{p_i\in P,p_i\mid (ab)} \frac {p_i-1}{p_i}=\prod\limits_{p_i\in P,p_i\mid a} \frac {p_i-1}{p_i}\prod\limits_{p_i\in P,p_i\mid b} \frac {p_i-1}{p_i}\prod\limits_{p_i\in P,p_i\mid d} \frac {p_i}{p_i-1}$ 即可。 考虑 $ab$ 的质因子怎么由 $a,b$ 得来，其实是将 $a,b$ 的质因子暴力合在一起，然后去掉重复的，即 $d$ 的质因子。不难发现上式的 $\prod\limits_{p_i\in P,p_i\mid d} \frac {p_i}{p_i-1}$ 部分刚好抵消重复部分的质因子。证毕。 -
性质
8 ：n=\sum\limits_{d\mid n} \phi(d) 欧拉反演式子，
人称小莫反。证明：
首先
n=\sum\limits_{1\le i\le n,i\in N^+} 1 ，考虑将[1,n] 中的数按照与n 的\gcd 分类，即n=\sum\limits_{d\mid n} \sum\limits_{gcd(i,n)=d} 1 。如何快速求出后半部分？考虑对
\gcd(a,b)=d 的常规处理方式，若\gcd(i,n)=d ，则有\gcd(\frac{i}{d},\frac{n}{d})=1 ，因此\sum\limits_{gcd(i,n)=d}1=\phi(\frac nd) 。于是
n=\sum\limits_{d\mid n} \phi(\frac nd)=\sum\limits_{d\mid n} \phi(d) ，这是因为约数一一对应。有待补充。。。