欧拉函数通项
\(\varphi(n)=n\prod\limits_{i=1}^n (1- \dfrac{1}{p_i})\)
常用性质
-
当 \(n\) 为质数时，\(\varphi(n)=n-1\)
-
当 \(gcd(n,m)=1\) 时 \(\varphi(nm)=\varphi(n) * \varphi(m)\)
-
\(\varphi(p^k)=p^k-p^{k-1}\)
欧拉反演
\(n=\sum\limits_{d|n}\varphi(d)\)
证明：
令 \(f(n)=\sum\limits_{d|n}\varphi(d)\)
$ f(n)* f(m)=\sum\limits_{i|n}\sum\limits_{j|m}\varphi(i)* \varphi(j)
=\sum\limits_{ij|nm}\varphi(ij)=f(nm) $
\(f(p^k)=\varphi(p^0)+\varphi(p^1)+...+\varphi(p^k)\)
\(\qquad\ \ =1+(p^1-1)+...+(p^k-p^{k-1})\)
\(\qquad\ \ =p^k\)
\(f(n)=f(p_1^{k_1})f(p_2^{k_2})...f(p_n^{k_n})=n\)
\(n=\sum\limits_{d|n}\varphi(d)\)
扩展欧拉定理
\( a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m \)
标签：函数,limits,sum,varphi,nm,欧拉,gcd From： https://www.cnblogs.com/xingke233/p/18492634