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} \]
证毕。