欧拉函数的几个性质

Note

这篇文章涉及几个欧拉函数的性质

暂时没有证明，大概寒假的时候会补一下证明

定义

\(\phi(n)\)表示在1~n中与n互质的数

计算式

\[ \large{ 若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)\本质是一样的 } \]

性质1

\[ \large{ \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})} } \]

性质2

\[ \large{ n中与n互质的数的和为：\\phi(n)*n/2 } \]

性质3

\[ \large{ 若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) } \]

这个性质广泛用于递推求欧拉函数

性质4

\[ \large \sum_{d|n}\phi(d)=n \]

欧拉函数的几个性质

原文：https://www.cnblogs.com/henry-1202/p/10246196.html