欧拉函数的几个性质及证明
定义
\(\varphi(n)\)表示在\(1\)~\(n\)中与\(n\)互质的数
计算式及计算方法
若n根据算术基本定理分解为\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)
则\(\varphi(n)=n\prod_{i=1}^{m}\left(1-\frac{1}{p}\right)\\\)
也可以变式为\(\varphi(n)=n\prod_{i=1}^m\left(\frac{p-1}{p}\right)\\\)
本质是一样的
计算一个数的欧拉函数
分解质因数，由性质4可以顺便算出每个\(\varphi(p^k)\)，然后因为\(\varphi\)是个积性函数，所以直接把每个值相乘即得到该数的\(\varphi\)。直接分解质因数是\(O(\sqrt{n})\)的，但是只要预处理出根号内的质数就可以\(O(\frac{\sqrt{n}}{\log n})\)计算一个数的欧拉函数了。
性质1
\(\varphi\)是积性函数，但不是完全积性函数
当\(n\),\(m\)互质时，满足:\(\\ \varphi(nm)=\varphi(n)*\varphi(m)\)那么显然，
当\(n\)根据算术基本定理分解为\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)时$ \varphi(n)=\prod_{i=1}m{\varphi(p_i{c_i})}$
证明：
若\(n\)与\(m\)互质，则\(n\)与\(m\)没有相同的质因子
设\(n\)的质因子个数为\(cnt_n, m\)的质因子个数为\(cnt_m\)，则
\(\varphi(n)*\varphi(m)\)
\(=n*\prod_{i=1}^{cnt_n}(1-p_i)*m*\prod_{i=1}^{cnt_m}(1-p_i)\)
\(=n*m*\prod_{i=1}^{cnt_n+cnt_m}(1-p_i)\)
$=\varphi(nm) $
证毕。
性质2
对于质数\(p\)，它的欧拉函数值\(\varphi(p)=p-1\)
证明：
因为\(p\)为质数，所以比它小的数都和它互质，即在\(1\)~\(p\)
有p-1个数和它互质。
证毕。
性质3
当\(n\)为奇数时,\(\varphi(2*n)=\varphi(n)\)
证明：
当\(n\)为奇数时，\(n\)与\(2\)互质
由欧拉函数是积性函数可知，n与2互质时，\(\varphi(2n)=\varphi(2)*\varphi(n)\)又因为\(\varphi(2)=1\)所以\(\varphi(2n)=\varphi(n)\)
证毕。
性质4
当\(n=p^k\)时，\(\varphi(n)=p^k-p^{k-1}\)
证明：
因为\(n=p^k\)，所以\(n\)只有\(p\)一个质因数，则由欧拉函数的计算式可得
\(\varphi(n)=p^k*(1-\frac{1}{p})=p^k-p^{k-1}\)
性质5
\(n\)中与\(n\)互质的数的和为\(\varphi(n)/2*n(n>1)\)
\(\varphi(n)(n>2)\)为偶数
证明：
需要知道的一个基本事实是\(gcd(n,x)=gcd(n,n-x)(n>x)gcd(n,x)=gcd(n,n−x)(n>x)\)
关于这个，可以了解一下更相减损术
因为\(gcd(n,x)=gcd(n,n-x)(n>x)gcd(n,x)=gcd(n,n−x)(n>x)\)，所以与n互质的数都是成对出现的
每一对的和都为\(n\)。所以他们的和为\(\varphi(n)/2*n\)。
至于\(\varphi(n)(n>2)\)为偶数。因为与\(n\)互质的数都是成对出现的，所以显然与\(n\)互质的数为偶数，即\(\varphi(n)\)为偶数。
证毕。
性质6
若\(p|n\)且\(p^2|n\)，则\(\varphi(n)=\varphi(\frac{n}{p})*p\)
若\(p|n\)且\(p^2\not|\space\space n\),则\(\varphi(n)=\varphi(\frac{n}{p})*(p-1)\)
证明：
对于第一点
若\(p|n\)且\(p^2|n\)，则证明\(n\)和\(\frac{n}{p}\)有相同的质因子，只是\(p\)这一项的指数不同
那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：
\[\frac{\varphi(p)}{\varphi(\frac{n}{p})} =\frac{n\prod_{i=1}^m(1-\frac{1}{p_i})}{\frac{n}{p}\prod_{i=1}^{m}(1-\frac{1}{p_i})}=\frac{n}{\frac{n}{p}}=p \]即\(\varphi(n)=\varphi(\frac{n}{p})*p\)
对于第二点
若\(p|n\)且\(p^2\not|\space\space n\)，则说明\(p\)与\(\frac{n}{p}\)互质（因为p为素数）
那么根据欧拉函数为积性函数的这个性质即可证得$\varphi(n)=\varphi(\frac{n}{p})\varphi(p)=\varphi(\frac{n}{p})(p-1) $
证毕。
这个性质广泛用于递推求欧拉函数
性质7
\(\sum_{d|n}\varphi(d)=n\)
证明：
设\(f(n)=\sum_{d|n}\varphi(d)\)
则\(f(n)\)为一个积性函数（当\(n\)，\(m\)互质时）
证明：
（设\(n\),\(m\)互质）
\(f(n)*f(m)\)
\(=\sum_{i|n}\varphi(i)*\sum_{j|m}\varphi(m)\)
\(=\sum_{i|n}\sum_{j|m}\varphi(i)*\varphi(j)\)
\(=\sum_{i|n}\sum_{j|m}\varphi(i*j)\)
\(=\sum_{d|nm}\varphi(d)\)
$=f(nm) $
可以发现的是\(\sum_{i|n}\sum_{j|m}\varphi(i*j)\)涵盖了所有\(nm\)的因数的欧拉函数，即为\(f(n)*f(m)\)
所以\(f\)是一个积性函数
那么则有
若\(n\)根据算数基本定理可以分解为\(p_1^{c_1}p_2^{c_2}...p_k^{c_k}\)
则由\(f\)是一个积性函数可知，\(f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})\)
所以\(f(p^c)=\varphi(1)+\varphi(p)+\varphi(p^2)+...+\varphi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k\)
则\(f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k}=n\)
即\(\sum_{d|n}\varphi(d)=n\)
证毕。
性质8
\(\varphi(n)=\sum_{d|n}\frac{\mu(d)}{d}\)
证明
我们将性质\(7\)用狄利克雷卷积形式表示出来
\(\varphi*1=id\)
两边卷上\(\mu\)
\(\varphi*1*\mu=id*\mu\)
\(\varphi*(1*\mu)=id*\mu\)
\(\varphi*e=id*\mu\)
最后一个式子写出来就是
\(\varphi(n)=\sum_{d|n}\frac{\mu(d)}{d}\)
证毕。
标签：frac,函数,sum,varphi,互质,欧拉 From： https://www.cnblogs.com/AC7-/p/16813703.html