欧拉函数性质
前言：欧拉函数的定义 \(\varphi(n)\) 为 \(1-n\) 中与 \(n\) 互质的数。
1证明： \(\varphi(1)=1\)
\[\because 只有1与1本身互质\\ \therefore \varphi(1)=1 \]2证明：\(当p是质数时，\varphi(p)=p-1\)
\[\because p是质数\\ \therefore \forall x(1<x<p) gcd(x,p)=1\\ \therefore \varphi(p)=p-1 \]3证明：\(当p是质数时，对于n=p^k,\varphi(n)=p^k-p^{k-1}=(p-1)\times p^{k-1}\)
\[\because n=p^k\\ \therefore \varphi(n)=n-\frac n p\\ =n(1-\frac 1 p)\\ =p^k\times1-p^k\times \frac 1 p\\ =p^k-p^{k-1}\\ =p^{k-1}\times \frac {p^k-p^{k-1}} {p^{k-1}}\\ =p^{k-1}\times (\frac {p^k} {p^{k-1}}-\frac {p^k} {p^k})\\ =p^{k-1}\times (p-1)\\ =p^k-p^{k-1} \]4证明：\(对于gcd(a,b)=1,\varphi(a\times b)=\varphi(a)\times \varphi(b)\)
\[设a=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n},b=q_1^{d_1}q_2^{d_2}\cdots q_m^{d_m}\\ \therefore \varphi(a\times b)=a\times b(1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n})(1-\frac 1 {q_1})(1-\frac 1 {q_2})\cdots (1-\frac 1 {q_m})\\ =(a\times (1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n}))(b\times (1-\frac 1 {q_1})(1-\frac 1 {q_2})\cdots (1-\frac 1 {q_m}))\\ =\varphi(a) \times \varphi(b) \]5证明1：\(对于质数p，若n\%p=0,则\varphi(n\times p)=\varphi(n)\times p\)
\[设n=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}\\ \because n\%p=0\\ \therefore lcm(n,p)=n\\ \therefore \varphi(n\times p)=p\times n(1-\frac 1 {p_1})(1-\frac 1 {p_2})\cdots (1-\frac 1 {p_n})=\varphi(n)\times p \]证明2：\(对于质数p，若n\%p!=0,则\varphi(n\times p)=\varphi(n)\times (p-1)\)
\[\because p是质数\\ \therefore \varphi(p)=p-1,p与n互质\\ \therefore \varphi(n\times p)=\varphi(n)\times \varphi(p)=\varphi(n)\times (p-1) \]7证明： \(\sum_{d\vert n} \varphi(d)=n\)
\[设 f(n)=\sum_{d\vert n} \varphi(d)\\ \because f(n\times m)=\sum_{d\vert nm} \varphi(d)=\sum_{d\vert n} \varphi(d)\cdot\sum_{d\vert m} \varphi(d)=f(n) \times f(m)\\ \therefore f(x)是积性函数\\ f(p^m)=\sum_{d|p^m} \varphi(d)=\varphi(p^0) + \varphi(p^1) + \cdots + \varphi(p^m)=1+(p^1-1)+(p^2-p^1)+\cdots +(p^m-p^{m-1})=p^m\\ 设n=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}\\ \therefore f(n)=f(p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n})=f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_n^{c_n})=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}=n \therefore \sum_{d\vert n} \varphi(d)=f(n)=n \] 标签：frac,函数,sum,varphi,times,cdots,therefore,证明,欧拉 From： https://www.cnblogs.com/lyz09-blog/p/Prove-PhiFunction.html