Note
这篇文章涉及几个欧拉函数的性质
暂时没有证明，大概寒假的时候会补一下证明
完结撒花！我居然在寒假第一天就把这证明补完了...
如果下方的证明有哪里有问题的话，请在下方评论区指出，以提醒作者修改。
定义
\(\phi(n)\)表示在1~n中与n互质的数
计算式及计算方法
\[\begin{aligned}
&若n根据算术基本定理分解为n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\\
&则\phi(n)=n\prod_{i=1}^{m}\left(1-\frac{1}{p}\right)\\
&也可以变式为\phi(n)=n\prod_{i=1}^m\left(\frac{p-1}{p}\right)\\
&本质是一样的
\end{aligned}
\]
\(upd\)：\(O(\frac{\sqrt{n}}{\log n})\)计算一个数的欧拉函数
分解质因数，由性质4可以顺便算出每个\(\varphi(p^k)\)，然后因为\(\varphi\)是个积性函数，所以直接把每个值相乘即得到该数的\(\varphi\)。
直接分解质因数是\(O(\sqrt{n})\)的，但是只要预处理出根号内的质数就可以\(O(\frac{\sqrt{n}}{\log n})\)计算一个数的欧拉函数了。
性质1
\[\begin{aligned}
&\phi是积性函数，但不是完全积性函数\\
&当n,m互质时，满足:\\
&\phi(nm)=\phi(n)*\phi(m)\\
&那么显然，当n根据算术基本定理分解为n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}时\\
&\phi(n)=\prod_{i=1}^m{\phi(p_i^{c_i})}
\end{aligned}
\]
证明：
\[\begin{aligned}
&若n与m互质，则n与m没有相同的质因子\\
&设n的质因子个数为cnt_n,m的质因子个数为cnt_m，则\\
&\phi(n)*\phi(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)\\
&=\phi(nm)
\end{aligned}
\]
证毕。
性质2
对于质数\(p\)，它的欧拉函数值\(\phi(p)=p-1\)
证明：
因为\(p\)为质数，所以比它小的数都和它互质，即在1~p***有p-1个数和它互质。
证毕。
性质3
\[当n为奇数时,\phi(2*n)=\phi(n)
\]
证明：
\[\begin{aligned}
&当n为奇数时，n与2互质\\
&由欧拉函数是积性函数可知，n与2互质时，\phi(2n)=\phi(2)*\phi(n)\\
&又因为\phi(2)=1\\
&所以\phi(2n)=\phi(n)
\end{aligned}
\]
证毕。
性质4
\[当n=p^k时，\phi(n)=p^k-p^{k-1}
\]
证明：
\[因为n=p^k，所以n只有p一个质因数，则由欧拉函数的计算式可得\\
\phi(n)=p^k*(1-\frac{1}{p})=p^k-p^{k-1}
\]
性质5
\[\begin{aligned}
&n中与n互质的数的和为\phi(n)/2*n(n>1)\\
&\phi(n)(n>2)为偶数
\end{aligned}
\]
证明：
需要知道的一个基本事实是\(gcd(n,x)=gcd(n,n-x)(n>x)\)
关于这个，可以了解一下更相减损术
因为\(gcd(n,x)=gcd(n,n-x)(n>x)\)，所以与n互质的数都是成对出现的
每一对的和都为\(n\)。所以他们的和为\(\phi(n)/2*n\)。
至于\(\phi(n)(n>2)\)为偶数。因为与n互质的数都是成对出现的，所以显然与n互质的数为偶数，即\(\phi(n)\)为偶数。
证毕。
性质6
\[\begin{aligned}
&若p|n且p^2|n，则\phi(n)=\phi(\frac{n}{p})*p\\
&若p|n且p^2\not|\space\space n,则\phi(n)=\phi(\frac{n}{p})*(p-1)
\end{aligned}
\]
证明：
对于第一点
\[\begin{aligned}
&若p|n且p^2|n，则证明n和\frac{n}{p}有相同的质因子，只是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\\
\end{aligned}
\]
对于第二点
\[\begin{aligned}
&若p|n且p^2\not|\space\space n，则说明p与\frac{n}{p}互质（因为p为素数）\\
&那么根据欧拉函数为积性函数的这个性质即可证得\phi(n)=\phi(\frac{n}{p})*\phi(p)=\phi(\frac{n}{p})*(p-1)
\end{aligned}
\]
证毕。
这个性质广泛用于递推求欧拉函数
性质7
\[\sum_{d|n}\phi(d)=n
\]
证明：
\[设f(n)=\sum_{d|n}\phi(d)\\
\]
则f(n)为一个积性函数（当n，m互质时）
证明：
（设n,m互质）
\[\begin{aligned}
&f(n)*f(m)\\
&=\sum_{i|n}\phi(i)*\sum_{j|m}\phi(m)\\
&=\sum_{i|n}\sum_{j|m}\phi(i)*\phi(j)\\
&=\sum_{i|n}\sum_{j|m}\phi(i*j)\\
&=\sum_{d|nm}\phi(d)\\
&=f(nm)
\end{aligned}\\
\begin{aligned}
&可以发现的是\sum_{i|n}\sum_{j|m}\phi(i*j)涵盖了所有nm的因数的欧拉函数，即为f(n)*f(m)\\
&所以f是一个积性函数
\end{aligned}
\]
那么则有
\[\begin{aligned}
&若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)=\phi(1)+\phi(p)+\phi(p^2)+...+\phi(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}\phi(d)=n
\end{aligned}
\]
证毕。
性质8
\[\phi(n)=\sum_{d|n}\frac{\mu(d)}{d}
\]
证明
我们将性质7用狄利克雷卷积形式表示出来
\[\begin{aligned}
&\phi*1=id\\
&两边卷上\mu\\
&\phi*1*\mu=id*\mu\\
&\phi*(1*\mu)=id*\mu\\
&\phi*e=id*\mu
\end{aligned}
\]
最后一个式子写出来就是
\[\phi(n)=\sum_{d|n}\frac{\mu(d)}{d}
\]
证毕。